### Abstract

In the Steiner Network problem we are given a graph G with edge-costs and connectivity requirements r_{uv} between node pairs u,v. The goal is to find a minimum-cost subgraph H of G that contains r_{uv} 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 r_{uv} ∈ {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 language | English (US) |
---|---|

Title of host publication | Integer Programming and Combinatorial Optimization - 14th International Conference, IPCO 2010, Proceedings |

Pages | 71-84 |

Number of pages | 14 |

DOIs | |

State | Published - Jul 14 2010 |

Event | 14th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2010 - Lausanne, China Duration: Jun 9 2010 → Jun 11 2010 |

### Publication series

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

Volume | 6080 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 14th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2010 |
---|---|

Country | China |

City | Lausanne |

Period | 6/9/10 → 6/11/10 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*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