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

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

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

• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• 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?
• 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
• \(k\)-means requires exponentially many iterations even in the plane

Cited in

(1)

• Complexity of single-swap heuristics for metric facility location and related 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)