Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems

DOI10.1007/978-981-10-6147-9_1zbMath1397.90231OpenAlexW2758862595MaRDI QIDQ4689624

Hyung-Chan An, Ola Svensson

Publication date: 16 October 2018

Published in: Combinatorial Optimization and Graph Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-981-10-6147-9_1

zbMATH Keywords

linear programminglocal search

Mathematics Subject Classification ID

Linear programming (90C05) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items

An improved \((1+1)\) evolutionary algorithm for \(k\)-Median clustering problem with performance guarantee ⋮ Discrete facility location in machine learning

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A 3-approximation algorithm for the facility location problem with uniform capacities
• Centrality of trees for capacitated \(k\)-center
• Easy and hard bottleneck location problems
• Improved approximation algorithms for capacitated facility location problems
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A constant-factor approximation algorithm for the k -median problem (extended abstract)
• A Dependent LP-Rounding Approach for the k-Median Problem
• A 5-Approximation for Capacitated Facility Location
• LP-Based Algorithms for Capacitated Facility Location
• 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
• A Best Possible Heuristic for the k-Center Problem
• Faces for a linear inequality in 0–1 variables
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Analysis of a Local Search Heuristic for Facility Location Problems
• Local search heuristic for k-median and facility location problems
• Evaluation of a Branch and Bound Algorithm for Clustering
• Improved Combinatorial Algorithms for Facility Location Problems
• The analysis of a simple k -means clustering algorithm
• Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems
• Approximating k-median via pseudo-approximation
• Heuristic Methods for Estimating the Generalized Vertex Median of a Weighted Graph
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

This page was built for publication: Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems