Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems

DOI10.1007/978-3-319-57586-5_11zbMath1407.68209OpenAlexW2585261962MaRDI QIDQ5283361

Sascha Brauer

Publication date: 21 July 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-57586-5_11

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• Unnamed Item
• \(k\)-means requires exponentially many iterations even in the plane
• A local search approximation algorithm for \(k\)-means clustering
• How easy is local search?
• The Complexity of the Simplex Method
• Simple Local Search Problems that are Hard to Solve
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A new greedy approach for facility location problems
• Local Search: Simple, Successful, But Sometimes Sluggish
• Greedy Strikes Back: Improved Facility Location Algorithms
• The Complexity of the k-means Method
• Local Search Heuristics for k-Median and Facility Location Problems
• Least squares quantization in PCM
• On Simplex Pivoting Rules and Complexity Theory