Minimum Power Strong Connectivity

Prelegent(ci)

Gruia Calinescu

Afiliacja

Illinois Institute of Technology

Termin

10 maja 2012 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

Given a directed simple graph G=(V,E) and a nonnegative-valued cost function the power of a vertex u in a directed spanning subgraph H is given by the maximum cost of an arcs of H exiting u. The power of H is the sum of the power of its vertices.

Power Assignment seeks to minimize the power of H while H satisfies some connectivity constraint. In this paper, we assume E is bidirected (for every directed edge e in E, the opposite edge exists and has the same cost), while H is required to be strongly connected. This is the original power assignment problem introduce in 1989 and since then the best known approximation ratio is 2 and is achieved by a bidirected minimum spanning tree.  We improve this to 2 - epsilon for a small positive epsilon, by combining techniques from Robins-Zelikovsky (2000), Christofides (1976), and Caragiannis, Flammini, and Moscardelli (2007), together with a novel property on T-joins in certain hypergraphs.

We also present a integer/linear programming formulation, a fast variant of the approximation algorithm, and simulation results comparing new and previously proposed heuristics with the above exact and approximation algorithms, showing tradeoffs between the running time and the quality of the output. This part joint work with Kan Qiao.

---