On the depth of combinatorial optimization problems

DOI10.1016/0166-218X(93)90003-7zbMath0778.68042OpenAlexW2027960705MaRDI QIDQ1801676

Walter Kern

Publication date: 9 January 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)90003-7

zbMATH Keywords

depthSimulated Annealinghill climbing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Metaheuristics: A bibliography, On the classification of NP-complete problems in terms of their correlation coefficient, Simulated annealing: An introduction, A note on the depth function of combinatorial optimization problems, Landscapes on spaces of trees, An efficient local search method for random 3-satisfiability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching theory
• How easy is local search?
• The shortest path and the shortest road through n points
• Convergence of an annealing algorithm
• Cooling Schedules for Optimal Annealing
• Two-Processor Scheduling with Start-Times and Deadlines
• On the Complexity of Local Search for the Traveling Salesman Problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem