Approximate Local Search in Combinatorial Optimization

DOI10.1137/S0097539703431007zbMath1101.68601OpenAlexW3124896382WikidataQ59592518 ScholiaQ59592518MaRDI QIDQ4651511

James B. Orlin, Abraham P. Punnen, Andreas S. Schulz

Publication date: 21 February 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitycombinatorial optimizationlocal searchapproximation algorithmsneighborhood search0/1-integer programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (17)

Computing Stable Outcomes in Hedonic Games ⋮ Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem ⋮ Integer Programming: Optimization and Evaluation Are Equivalent ⋮ An improved \((1+1)\) evolutionary algorithm for \(k\)-Median clustering problem with performance guarantee ⋮ Exact and Approximation Algorithms for the Expanding Search Problem ⋮ Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games ⋮ On the Relative Complexity of 15 Problems Related to 0/1-Integer Programming ⋮ The capacitated max \(k\)-cut problem ⋮ Complexity of local search for the \(p\)-median problem ⋮ Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees ⋮ A scaling algorithm for optimizing arbitrary functions over vertices of polytopes ⋮ Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games ⋮ A problem reduction based approach to discrete optimization algorithm design ⋮ Symmetries and the complexity of pure Nash equilibrium ⋮ Nonoblivious 2-Opt heuristics for the traveling salesman problem ⋮ A class of exponential neighbourhoods for the quadratic travelling salesman problem ⋮ Better approximation algorithms for the maximum internal spanning tree problem

This page was built for publication: Approximate Local Search in Combinatorial Optimization