Embedding complexity and discrete optimization. I: A new divide and conquer approach to discrete optimization

DOI10.1007/s000260200002zbMath1023.90051OpenAlexW1988470180MaRDI QIDQ1400780

Dietmar Cieslik, Andreas W. M. Dress, Katharina T. Huber, Vincent L. Moulton

Publication date: 14 August 2003

Published in: Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s000260200002

zbMATH Keywords

optimizationcomputational complexitylinear programmingdynamic programmingtreewidthalgorithmic complexityinteger linear programmingdiscrete optimizationILPLPBoltzmann statistics for discrete optimization problemsdivide and qonquerdynamic-programming schemesembedding complexity

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items

Connectivity calculus ⋮ Steiner's problem in double trees