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

DOI10.1007/978-3-319-57586-5_11MaRDI QIDQ5283361zbMATH OpenOpenAlexFDO

Authors 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) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Discrete location and assignment (90B80) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Complexity of single-swap heuristics for metric facility location and related problems
• Approximation Algorithms for Metric Facility Location Problems
• A Multi-Exchange Heuristic for the Single-Source Capacitated Facility Location Problem
• A heuristic approach to the single facility maximin location problem
• Approximation Algorithms for Single and Multi-Commodity Connected Facility Location
• scientific article; zbMATH DE number 1947060
• A hypergraph multi-exchange heuristic for the single-source capacitated facility location problem
• scientific article; zbMATH DE number 1670526
• Approximation algorithms for multicommodity facility location problems
• scientific article; zbMATH DE number 1559542

Cites work

• k-means requires exponentially many iterations even in the plane
• A local search approximation algorithm for \(k\)-means clustering
• A new greedy approach for facility location problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Greedy Strikes Back: Improved Facility Location Algorithms
• How easy is local search?
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• Least squares quantization in PCM
• Local Search Heuristics for k-Median and Facility Location Problems
• Local search: simple, successful, but sometimes sluggish
• On Simplex Pivoting Rules and Complexity Theory
• Simple Local Search Problems that are Hard to Solve
• The complexity of the \texttt{k-means} method
• The complexity of the simplex method

Cited in

(2)

• Complexity of single-swap heuristics for metric facility location and related problems
• Complexity of local search for Euclidean clustering problems

This page was built for publication: Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems

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