Exponential Lower Bounds on the Complexity of a Class of Dynamic Programs for Combinatorial Optimization Problems | Algorithmica Skip to main content
Springer Nature Link
Log in

Exponential Lower Bounds on the Complexity of a Class of Dynamic Programs for Combinatorial Optimization Problems

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We prove exponential lower bounds on the running time of Dynamic Programs (DP) of a certain class for some Combinatorial Optimization Problems. The class of DPs for which we derive the lower bounds is general enough to include well-known DPs for Combinatorial Optimization Problems, such as the ones developed for the Shortest Path Problem, the Knapsack Problem, or the Traveling Salesman Problem. The problems analyzed include the Traveling Salesman Problem (TSP), the Bipartite Matching Problem (BMP), the Min and the Max Cut Problems (MCP), the Min Partition Problem (MPP), and the Min Cost Test Collection Problem (MCTCP).

We draw a connection between Dynamic Programs and algorithms for polynomial evaluation. We then derive and use complexity results of polynomial evaluation to prove similar results for Dynamic Programs for the TSP or the BMP. We define a reduction between problems that allows us to generalize these bounds to problems for which either the TSP or the BMP transforms to. Moreover, we show that some standard transformations between problems are of this kind. In this fashion, we extend the lower bounds to other Combinatorial Optimization Problems.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs, Prentice Hall (1993)

    MATH  Google Scholar 

  2. Alekhnovich, M., Borodin, A., Buresh-Oppenheim, J., Impagliazzo, R., Magen, A., Pitassi, T.: Toward a model for backtracking and dynamic programming. In: Twentieth Annual IEEE Conference on Computational Complexity, pp. 308–322 (2005)

    Google Scholar 

  3. Balas, E., Simonetti, N.: Linear time dynamic-programming algorithms for new classes of restricted TSPs: a computational study. INFORMS J. Comput. 13(1), 56–75 (2001)

    Article  MathSciNet  Google Scholar 

  4. Bertsekas, D.: Dynamic Programming and Optimal Control. Athena Scientific, Belmont (2000)

    Google Scholar 

  5. Bompadre, A.: Three essays on sequencing and routing problems. PhD thesis, Massachusetts Institute of Technology, USA (2005)

  6. Bompadre, A., Orlin, J.B.: Using grammars to generate very large scale neighborhoods for the traveling salesman problem and other sequencing problems. In: Eleventh International Conference on Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 3509, pp. 437–451. Springer, Berlin (2005)

    Chapter  Google Scholar 

  7. Bondel, V.D., Tsitsiklis, J.N.: A survey of computational complexity results in systems and control. Automatica 36, 1249–1274 (2000)

    Article  Google Scholar 

  8. Borodin, A., Nielsen, M.N., Rackoff, C.: (Incremental) priority algorithms. Algorithmica 37(4), 295–326 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  9. Buresh-Oppenheim, J., Davis, S., Impagliazzo, R.: A stronger model of dynamic programming algorithm. Algorithmica (2010). doi:10.1007/s00453-009-9385-1

    Google Scholar 

  10. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2002)

    Google Scholar 

  11. Deı̌neko, V.G., Woeginger, G.J.: A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem. Math. Program., Ser. A 87(3), 519–542 (2000)

    Article  Google Scholar 

  12. Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 1, 3rd edn. Wiley, New York (1968)

    MATH  Google Scholar 

  13. Garey, M., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)

    MATH  Google Scholar 

  14. Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. In: Proceedings of the 1961 16th ACM National Meeting, pp. 71.201–71.204. ACM Press, New York (1961)

    Chapter  Google Scholar 

  15. Jeroslow, R.: Trivial integer programs unsolvable by branch-and-bound. Math. Program. 6(1), 105–109 (1974)

    Article  MATH  Google Scholar 

  16. Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM 51(4), 671–697 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  17. Jerrum, M., Snir, M.: Some exact complexity results for straight-line computations over semirings. J. ACM 29(3), 874–897 (1982)

    MATH  MathSciNet  Google Scholar 

  18. Klyaus, P.S.: The structure of the optimal solution of certain classes of traveling salesman problems. In: Vestsi Akad. Nauk BSSR, pp. 95–98. Phys. Math. Sci., Minsk (1976) (in Russian)

    Google Scholar 

  19. Potts, C.N., van de Velde, S.L.: Dynasearch—iterative local improvement by dynamic programming. Part I. The traveling salesman problem. Preprint, Faculty of Mathematical Studies, University of Southampton, UK (1995)

  20. Pudlák, P.: Lower bounds for resolution and cutting plane proofs and monotone computations. J. Symb. Log. 62(3), 981–998 (1997)

    Article  MATH  Google Scholar 

  21. Rust, J.: Using randomization to break the curse of dimensionality. Econometrica 65(3), 487–516 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  22. Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8(2), 189–201 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  23. von zur Gathen, J.: Parallel Linear Algebra. Morgan Kaufmann, Los Altas (1993)

    Google Scholar 

  24. Whitt, W.: Approximations of dynamic programs, I. Math. Oper. Res. 3, 231–243 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  25. Whitt, W.: Approximations of dynamic programs, II. Math. Oper. Res. 4, 179–185 (1978)

    Article  MathSciNet  Google Scholar 

  26. Woeginger, G.J.: When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? INFORMS J. Comput. 12(1), 57–74 (2000)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Graduate Aerospace Laboratories, California Institute of Technology, Pasadena, CA, 91125, USA

    Agustín Bompadre

Authors
  1. Agustín Bompadre
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Agustín Bompadre.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bompadre, A. Exponential Lower Bounds on the Complexity of a Class of Dynamic Programs for Combinatorial Optimization Problems. Algorithmica 62, 659–700 (2012). https://doi.org/10.1007/s00453-010-9475-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-010-9475-0

Keywords

Search

Navigation