Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Kortsarz, Guy; Nutov, Zeev License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-24975


Approximating minimum cost connectivity problems



We survey approximation algorithms of connectivity problems.
The survey presented describing various techniques. In the talk the following techniques and results are presented.

1)Outconnectivity: Its well known that there exists a polynomial time algorithm to solve the problems of finding an edge k-outconnected from r subgraph [EDMONDS] and a vertex k-outconnectivity subgraph from r [Frank-Tardos] .
We show how to use this to obtain a ratio 2 approximation for the min cost edge k-connectivity

2)The critical cycle theorem of Mader: We state a fundamental theorem of Mader and use it to provide a 1+(k-1)/n ratio approximation for the min cost vertex k-connected subgraph, in the metric case.
We also show results for the min power vertex k-connected problem using this lemma.
We show that the min power is equivalent to the min-cost case with respect to approximation.

3)Laminarity and uncrossing: We use the well known laminarity of a BFS solution and show a simple new proof due to Ravi et al for Jain's 2 approximation for Steiner network.

BibTeX - Entry

  author =	{Kortsarz, Guy and Nutov, Zeev},
  title =	{{Approximating minimum cost connectivity problems}},
  booktitle =	{Parameterized complexity and approximation algorithms},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9511},
  editor =	{Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'{a}niel Marx},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-24975},
  doi =		{10.4230/DagSemProc.09511.4},
  annote =	{Keywords: Connectivity, laminar, uncrossing, Mader's Theorem, power problems}

Keywords: Connectivity, laminar, uncrossing, Mader's Theorem, power problems
Seminar: 09511 - Parameterized complexity and approximation algorithms
Issue date: 2010
Date of publication: 02.03.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI