Result: Power optimization for connectivity problems

Title:
Power optimization for connectivity problems
Authors:
HAJIAGHAYI, Mohammad T, KORTSARZ, Guy, MIRROKNI, Vahab S, NUTOV, Zeev
Source:
IPCO 2005, Berlin, June 8-10, 2005Mathematical programming. 110(1):195-208
Publisher Information:
Heidelberg: Springer, 2007.
Publication Year:
2007
Physical Description:
print, 25 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Recherche operationnelle. Gestion, Operational research. Management science, Recherche opérationnelle et modèles formalisés de gestion, Operational research and scientific management, Flots dans les réseaux. Problèmes combinatoires, Flows in networks. Combinatorial problems, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Logiciel, Software, Systèmes informatiques et systèmes répartis. Interface utilisateur, Computer systems and distributed systems. User interface, Algorithme approximation, Approximation algorithm, Algoritmo aproximación, Chemin graphe, Graph path, Camino grafo, Connectivité graphe, Graph connectivity, Conectividad grafo, Graphe orienté, Directed graph, Grafo orientado, Minimisation, Minimization, Minimización, Noeud graphe, Graph node, Nudo grafo, Optimisation combinatoire, Combinatorial optimization, Optimización combinatoria, Problème NP difficile, NP hard problem, Problema NP duro, Problème direct, Direct problem, Problema directo, Programmation en nombres entiers, Integer programming, Programación entera, Programmation mathématique, Mathematical programming, Programación matemática, Routage, Routing, Enrutamiento, Sous graphe, Subgraph, Subgrafo, Temps polynomial, Polynomial time, Tiempo polinomial, Théorie graphe, Graph theory, Teoría grafo, Arête disjointe, Disjoint edge, Arista disyuntiva, Réseau multi sauts, Multi hop network, Red multisalto, Réseau sans fil, Wireless network, Red sin hilo
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, United States
Department of Computer Science, Rutgers University-Camden, Camden, NJ, United States
Theory of Computation Group, Microsoft Research, Redmond, WA, United States
Computer Science Division, The Open University of Israel, Tel-Aviv, Israel
ISSN:
0025-5610
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18658084
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Operational research. Management
Accession Number:
edscal.18658084
Database:
PASCAL Archive

Further Information

Given a graph with costs on the edges, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of the nodes of this graph. Motivated by applications in wireless multi-hop networks, we consider four fundamental problems under the power minimization criteria: the Min-Power b-Edge-Cover problem (MPb-EC) where the goal is to find a min-power subgraph so that the degree of every node v is at least some given integer b(v), the Min-Power k-node Connected Spanning Subgraph problem (MPk-CSS), Min-Power k-edge Connected Spanning Subgraph problem (MPk-ECSS), and finally the Min-Power k-Edge-Disjoint Paths problem in directed graphs (MPk-EDP). We give an O(log4 n)-approximation algorithm for MPb-EC. This gives an O(log4n)-approximation algorithm for MPk-CSS for most values of k, improving the best previously known O(k)-approximation guarantee. In contrast, we obtain an O(∫n) approximation algorithm for MPk-ECSS, and for its variant in directed graphs (i.e., MPk-EDP), we establish the following inapproximability threshold: MPk-EDP cannot be approximated within O(2log1-ε n) for any fixed ε > 0, unless NP-hard problems can be solved in quasi-polynomial time.