Kortsarz, Guy ;
Nutov, Zeev
Approximating minimum cost connectivity problems
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 koutconnected from r subgraph [EDMONDS] and a vertex koutconnectivity subgraph from r [FrankTardos] .
We show how to use this to obtain a ratio 2 approximation for the min cost edge kconnectivity
problem.
2)The critical cycle theorem of Mader: We state a fundamental theorem of Mader and use it to provide a 1+(k1)/n ratio approximation for the min cost vertex kconnected subgraph, in the metric case.
We also show results for the min power vertex kconnected problem using this lemma.
We show that the min power is equivalent to the mincost 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 = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum 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}
}
2010
Keywords: 

Connectivity, laminar, uncrossing, Mader's Theorem, power problems 
Seminar: 

09511  Parameterized complexity and approximation algorithms

Issue date: 

2010 
Date of publication: 

2010 