A Caltech Library Service

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

Bompadre, Agustín (2012) Exponential Lower Bounds on the Complexity of a Class of Dynamic Programs for Combinatorial Optimization Problems. Algorithmica, 62 (3-4). pp. 659-700. ISSN 0178-4617. doi:10.1007/s00453-010-9475-0.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
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.
Subject Keywords:Dynamic programming; Combinatorial optimization problems; Monotone arithmetic circuits
Issue or Number:3-4
Record Number:CaltechAUTHORS:20120214-100835265
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:29273
Deposited By: Tony Diaz
Deposited On:21 Mar 2012 17:16
Last Modified:09 Nov 2021 17:05

Repository Staff Only: item control page