The effectiveness of finite improvement algorithms for finding global optima

DOI10.1007/BF01415994zbMath0788.68061OpenAlexW1992196549MaRDI QIDQ4201810

Jacobson, Sheldon H., Daniel Solow

Publication date: 29 August 1993

Published in: [https://portal.mardi4nfdi.de/entity/Q3031760 ZOR Zeitschrift f�r Operations Research Methods and Models of Operations Research] (Search for Journal in Brave)

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

zbMATH Keywords

optimizationdecidabilitylocal search algorithms\(NP\)-hard

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (4)

Analyzing the complexity of finding good neighborhood functions for local search algorithms ⋮ An analysis of neighborhood functions on generic solution spaces ⋮ A class of convergent generalized hill climbing algorithms ⋮ Order preserving reductions and polynomial improving paths

Cites Work

• On the number of iterations of local improvement algorithms
• A new polynomial-time algorithm for linear programming
• How easy is local search?
• The generalized simplex method for minimizing a linear form under linear inequality restraints
• Maximal Flow Through a Network
• A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem
• A finite descent theory for linear programming, piecewise linear convex minimization, and the linear complementarity problem
• An Out-of-Kilter Method for Minimal-Cost Flow Problems
• The Simplex and Projective Scaling Algorithms as Iteratively Reweighted Least Squares Methods
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Bimatrix Equilibrium Points and Mathematical Programming

This page was built for publication: The effectiveness of finite improvement algorithms for finding global optima