Prize-collecting steiner network problems
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Dec 01, 2012
- Source ID
- 10.1145/2390176.2390178
Entities
People
- Guy Kortsarz
- MohammadTaghi Hajiaghayi
- Rohit Khandekar
- Zeev Nutov
Organizations
- Air Force Office of Scientific Research
- Defense Advanced Research Projects Agency
- Division of Computing and Communication Foundations
- International Business Machines Corporation (Armonk, NY)
- National Science Foundation
- Office of Naval Research
- Open University of Israel
- Rutgers University
- University of Maryland