Computational bounds for local search in combinatorial optimization

DOI10.1134/S0965542508050059zbMATH Open1164.90388MaRDI QIDQ3545176FDOQ3545176

Authors: Yury Kochetov 

Publication date: 9 December 2008

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

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

zbMATH Keywords

metaheuristicslocal searchPLS problems

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cited In (16)

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

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)