A distributed O(1)-approximation algorithm for the uniform facility location problem

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

zbMATH Keywords

facility locationdistributed algorithmrandomized approximation algorithmsynchronous message passing model

Mathematics Subject Classification ID

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