Hill Climbing with Multiple Local Optima

DOI10.1137/0606040MaRDI QIDQ3690218zbMATH OpenOpenAlexFDO

Authors Craig A. Tovey

Publication date 1985

Published in SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0606040

zbMATH Keywords

average performance of algorithmsbehavior of local improvement algorithmsclique problemcombinatorial optimization problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10)

Recommendations

• Low order polynomial bounds on the expected performance of local improvement algorithms
• scientific article; zbMATH DE number 18531
• A local search template.
• How easy is local search?
• Efficiency of local search with multiple local optima

Cites work

• Efficient Heuristic Procedures for Integer Linear Programming with an Interior
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3657150 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3482343 (Why is no real title available?)
• scientific article; zbMATH DE number 3559037 (Why is no real title available?)
• On the number of iterations of local improvement algorithms
• Some Examples of Difficult Traveling Salesman Problems
• Some simplified NP-complete graph problems

Cited in

(27)

• Recognition problems for special classes of polynomials in 0-1 variables
• Mechanisms for local search
• An empirical study of a new metaheuristic for the traveling salesman problem
• A new extension of local search applied to the Dial-A-Ride problem
• Data-independent neighborhood functions and strict local optima
• Polynomial transformations and data-independent neighborhood functions
• Extending shelling orders and a hierarchy of functions of unimodal simple polytopes
• How difficult is the frequency selection problem?
• PALO: a probabilistic hill-climbing algorithm
• Steepest ascent can be exponential in bounded treewidth problems
• An analysis of neighborhood functions on generic solution spaces
• On local optima in multiobjective combinatorial optimization problems
• Order preserving reductions and polynomial improving paths
• On the relative complexity of 15 problems related to~0/1-integer programming
• A TWO-STATE ANT COLONY ALGORITHM FOR SOLVING THE MINIMUM GRAPH BISECTION PROBLEM
• Multiple optima in local search
• Accelerated branch exchange heuristics for symmetric traveling salesman problems
• Construction of skolem sequences
• Low order polynomial bounds on the expected performance of local improvement algorithms
• scientific article; zbMATH DE number 1833396 (Why is no real title available?)
• Hill-Climbing Algorithm with a Stick for Unconstrained Optimization Problems
• When does hillclimbing fail on monotone functions: an entropy compression argument
• Worst improvement based iterated local search
• On the number of iterations of local improvement algorithms
• Expansion-based hill-climbing
• Cross-Hill: a heuristic method for global optimization
• Pseudo-Boolean optimization

This page was built for publication: Hill Climbing with Multiple Local Optima

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