Dinitz, Michael ;
Kortsarz, Guy ;
Nutov, Zeev
Improved Approximation Algorithm for Steiner kForest with Nearly Uniform Weights
Abstract
In the Steiner kForest problem we are given an edge weighted graph, a collection D of node pairs, and an integer k \leq D. The goal is to find a minimum cost subgraph that connects at least k pairs. The best known ratio for this problem is min{O(sqrt{n}),O(sqrt{k})} [Gupta et al., 2008]. In [Gupta et al., 2008] it is also shown that ratio rho for Steiner kForest implies ratio O(rho log^2 n) for the DialaRide problem: given an edge weighted graph and a set of items with a source and a destination each, find a minimum length tour to move each object from its source to destination, but carrying at most k objects at a time. The only other algorithm known for DialaRide, besides the one resulting from [Gupta et al., 2008], has ratio O(sqrt{n}) [Charikar and Raghavachari, 1998]. We obtain ratio n^{0.448} for Steiner kForest and DialaRide with unit weights, breaking the O(sqrt{n}) ratio barrier for this natural special case. We also show that if the maximum weight of an edge is O(n^{epsilon}), then one can achieve ratio O(n^{(1+epsilon) 0.448}), which is less than sqrt{n} if epsilon is small enough. To prove our main result we consider the following generalization of the Minimum kEdge Subgraph (MkES) problem, which we call MinCost lEdgeProfit Subgraph (MClEPS): Given a graph G=(V,E) with edgeprofits p={p_e: e in E} and nodecosts c={c_v: v in V}, and a lower profit bound l, find a minimum nodecost subgraph of G of edge profit at least l. The MkES problem is a special case of MClEPS with unit node costs and unit edge profits. The currently best known ratio for MkES is n^{32*sqrt{2} + epsilon} (note that 32*sqrt{2} < 0.1716). We extend this ratio to MClEPS for arbitrary node weights and edge profits that are polynomial in n, which may be of independent interest.
BibTeX  Entry
@InProceedings{dinitz_et_al:LIPIcs:2014:4692,
author = {Michael Dinitz and Guy Kortsarz and Zeev Nutov},
title = {{Improved Approximation Algorithm for Steiner kForest with Nearly Uniform Weights}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
pages = {115127},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897743},
ISSN = {18688969},
year = {2014},
volume = {28},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4692},
URN = {urn:nbn:de:0030drops46925},
doi = {10.4230/LIPIcs.APPROXRANDOM.2014.115},
annote = {Keywords: kSteiner Forest; Uniform weights; Densest kSubgraph; Approximation algorithms}
}
04.09.2014
Keywords: 

kSteiner Forest; Uniform weights; Densest kSubgraph; Approximation algorithms 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Issue date: 

2014 
Date of publication: 

04.09.2014 