License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-24975
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2497/
Go to the corresponding Portal


Kortsarz, Guy ; Nutov, Zeev

Approximating minimum cost connectivity problems

pdf-format:
Document 1.pdf (347 KB)


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:DSP:2010:2497,
  author =	{Guy Kortsarz and Zeev Nutov},
  title =	{Approximating minimum cost connectivity problems},
  booktitle =	{Parameterized complexity and approximation algorithms},
  year =	{2010},
  editor =	{Erik D. Demaine and MohammadTaghi Hajiaghayi and D{\'a}niel Marx},
  number =	{09511},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2497},
  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 Published by LZI