A distributed O(1)-approximation algorithm for the uniform facility location problem
From MaRDI portal
Publication:528857
DOI10.1007/s00453-012-9690-yzbMath1360.68893OpenAlexW1973201650MaRDI QIDQ528857
Joachim Gehweiler, Christiane Lammersen, Christian Sohler
Publication date: 17 May 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9690-y
facility locationdistributed algorithmrandomized approximation algorithmsynchronous message passing model
Discrete location and assignment (90B80) Approximation algorithms (68W25) Distributed algorithms (68W15)
Related Items (2)
Sub-logarithmic distributed algorithms for metric facility location ⋮ Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation Algorithms for Metric Facility Location Problems
- 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
- A new greedy approach for facility location problems
- 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
- Distributed Computing: A Locality-Sensitive Approach
- Local Search Heuristics for k-Median and Facility Location Problems
- Quick k-Median, k-Center, and Facility Location for Sparse Graphs
- The Online Median Problem
- Return of the primal-dual
- Facility location
- Improved Combinatorial Algorithms for Facility Location Problems
- A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
- Automata, Languages and Programming
- An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
This page was built for publication: A distributed O(1)-approximation algorithm for the uniform facility location problem
