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

被引：0
|
作者：
Agustín Bompadre
机构：
[1] California Institute of Technology,Graduate Aerospace Laboratories
来源：
Algorithmica | 2012年 / 62卷
关键词：
Dynamic programming; Combinatorial optimization problems; Monotone arithmetic circuits;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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).
引用
收藏
页码：659 / 700
页数：41
相关论文
共 50 条
  • [1] Exponential Lower Bounds on the Complexity of a Class of Dynamic Programs for Combinatorial Optimization Problems
    Bompadre, Agustin
    ALGORITHMICA, 2012, 62 (3-4) : 659 - 700
  • [2] BOUNDS OF THE COMPLEXITY OF COMBINATORIAL OPTIMIZATION PROBLEMS IN ONE CLASS OF ALGORITHMS
    BONDARENKO, VA
    DOKLADY AKADEMII NAUK, 1993, 328 (01) : 22 - 24
  • [3] Exponential Lower Bounds for Polytopes in Combinatorial Optimization
    Fiorini, Samuel
    Massar, Serge
    Pokutta, Sebastian
    Tiwary, Hans Raj
    De Wolf, Ronald
    JOURNAL OF THE ACM, 2015, 62 (02)
  • [4] On the complexity of a class of combinatorial optimization problems with uncertainty
    Averbakh, I
    MATHEMATICAL PROGRAMMING, 2001, 90 (02) : 263 - 272
  • [5] On the complexity of a class of combinatorial optimization problems with uncertainty
    Igor Averbakh
    Mathematical Programming, 2001, 90 : 263 - 272
  • [6] Algorithms and Complexity for a Class of Combinatorial Optimization Problems with Labelling
    Yang, Zishen
    Wang, Wei
    Shi, Majun
    JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2021, 188 (03) : 673 - 695
  • [7] Algorithms and Complexity for a Class of Combinatorial Optimization Problems with Labelling
    Zishen Yang
    Wei Wang
    Majun Shi
    Journal of Optimization Theory and Applications, 2021, 188 : 673 - 695
  • [8] On the Complexity of Nonoverlapping Multivariate Marginal Bounds for Probabilistic Combinatorial Optimization Problems
    Doan, Xuan Vinh
    Natarajan, Karthik
    OPERATIONS RESEARCH, 2012, 60 (01) : 138 - 149
  • [9] LOWER BOUNDS FOR COMBINATORIAL PROBLEMS ON GRAPHS
    NAKAYAMA, H
    NISHIZEKI, T
    SAITO, N
    JOURNAL OF ALGORITHMS, 1985, 6 (03) : 393 - 399
  • [10] Exponential Lower Bounds for Monotone Span Programs
    Robere, Robert
    Pitassi, Toniann
    Rossman, Benjamin
    Cook, Stephen A.
    2016 IEEE 57TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2016, : 406 - 415
12345