A framework for analyzing sub-optimal performance of local search algorithms

DOI10.1007/S10589-009-9290-1zbMATH Open1222.90035OpenAlexW1969481946MaRDI QIDQ548682FDOQ548682

Sheldon H. Jacobson, Shane N. Hall, Alexander G. Nikolaev, Darrall Henderson

Publication date: 30 June 2011

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10589-009-9290-1

Recommendations

• Using Markov chains to analyze the effectiveness of local search algorithms
• Visiting near-optimal solutions using local search algorithms
• scientific article; zbMATH DE number 1054958
• Analyzing the performance of local search algorithms using generalized hill climbing algorithms
• Theoretical aspects of local search.

zbMATH Keywords

simulated annealingconvergencetabu searchtravelling salesman problemLin-Kernighan-Helsgaun algorithmfinite-time performance

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Integer programming (90C10)

Cites Work

• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• TSPLIB—A Traveling Salesman Problem Library
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Stochastic local search. Foundations and applications.
• Title not available (Why is that?)
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing
• Title not available (Why is that?)
• Handbook of metaheuristics
• The Theory and Practice of Simulated Annealing
• On the convergence of generalized hill climbing algorithms
• A class of convergent generalized hill climbing algorithms
• Using Markov chains to analyze the effectiveness of local search algorithms
• Finite-time performance analysis of static simulated annealing algorithms
• An empirical study of a new metaheuristic for the traveling salesman problem
• Tabu search performance on the symmetric travelling salesman problem

Cited In (4)

• Subthreshold-seeking local search
• Analyzing the complexity of finding good neighborhood functions for local search algorithms
• An experimental analysis of local minima to improve neighbourhood search.
• Analyzing the performance of local search algorithms using generalized hill climbing algorithms

Uses Software

• TSPLIB
• LKH
• Tabu search

This page was built for publication: A framework for analyzing sub-optimal performance of local search algorithms

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