Computational bounds for local search in combinatorial optimization

DOI10.1134/S0965542508050059MaRDI QIDQ3545176zbMATH OpenFDO

Authors Yury Kochetov

Publication date 9 December 2008

Published in Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

zbMATH Keywords

metaheuristicslocal searchPLS problems

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 18531
• Local search: simple, successful, but sometimes sluggish
• How easy is local search?
• A note on the complexity of local search problems
• Approximate local search in combinatorial optimization

Cited in

(16)

• On the complexity of the local search in the \(p\)-median problem
• Local search, reducibility and approximability of NP-optimization problems
• Approximate local search in combinatorial optimization
• scientific article; zbMATH DE number 2087632 (Why is no real title available?)
• On solving travelling salesman problem with vertex requisitions
• Approximate Local Search in Combinatorial Optimization
• Comparison of models of planning public-private partnership
• Classification of applied methods of combinatorial optimization
• Low order polynomial bounds on the expected performance of local improvement algorithms
• Structural analysis of local search heuristics in combinatorial optimization
• Approximate solution of the \(p\)-median minimization problem
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• The communication complexity of local search
• Condition number based complexity estimate for computing local extrema
• Bounds-Consistent Local Search

This page was built for publication: Computational bounds for local search in combinatorial optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3545176)