Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published April 2012 | public
Journal Article

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

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.

Additional Information

© 2010 Springer Science+Business Media, LLC. Received: 5 April 2009; Accepted: 21 November 2010; Published online: 1 December 2010. The author would like to thank the anonymous referees and Prof. Allan Borodin for suggesting many improvements to the paper during the review process. In particular, one referee suggested the definition of COPs as shortest paths on DAGs, and simplified the proof of Proposition 4. The author would also like to thank Moshe Dror, Mike Wagner, and Malena Español for helpful comments on an earlier version of the paper.

Additional details

Created:
August 22, 2023
Modified:
October 24, 2023