Skip to main content
Log in

On generalizations of network design problems with degree bounds

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems. In this paper we extend the scope of the iterative relaxation method in two directions: (1) by handling more complex degree constraints in the minimum spanning tree problem (namely laminar crossing spanning tree), and (2) by incorporating ‘degree bounds’ in other combinatorial optimization problems such as matroid intersection and lattice polyhedra. We give new or improved approximation algorithms, hardness results, and integrality gaps for these problems. Our main result is a (1, b + O(log n))-approximation algorithm for the minimum crossing spanning tree (MCST) problem with laminar degree constraints. The laminar MCST problem is a natural generalization of the well-studied bounded-degree MST, and is a special case of general crossing spanning tree. We give an additive Ω(logc m) hardness of approximation for general MCST, even in the absence of costs (c > 0 is a fixed constant, and m is the number of degree constraints). This also leads to a multiplicative Ω(logc m) hardness of approximation for the robust k-median problem (Anthony et al. in Math Oper Res 35:79–101, 2010), improving over the previously known factor 2 hardness. We then consider the crossing contra-polymatroid intersection problem and obtain a (2, 2b + Δ − 1)-approximation algorithm, where Δ is the maximum element frequency. This models for example the degree-bounded spanning-set intersection in two matroids. Finally, we introduce the crossing latticep olyhedron problem, and obtain a (1, b + 2Δ − 1) approximation algorithm under certain condition. This result provides a unified framework and common generalization of various problems studied previously, such as degree bounded matroids.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Anthony B., Goyal V., Gupta A., Nagarajan V.: A plant location guide for the unsure: approximation algorithms for min–max location problems. Math. Oper. Res. 35, 79–101 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  2. Arora S., Babai L., Stern J., Sweedyk Z.: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci. 54(2), 317–331 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  3. Arya V., Garg N., Khandekar R., Meyerson A., Munagala K., Pandit V.: Local search heuristics for k-median and facility location problems. SIAM J. Comput. 33(3), 544–562 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bansal N., Khandekar R., Nagarajan V.: Additive guarantees for degree-bounded directed network design. SIAM J. Comput. 39(4), 1413–1431 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bansal, N., Khandekar, R., Könemann, J., Nagarajan, V., Peis, B.: On generalizations of network design problems with degree bounds. In: Proceedings of Integer Programming Combinatorial Optimization (IPCO), pp. 110–123 (2010)

  6. Bilo,V., Goyal, V., Ravi, R., Singh, M.: On the crossing spanning tree problem, In: Proceedings of Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), pp. 51–60 (2004)

  7. Charikar M., Guha S., Tardos E., Shmoys D.B.: A constant-factor approximation algorithm for the k-median problem. J. Comput. Syst. Sci. 65(1), 129–149 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  8. Charikar, D.B., Newman, A., Nikolov, A.: Tight hardness results for minimizing discrepancy. In: Proceedings of Sympoisum on Discrete Algorithms (SODA), pp. 1607–1614 (2011)

  9. Chaudhuri K., Rao S., Riesenfeld S., Talwar K.: What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs. Algorithmica. 55(1), 157–189 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  10. Chaudhuri K., Rao S., Riesenfeld S., Talwar K.: A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids. Theor. Comput. Sci. 410(44), 4489–4503 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  11. Chazelle B.: The Discrepancy Method: Randomness and Complexity. Cambridge University Press, Cambridge (2000)

    Book  Google Scholar 

  12. Chekuri, C., Vondrák, J., Zenklusen, R.: Dependent randomized rounding via Exchange Properties of Combinatorial Structures. In: Proceedings of Foundations of Computer Science (FOCS), 575–584 (2010)

  13. Faigle, U., Peis, B.: Two-phase greedy algorithms for some classes of combinatorial linear programs. In: Proceedings of Symposium on Discrete Algorithms (SODA), pp. 161–166 (2008)

  14. Frank A.: Increasing the rooted connectivity of a digraph by one. Math. Program. 84, 565–576 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  15. Goemans, M.X.: Minimum bounded-degree spanning trees. In: Proceedings of Foundations of Computer Scienc (FOCS), pp. 273–282 (2006)

  16. Grandoni, F., Ravi, R., Singh, M.: Iterative rounding for multiobjective optimization problems. In: Proceedings of European Symposium on Algorithms (ESA), pp. 95–106 (2009)

  17. Hoffman, A., Schwartz, D.E.: On lattice polyhedra. In: Hajnal A., Sos V.T. (eds.) Proceedings of Fifth Hungarian Combinatorial Coll., North-Holland, Amsterdam, pp. 593–598 (1978)

  18. Jain K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica. 21, 39–60 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  19. Király, T., Lau, L.C., Singh, M.: Degree bounded matroids and submodular flows. In: Proceedings of Integer Programming and Combinatorial Optimization (IPCO), pp. 259–272 (2008)

  20. Könemann J., Ravi R.: A matter of degree: improved approximation algorithms for degree bounded minimum spanning trees. SIAM J. Comput. 31, 1783–1793 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  21. Könemann J., Ravi R.: Primal-dual meets local search: approximating MSTs with nonuniform degree bounds. SIAM J. Comput. 34(3), 763–773 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  22. Korte B., Vygen J.: Combinatorial Optimization, 4th edn. Springer, New York (2008)

    Google Scholar 

  23. Lau L.C., Naor J., Salavatipour M. R., Singh M.: Survivable network design with degree or order constraints. SIAM J. Comput. 39(3), 1062–1087 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  24. Lau, L.C., Singh, M.: Additive approximation for bounded degree survivable network design. In: Proceedings of Symposium on Theory of Computing (STOC), pp. 759–768 (2008)

  25. Matuschke, J., Peis, B.: Lattices and maximum flow algorithms in planar graphs. In: Proceedings of Workshop on Graph Theoretic Concepts in Computer Science (WG), pp. 324–335 (2010)

  26. McCormick, S. T., Peis, B.: A Primal-dual algorithm for weighted abstract cut packing. In: Proceedings of Integer Programming and Combinatorial Optimization (IPCO), pp. 324–335 (2011)

  27. Nutov, Z.: Approximating directed weighted-degree constrained networks. In: Proceedings of Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), pp. 219–232 (2008)

  28. Ravi, R. Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Hunt, H.B.: Many birds with one stone: multi-objective approximation algorithms. In: Proceedings of Symposium on Theory of Computing (STOC), pp. 438–447 (1993)

  29. Ravi, R., Singh, M.: Delegate and conquer: an LP-based approximation algorithm for minimum degree MSTs. In: Proceedings of International Colloquium on Automata, Languages and Programming (ICALP), pp. 169–180 (2006)

  30. Raz R.: A parallel repetition theorem. SIAM J. Comput. 27(3), 763–803 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  31. Schrijver A.: Combinatorial Optimization. Springer, New York (2003)

    MATH  Google Scholar 

  32. Singh, M.: Personal Communication (2008)

  33. Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one of optimal. In: Proceedings of Symposium on Theory of Computing (STOC), pp. 661–670 (2007)

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Viswanath Nagarajan.

Additional information

A preliminary version of this paper appeared as [5].

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bansal, N., Khandekar, R., Könemann, J. et al. On generalizations of network design problems with degree bounds. Math. Program. 141, 479–506 (2013). https://doi.org/10.1007/s10107-012-0537-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-012-0537-8

Mathematics Subject Classification

Navigation