skip to main content
10.5555/1283383.1283520acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Approximation algorithms for prize collecting forest problems with submodular penalty functions

Published: 07 January 2007 Publication History

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.

References

[1]
{Bal89} Egon Balas. The prize collecting traveling salesman problem. Networks, 19:621--636, 1989.
[2]
{BGSLW93} Daniel Bienstock, Michel X. Goemans, David Simchi-Levi, and David P. Williamson. A note on the prize collecting traveling salesman problem. Math. Programming, 59:413--420, 1993.
[3]
{Edm70} Jack Edmonds. Submodular functions, matroids, and certain polyhedra. In R. Guy, H. Hanani, N. Sauer, and J. Schönheim, editors, Combinatorial Structures and Their Applications, pages 68--87, 1970.
[4]
{GLS88} M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization. Springer Verlag, 1988.
[5]
{Goe98} Michel Goemans, 1998. Personal communication.
[6]
{GW95} Michel X. Goemans and David P. Williamson. A general approximation technique for constrained forest problems. SIAM J. Comput., 24(2):296--317, 1995.
[7]
{HJ06} M. T. Hajiaghayi and K. Jain. The prize-collecting generalized Steiner tree problem via a new approach of primal-dual schema. In SODA, pages 631--640, 2006.
[8]
{HST05} Ara Hayrapetyan, Chaitanya Swamy, and Éva Tardos. Network design for information networks. In SODA, pages 933--942, 2005.
[9]
{IFF01} S. Iwata, L. Fleischer, and S. Fujishige. A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM, 48(4):761--777, 2001.
[10]
{Jai01} Kamal Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1):39--60, 2001.
[11]
{JMP00} David S. Johnson, Maria Minkoff, and Steven Phillips. The prize collecting Steiner tree problem: theory and practice. In SODA, pages 760--769, 2000.
[12]
{KN06} G. Kortsarz and Z. Nutov. Approximating minimum cost connectivity problems. In T. Gonzales, editor, Handbook of Approximation Algorithms and Metaheuristics. CRC Press, 2006.
[13]
{Sch00} A. Schrijver. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Comb. Theory, Ser. B, 80(2):346--355, 2000.

Cited By

View all
  1. Approximation algorithms for prize collecting forest problems with submodular penalty functions

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms
      January 2007
      1322 pages
      ISBN:9780898716245
      • Conference Chair:
      • Harold Gabow

      Sponsors

      Publisher

      Society for Industrial and Applied Mathematics

      United States

      Publication History

      Published: 07 January 2007

      Check for updates

      Qualifiers

      • Article

      Acceptance Rates

      SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;
      Overall Acceptance Rate 411 of 1,322 submissions, 31%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

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

      Other Metrics

      Citations

      Cited By

      View all
      • (2020)Hunting multiple bumps in graphsProceedings of the VLDB Endowment10.14778/3377369.337737513:5(656-669)Online publication date: 1-Jan-2020
      • (2018)Online Constrained Forest and Prize-Collecting Network DesignAlgorithmica10.1007/s00453-017-0391-480:11(3335-3364)Online publication date: 1-Nov-2018
      • (2014)Node-Weighted Steiner Tree and Group Steiner Tree in Planar GraphsACM Transactions on Algorithms10.1145/260107010:3(1-20)Online publication date: 1-Jul-2014
      • (2012)Prize-collecting steiner network problemsACM Transactions on Algorithms10.1145/2390176.23901789:1(1-13)Online publication date: 26-Dec-2012
      • (2011)Prize-collecting Steiner problems on planar graphsProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133115(1028-1049)Online publication date: 23-Jan-2011
      • (2010)Approximability of combinatorial problems with multi-agent submodular cost functionsACM SIGecom Exchanges10.1145/1980534.19805429:1(1-4)Online publication date: 1-Jun-2010
      • (2010)Prize-Collecting steiner network problemsProceedings of the 14th international conference on Integer Programming and Combinatorial Optimization10.1007/978-3-642-13036-6_6(71-84)Online publication date: 9-Jun-2010
      • (2010)Prize-collecting steiner networks via iterative roundingProceedings of the 9th Latin American conference on Theoretical Informatics10.1007/978-3-642-12200-2_45(515-526)Online publication date: 19-Apr-2010
      • (2010)Euclidean prize-collecting steiner forestProceedings of the 9th Latin American conference on Theoretical Informatics10.1007/978-3-642-12200-2_44(503-514)Online publication date: 19-Apr-2010
      • (2009)Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity RequirementsApproximation and Online Algorithms10.1007/978-3-540-93980-1_14(174-187)Online publication date: 13-Jan-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