Improved approximation algorithm for steiner κ-Forest with nearly uniform weights

Michael Dinitz, Guy Kortsarz, Zeev Nutov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

In the Steiner κ-Forest problem we are given an edge weighted graph, a collection D of node pairs, and an integer κ ≤ |D|. The goal is to find a minimum cost subgraph that connects at least κ pairs. The best known ratio for this problem is min{O( √n),O(√κ)} [8]. In [8] it is also shown that ratio ρ for Steiner κ-Forest implies ratio O(ρ · log2 n) for the Dial-a-Ride 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 κ objects at a time. The only other algorithm known for Dial-a-Ride, besides the one resulting from [8], has ratio O( √n) [4]. We obtain ratio n0.448 for Steiner κ-Forest and Dial-a-Ride with unit weights, breaking the O(√n) ratio barrier for this natural special case. We also show that if the maximum weight of an edge is O(nε), then one can achieve ratio O(n(1+ε)·0.448), which is less than √n if ε is small enough. To prove our main result we consider the following generalization of the Minimum κ-Edge Subgraph (Mk-ES) problem, which we call Min-Cost ℓ-Edge-Profit Subgraph (MCℓ-EPS): Given a graph G = (V,E) with edge-profits p = {pe : e ∈ E} and node-costs c = {cv : v ∈ V }, and a lower profit bound ℓ, find a minimum node-cost subgraph of G of edge profit at least ℓ. The Mk-ES problem is a special case of MCℓ-EPS with unit node costs and unit edge profits. The currently best known ratio for Mk-ES is n3-2√2+ε (note that 3-2√2 < 0.1716) [5]. We extend this ratio to MCℓ-EPS for arbitrary node weights and edge profits that are polynomial in n, which may be of independent interest.

Original languageEnglish (US)
Title of host publicationLeibniz International Proceedings in Informatics, LIPIcs
EditorsKlaus Jansen, Cristopher Moore, Nikhil R. Devanur, Jose D. P. Rolim
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages115-127
Number of pages13
ISBN (Electronic)9783939897743
DOIs
StatePublished - Sep 1 2014
Event17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014 - Barcelona, Spain
Duration: Sep 4 2014Sep 6 2014

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume28
ISSN (Print)1868-8969

Other

Other17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014
Country/TerritorySpain
CityBarcelona
Period9/4/149/6/14

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Approximation algorithms
  • Densest κ-Subgraph
  • Uniform weights
  • κ-Steiner Forest

Fingerprint

Dive into the research topics of 'Improved approximation algorithm for steiner κ-Forest with nearly uniform weights'. Together they form a unique fingerprint.

Cite this