Incremental algorithms for facility location and \(k\)-median

DOI10.1016/j.tcs.2006.05.015zbMath1097.68139WikidataQ59818637 ScholiaQ59818637MaRDI QIDQ2503354

Dimitris Fotakis

Publication date: 14 September 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.05.015

zbMATH Keywords

online algorithms; facility location; incremental clustering

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

90B85: Continuous location

Related Items

Efficient Approximations for the Online Dispersion Problem, Unnamed Item, On the Facility Location Problem in Online and Dynamic Models., An online 2-dimensional clustering problem with variable sized clusters, Online facility location with facility movements, Online clustering with variable sized clusters, Online facility location with mobile facilities, General bounds for incremental maximization, Reallocating multiple facilities on the line

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple and deterministic competitive algorithm for online 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
• Better streaming algorithms for clustering problems
• Greedy Strikes Back: Improved Facility Location Algorithms
• Analysis of a Local Search Heuristic for Facility Location Problems
• Local Search Heuristics for k-Median and Facility Location Problems
• The Online Median Problem
• Clustering to minimize the sum of cluster diameters
• Approximation algorithms for hierarchical location problems