skip to main content
10.5555/1347082.1347210acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
research-article

Approximating connected facility location problems via random facility sampling and core detouring

Published: 20 January 2008 Publication History

Abstract

We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the facilities serving sampled clients in the approximate solution. Via a novel analytical tool, which we term core detouring, we show that this approach significantly improves over the previously best known approximation ratios for several NP-hard network design problems. For example, we reduce the approximation ratio for the connected facility location problem from 8.55 to 4.00 and for the single-sink rent-or-buy problem from 3.55 to 2.92. We show that our connected facility location algorithms can be derandomized at the expense of a slightly worse approximation ratio. The versatility of our framework is demonstrated by devising improved approximation algorithms also for other related problems.

References

[1]
M. Andrews and L. Zhang. The access network design problem. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 40--49, 1998.
[2]
S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501--555, 1998.
[3]
L. Becchetti, J. Könemann, S. Leonardi, and M. Pál. Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 375--384, 2005.
[4]
M. Bern and P. Plassmann. The Steiner problem with edge lengths 1 and 2. Information Processing Letters, 32(4):171--176, 1989.
[5]
N. Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Graduate School of Industrial Administration, Carnegie-Mellon University, 1976.
[6]
S. E. Dreyfus and R. A. Wagner. The Steiner problem in graphs. Networks, 1:195--207, 1971/72.
[7]
L. Fleischer, J. Könemann, S. Leonardi, and G. Schäfer. Simple cost sharing schemes for multicommodity rent-or-buy and stochastic steiner tree. In ACM Symposium on the Theory of Computing (STOC), pages 663--670, 2006.
[8]
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco, 1979.
[9]
A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, and B. Yener. Provisioning a virtual private network: a network design problem for multicommodity flow. In ACM Symposium on the Theory of Computing (STOC), pages 389--398, 2001.
[10]
A. Gupta, A. Kumar, M. Pal, and T. Roughgarden. Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 606--617, 2003.
[11]
A. Gupta, A. Kumar, M. Pal, and T. Roughgarden. Approximation via cost-sharing: simpler and better approximation algorithms for network design. To appear in Journal of the ACM, 2007.
[12]
A. Gupta, A. Kumar, and T. Roughgarden. Simpler and better approximation algorithms for network design. In ACM Symposium on the Theory of Computing (STOC), pages 365--372, 2003.
[13]
A. Gupta, M. Pál, R. Ravi, and A. Sinha. Boosted sampling: approximation algorithms for stochastic optimization. In ACM Symposium on the Theory of Computing (STOC), pages 417--426, 2004.
[14]
A. Gupta, A. Srinivasan, and E. Tardos. Cost-sharing mechanisms for network design. In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 139--150, 2004.
[15]
K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. Vazirani. Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. Journal of the ACM, 50:795--824, 2003.
[16]
K. Jain and V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual scheme and Lagrangian relaxation. Journal of the ACM, 48:274--296, 2001.
[17]
D. R. Karger and M. Minkoff. Building steiner trees with incomplete global knowledge. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 613--623, 2000.
[18]
M. Mahdian, Y. Ye, and J. Zhang. Improved approximation algorithms for metric facility location problems. In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 229--242, 2002.
[19]
P. B. Mirchandani and R. L. Francis. Discrete Location Theory. John Wile and Sons, Inc., New York, 1990.
[20]
R. Motwani and P. Raghavan. Randomized algorithms. Cambridge University Press, Cambridge, first edition, 1995.
[21]
C. Papadimitriou and M. Yannakakis. The traveling salesman problem with distances one and two. Mathematics of Operations Research, 18:1--11, 1993.
[22]
R. Ravi and F. S. Salman. Approximation algorithms for the travelling purchaser problem and its variants in network design. In European Symposium on Algorithms (ESA), pages 29--40, 1999.
[23]
R. Ravi and A. Sinha. Approximation algorithms for problems combining facility location and network design. Operations Research, 54(1):73--81, 2006.
[24]
G. Robins and A. Zelikovsky. Improved Steiner tree approximation in graphs. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 770--779, 2000.
[25]
C. Swamy and A. Kumar. Primal-dual algorithms for connected facility location problems. In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 256--269, 2002.
[26]
C. Swamy and A. Kumar. Primal-dual algorithms for connected facility location problems. Algorithmica, 40(4):245--269, 2004.
[27]
A. van Zuylen and D. Williamson. A simpler and better derandomization of an approximation algorithm for single source rent-or-buy. 2007. To appear in Operations Research Letters.
[28]
J. Vygen. Approximation algorithms for facility location problems (Lecture Notes). Report No. 05950-OR, Research Institute for Discrete Mathematics, University of Bonn, 2005.

Cited By

View all
  • (2022)Optimization of relay placement for scalable virtual private LAN servicesProceedings of the ACM SIGCOMM Workshop on Future of Internet Routing & Addressing10.1145/3527974.3545719(43-49)Online publication date: 22-Aug-2022
  • (2017)An inexact sample average approximation approach for the stochastic connected facility location problemNetworks10.1002/net.2174370:1(19-33)Online publication date: 1-Aug-2017
  • (2016)Approximate robust optimization for the Connected Facility Location problemDiscrete Applied Mathematics10.1016/j.dam.2015.10.011210:C(246-260)Online publication date: 10-Sep-2016
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms
January 2008
1289 pages
  • Program Chair:
  • Shang-Hua Teng

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 20 January 2008

Check for updates

Qualifiers

  • Research-article

Conference

SODA08
Sponsor:
SODA08: 19th ACM-SIAM Symposium on Discrete Algorithms
January 20 - 22, 2008
California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)5
  • Downloads (Last 6 weeks)1
Reflects downloads up to 27 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2022)Optimization of relay placement for scalable virtual private LAN servicesProceedings of the ACM SIGCOMM Workshop on Future of Internet Routing & Addressing10.1145/3527974.3545719(43-49)Online publication date: 22-Aug-2022
  • (2017)An inexact sample average approximation approach for the stochastic connected facility location problemNetworks10.1002/net.2174370:1(19-33)Online publication date: 1-Aug-2017
  • (2016)Approximate robust optimization for the Connected Facility Location problemDiscrete Applied Mathematics10.1016/j.dam.2015.10.011210:C(246-260)Online publication date: 10-Sep-2016
  • (2016)Mathematical models and empirical analysis of a simulated annealing approach for two variants of the static data segment allocation problemNetworks10.1002/net.2167568:1(4-22)Online publication date: 1-Aug-2016
  • (2015)Online network design algorithms via hierarchical decompositionsProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722220(1373-1387)Online publication date: 4-Jan-2015
  • (2011)Contention-aware data caching in wireless multi-hop ad hoc networksJournal of Parallel and Distributed Computing10.1016/j.jpdc.2010.12.00871:4(603-614)Online publication date: 1-Apr-2011
  • (2010)Network design via core detouring for problems without a coreProceedings of the 37th international colloquium conference on Automata, languages and programming10.5555/1880918.1880972(490-502)Online publication date: 6-Jul-2010
  • (2010)Tree embeddings for two-edge-connected network designProceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms10.5555/1873601.1873725(1521-1538)Online publication date: 17-Jan-2010
  • (2010)An improved LP-based approximation for steiner treeProceedings of the forty-second ACM symposium on Theory of computing10.1145/1806689.1806769(583-592)Online publication date: 5-Jun-2010
  • (2009)A constant-factor approximation for stochastic Steiner forestProceedings of the forty-first annual ACM symposium on Theory of computing10.1145/1536414.1536504(659-668)Online publication date: 31-May-2009
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media