License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09511.4
URN: urn:nbn:de:0030-drops-24975
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2497/
Go to the corresponding Portal

Kortsarz, Guy ; Nutov, Zeev

Approximating minimum cost connectivity problems

pdf-format:
09511.KortsarzGuy.Paper.2497.pdf (0.3 MB)

Abstract

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
problem.

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

@InProceedings{kortsarz_et_al:DagSemProc.09511.4,
  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 =		{https://drops.dagstuhl.de/opus/volltexte/2010/2497},
  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
Collection: 09511 - Parameterized complexity and approximation algorithms
Issue Date: 2010
Date of publication: 02.03.2010

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