Polynomial transformations and data-independent neighborhood functions

DOI10.1016/j.dam.2003.06.008zbMath1077.90040OpenAlexW1984835487MaRDI QIDQ1887061

Derek E. Armstrong, Jacobson, Sheldon H.

Publication date: 23 November 2004

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

Full work available at URL: https://doi.org/10.1016/j.dam.2003.06.008

zbMATH Keywords

Computational complexityLocal search algorithmNP-hard discrete optimization problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Boolean programming (90C09)

Related Items

Analyzing the complexity of finding good neighborhood functions for local search algorithms, Data-independent neighborhood functions and strict local optima, Order preserving reductions and polynomial improving paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate solution of NP optimization problems
• Analyzing the complexity of finding good neighborhood functions for local search algorithms
• Neighborhood search algorithms for guaranteeing optimal traveling salesman tours must be inefficient
• Data-independent neighborhood functions and strict local optima
• Hill Climbing with Multiple Local Optima
• Multiple optima in local search
• Some Examples of Difficult Traveling Salesman Problems
• The complexity of theorem-proving procedures
• Further Reduction of Zero-One Polynomial Programming Problems to Zero-One linear Programming Problems