Prize-collecting Steiner network problems

Mohammad Taghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Zeev Nutov

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

4 Citations (Scopus)

Abstract

In the Steiner Network problem we are given a graph G with edge-costs and connectivity requirements ruv between node pairs u,v. The goal is to find a minimum-cost subgraph H of G that contains ruv edge-disjoint paths for all u,v ∈ V. In Prize-Collecting Steiner Network problems we do not need to satisfy all requirements, but are given a penalty function for violating the connectivity requirements, and the goal is to find a subgraph H that minimizes the cost plus the penalty. The case when ruv ∈ {0,1} is the classic Prize-Collecting Steiner Forest problem. In this paper we present a novel linear programming relaxation for the Prize-Collecting Steiner Network problem, and by rounding it, obtain the first constant-factor approximation algorithm for submodular and monotone non-decreasing penalty functions. In particular, our setting includes all-or-nothing penalty functions, which charge the penalty even if the connectivity requirement is slightly violated; this resolves an open question posed in [SSW07]. We further generalize our results for element-connectivity and node-connectivity.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 14th International Conference, IPCO 2010, Proceedings
Pages71-84
Number of pages14
DOIs
StatePublished - Jul 14 2010
Event14th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2010 - Lausanne, China
Duration: Jun 9 2010Jun 11 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6080 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other14th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2010
CountryChina
CityLausanne
Period6/9/106/11/10

Fingerprint

Steiner network
Connectivity
Penalty Function
Requirements
Costs
Approximation algorithms
Penalty
Subgraph
Linear programming
Edge-disjoint Paths
Linear Programming Relaxation
Rounding
Vertex of a graph
Approximation Algorithms
Resolve
Monotone
Charge
Minimise
Generalise
Graph in graph theory

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Hajiaghayi, M. T., Khandekar, R., Kortsarz, G., & Nutov, Z. (2010). Prize-collecting Steiner network problems. In Integer Programming and Combinatorial Optimization - 14th International Conference, IPCO 2010, Proceedings (pp. 71-84). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6080 LNCS). https://doi.org/10.1007/978-3-642-13036-6_6
Hajiaghayi, Mohammad Taghi ; Khandekar, Rohit ; Kortsarz, Guy ; Nutov, Zeev. / Prize-collecting Steiner network problems. Integer Programming and Combinatorial Optimization - 14th International Conference, IPCO 2010, Proceedings. 2010. pp. 71-84 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{d0b7948698314cb2b547bacb183f5d4b,
title = "Prize-collecting Steiner network problems",
abstract = "In the Steiner Network problem we are given a graph G with edge-costs and connectivity requirements ruv between node pairs u,v. The goal is to find a minimum-cost subgraph H of G that contains ruv edge-disjoint paths for all u,v ∈ V. In Prize-Collecting Steiner Network problems we do not need to satisfy all requirements, but are given a penalty function for violating the connectivity requirements, and the goal is to find a subgraph H that minimizes the cost plus the penalty. The case when ruv ∈ {0,1} is the classic Prize-Collecting Steiner Forest problem. In this paper we present a novel linear programming relaxation for the Prize-Collecting Steiner Network problem, and by rounding it, obtain the first constant-factor approximation algorithm for submodular and monotone non-decreasing penalty functions. In particular, our setting includes all-or-nothing penalty functions, which charge the penalty even if the connectivity requirement is slightly violated; this resolves an open question posed in [SSW07]. We further generalize our results for element-connectivity and node-connectivity.",
author = "Hajiaghayi, {Mohammad Taghi} and Rohit Khandekar and Guy Kortsarz and Zeev Nutov",
year = "2010",
month = "7",
day = "14",
doi = "10.1007/978-3-642-13036-6_6",
language = "English (US)",
isbn = "3642130356",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "71--84",
booktitle = "Integer Programming and Combinatorial Optimization - 14th International Conference, IPCO 2010, Proceedings",

}

Hajiaghayi, MT, Khandekar, R, Kortsarz, G & Nutov, Z 2010, Prize-collecting Steiner network problems. in Integer Programming and Combinatorial Optimization - 14th International Conference, IPCO 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6080 LNCS, pp. 71-84, 14th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2010, Lausanne, China, 6/9/10. https://doi.org/10.1007/978-3-642-13036-6_6

Prize-collecting Steiner network problems. / Hajiaghayi, Mohammad Taghi; Khandekar, Rohit; Kortsarz, Guy; Nutov, Zeev.

Integer Programming and Combinatorial Optimization - 14th International Conference, IPCO 2010, Proceedings. 2010. p. 71-84 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6080 LNCS).

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

TY - GEN

T1 - Prize-collecting Steiner network problems

AU - Hajiaghayi, Mohammad Taghi

AU - Khandekar, Rohit

AU - Kortsarz, Guy

AU - Nutov, Zeev

PY - 2010/7/14

Y1 - 2010/7/14

N2 - In the Steiner Network problem we are given a graph G with edge-costs and connectivity requirements ruv between node pairs u,v. The goal is to find a minimum-cost subgraph H of G that contains ruv edge-disjoint paths for all u,v ∈ V. In Prize-Collecting Steiner Network problems we do not need to satisfy all requirements, but are given a penalty function for violating the connectivity requirements, and the goal is to find a subgraph H that minimizes the cost plus the penalty. The case when ruv ∈ {0,1} is the classic Prize-Collecting Steiner Forest problem. In this paper we present a novel linear programming relaxation for the Prize-Collecting Steiner Network problem, and by rounding it, obtain the first constant-factor approximation algorithm for submodular and monotone non-decreasing penalty functions. In particular, our setting includes all-or-nothing penalty functions, which charge the penalty even if the connectivity requirement is slightly violated; this resolves an open question posed in [SSW07]. We further generalize our results for element-connectivity and node-connectivity.

AB - In the Steiner Network problem we are given a graph G with edge-costs and connectivity requirements ruv between node pairs u,v. The goal is to find a minimum-cost subgraph H of G that contains ruv edge-disjoint paths for all u,v ∈ V. In Prize-Collecting Steiner Network problems we do not need to satisfy all requirements, but are given a penalty function for violating the connectivity requirements, and the goal is to find a subgraph H that minimizes the cost plus the penalty. The case when ruv ∈ {0,1} is the classic Prize-Collecting Steiner Forest problem. In this paper we present a novel linear programming relaxation for the Prize-Collecting Steiner Network problem, and by rounding it, obtain the first constant-factor approximation algorithm for submodular and monotone non-decreasing penalty functions. In particular, our setting includes all-or-nothing penalty functions, which charge the penalty even if the connectivity requirement is slightly violated; this resolves an open question posed in [SSW07]. We further generalize our results for element-connectivity and node-connectivity.

UR - http://www.scopus.com/inward/record.url?scp=77954393830&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77954393830&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-13036-6_6

DO - 10.1007/978-3-642-13036-6_6

M3 - Conference contribution

AN - SCOPUS:77954393830

SN - 3642130356

SN - 9783642130359

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 71

EP - 84

BT - Integer Programming and Combinatorial Optimization - 14th International Conference, IPCO 2010, Proceedings

ER -

Hajiaghayi MT, Khandekar R, Kortsarz G, Nutov Z. Prize-collecting Steiner network problems. In Integer Programming and Combinatorial Optimization - 14th International Conference, IPCO 2010, Proceedings. 2010. p. 71-84. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-13036-6_6