SCIENCE@home

Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights

M. Dinitz,G. Kortsarz,Zeev Nutov

Published 2017 in International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

ABSTRACT

In the Steiner k-Forest problem, we are given an edge weighted graph, a collection D of node pairs, and an integer k ⩽ |D|. The goal is to find a min-weight subgraph that connects at least k pairs. The best known ratio for this problem is min {O(√n), O(√k)} [Gupta et al. 2010]. In Gupta et al. [2010], it is also shown that ratio ρ for Steiner k-Forest implies ratio O(ρ · log 2n) for the related Dial-a-Ride problem. The only other algorithm known for Dial-a-Ride, besides the one resulting from Gupta et al. [2010], has ratio O(√n) [Charikar and Raghavachari 1998]. We obtain approximation ratio n0.448 for Steiner k-Forest and Dial-a-Ride with unit weights, breaking the O(√n) approximation barrier for this natural case. We also show that if the maximum edge-weight is O(nε), then one can achieve ratio O(n(1 + ε) · 0.448), which is less than √n if ε is small enough. The improvement for Dial-a-Ride is the first progress for this problem in 15 years. To prove our main result, we consider the following generalization of the Minimum k-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 + ε [Chlamtac et al. 2012]. We extend this ratio to MCℓ-EPS for general node costs and profits bounded by a polynomial in n, which may be of independent interest.

PUBLICATION RECORD

  • Publication year

    2017

  • Venue

    International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

  • Publication date

    2017-07-13

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    DOI 10.1145/3077581
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-17 of 17 references · Page 1 of 1

CITED BY

Showing 1-10 of 10 citing papers · Page 1 of 1