Name
Title | ||
|---|---|---|
Approximation algorithms for prize collecting forest problems with submodular penalty functions |
Abstract | ||
|---|---|---|
In this paper, we study the prize-collecting version of constrained forest problems with an arbitrary 0-1 connectivity requirement function and a submodular penalty function. Our framework generalizes the Prize Collecting Generalized Steiner Tree framework of Hajiaghayi and Jain [HJ06] to incorporate more general connectivity requirements and penalty functions. We generalize their primal-dual algorithm using submodular function minimization to give a 3-approximation algorithm, and devise an LP rounding algorithm with a performance guarantee of 2.54. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1145/1283383.1283520 | SODA |
Keywords | Field | DocType |
independent set,penalty function,steiner tree | Approximation algorithm,Discrete mathematics,Mathematical optimization,Combinatorics,Computer science,Steiner tree problem,Performance guarantee,Submodular set function,Rounding,Submodular function minimization,Independent set,Penalty method | Conference |
ISBN | Citations | PageRank |
978-0-89871-624-5 | 17 | 0.75 |
References | Authors | |
12 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yogeshwer Sharma | 1 | 161 | 9.67 |
| Chaitanya Swamy | 2 | 1139 | 82.64 |
| David P. Williamson | 3 | 3564 | 413.34 |