Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems (Q2428688): Difference between revisions

@@ Property / full work available at URL @@
+https://doi.org/10.1007/s00453-010-9475-0
+Normal rank
@@ Property / OpenAlex ID @@
+W2146843586
@@ Property / OpenAlex ID: W2146843586 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3056948
@@ Property / cites work: Q3056948 / rank @@
+Normal rank
@@ Property / cites work @@
+Toward a model for backtracking and dynamic programming
+Normal rank
@@ Property / cites work @@
+Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study
+Normal rank
@@ Property / cites work @@
+Using Grammars to Generate Very Large Scale Neighborhoods for the Traveling Salesman Problem and Other Sequencing Problems
+Normal rank
@@ Property / cites work @@
+A survey of computational complexity results in systems and control
+Normal rank
@@ Property / cites work @@
+(Incremental) priority algorithms
@@ Property / cites work: (Incremental) priority algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+A stronger model of dynamic programming algorithms
+Normal rank
@@ Property / cites work @@
+Q3651735
@@ Property / cites work: Q3651735 / rank @@
+Normal rank
@@ Property / cites work @@
+A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.
+Normal rank
@@ Property / cites work @@
+Q5538132
@@ Property / cites work: Q5538132 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Trivial integer programs unsolvable by branch-and-bound
+Normal rank
@@ Property / cites work @@
+A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
+Normal rank
@@ Property / cites work @@
+Some Exact Complexity Results for Straight-Line Computations over Semirings
+Normal rank
@@ Property / cites work @@
+Lower bounds for resolution and cutting plane proofs and monotone computations
+Normal rank
@@ Property / cites work @@
+Using Randomization to Break the Curse of Dimensionality
+Normal rank
@@ Property / cites work @@
+The complexity of computing the permanent
@@ Property / cites work: The complexity of computing the permanent / rank @@
+Normal rank
@@ Property / cites work @@
+Computing Powers in Parallel
@@ Property / cites work: Computing Powers in Parallel / rank @@
+Normal rank
@@ Property / cites work @@
+Approximations of Dynamic Programs, I
@@ Property / cites work: Approximations of Dynamic Programs, I / rank @@
+Normal rank
@@ Property / cites work @@
+Approximations of Dynamic Programs, II
@@ Property / cites work: Approximations of Dynamic Programs, II / rank @@
+Normal rank
@@ Property / cites work @@
+When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
+Normal rank