Low order polynomial bounds on the expected performance of local improvement algorithms

DOI10.1007/BF01580647zbMath0613.90065OpenAlexW1973735752MaRDI QIDQ4721084

Craig A. Tovey

Publication date: 1986

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01580647

zbMATH Keywords

linear complementarityextremal set theorylocal improvementprincipal pivotingaverage performance of algorithmshill climbing in artificial intelligence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Linear programming (90C05) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Related Items

Extending shelling orders and a hierarchy of functions of unimodal simple polytopes, Recognition problems for special classes of polynomials in 0-1 variables, Local optimization on graphs, On parallel versus sequential approximation, Pseudo-Boolean optimization, Combinatorial structure and randomized subexponential algorithms for infinite games

Cites Work

• On the number of iterations of local improvement algorithms
• Observations on a class of nasty linear complementarity problems
• A simple heuristic approach to simplex efficiency
• Complementary pivot theory of mathematical programming
• The simplex algorithm with the pivot rule of maximizing criterion improvement
• Hill Climbing with Multiple Local Optima
• Computational complexity of LCPs associated with positive definite symmetric matrices
• Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
• Convex Location Problems on Tree Networks
• Computer Solutions of the Traveling Salesman Problem
• Lengths of snakes in boxes
• Efficient Heuristic Procedures for Integer Linear Programming with an Interior
• Sets of Lattice Points which Contain a Maximal Number of Edges
• The complexity of theorem-proving procedures
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item