Name
Title | ||
|---|---|---|
Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements |
Abstract | ||
|---|---|---|
In this paper, we introduce the study of prize-collecting network design problems having general connectivity requirements. Prior work considered only 0-1 or very limited connectivity requirements. We introduce general connectivity requirements in the prize-collecting generalized Steiner tree framework of Hajiaghayi and Jain [9], and consider penalty functions linear in the violation of the connectivity requirements. Using Jain’s iterated rounding algorithm [11] as a black box, and ideas from Goemans [7] and Levi, Lodi, Sviridenko [14], we give a 2.54-factor approximation algorithm for the problem. We also generalize the 0-1 requirements of PCF problem introduced by Sharma, Swamy, and Williamson [15] to include general connectivity requirements. Here we assume that the monotone submodular penalty function of Sharma et al. is generalized to a multiset function that can be decomposed into functions in the same form as that of Sharma et al. Using ideas from Goemans and Berstimas [6], we give an (αlogK)-approximation algorithm for the resulting problem, where K is the maximum connectivity requirement, and α= 2.54. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-93980-1_14 | WAOA |
Keywords | Field | DocType |
general connectivity requirements,general connectivity requirement,maximum connectivity requirement,rounding algorithm,resulting problem,prize-collecting network design problems,approximation algorithms,monotone submodular penalty function,approximation algorithm,prize-collecting network design problem,limited connectivity requirement,connectivity requirement,pcf problem,steiner tree,network design,penalty function | Discrete mathematics,Approximation algorithm,Combinatorics,Mathematical optimization,Network planning and design,Computer science,Multiset,Steiner tree problem,Submodular set function,Travelling salesman problem,Monotone polygon,Penalty method | Conference |
Volume | ISSN | Citations |
5426 | 0302-9743 | 2 |
PageRank | References | Authors |
0.38 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chandrashekhar Nagarajan | 1 | 151 | 7.62 |
| Yogeshwer Sharma | 2 | 161 | 9.67 |
| David P. Williamson | 3 | 3564 | 413.34 |