Analysis of a local search algorithm for the k-facility location problem

DOI10.1051/ita/2016002zbMath1372.68316MaRDI QIDQ3186668

Roberto Solis-Oba, Nasim Samei

Publication date: 12 August 2016

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1051/ita/2016002

Mathematics Subject Classification ID

68W40: Analysis of algorithms

90B80: Discrete location and assignment

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68W25: Approximation algorithms

Cites Work

• Unnamed Item
• Facility location models for distribution system design
• A constant-factor approximation algorithm for the \(k\)-median problem
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A new approximation algorithm for the \(k\)-facility location problem
• Mobile Wireless Sensor Network Connectivity Repair with K-Redundancy
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Local Search Heuristics for k-Median and Facility Location Problems
• Improved Combinatorial Algorithms for Facility Location Problems