Facility location, distributed approximation

DOI10.1145/1073814.1073834MaRDI QIDQ5177232zbMATH OpenOpenAlexFDO

Authors Thomas Moscibroda, Roger Wattenhofer

Publication date 10 March 2015

Published in Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1073814.1073834

zbMATH Keywords

linear programmingfacility locationprimal-dual algorithmsdistributed approximation

Mathematics Subject Classification ID

Linear programming (90C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Distributed algorithms (68W15) Continuous location (90B85)

Recommendations

• Return of the primal-dual, distributed metric facility location
• A distributed O(1)-approximation algorithm for the uniform facility location problem
• Sub-logarithmic distributed algorithms for metric facility location
• Super-fast distributed algorithms for metric facility location
• A distributed approximation algorithm for fault-tolerant metric facility location

Cited in

(12)

• MapReduce based location selection algorithm for utility maximization with capacity constraints
• Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
• Kinetic facility location
• Return of the primal-dual, distributed metric facility location
• Sub-logarithmic distributed algorithms for metric facility location
• Location of distribution centers in a multi-period collaborative distribution network
• Lessons from the congested clique applied to MapReduce
• Simultaneous siting and sizing of distribution centers on a plane
• LARGE-SCALE SINGLE FACILITY CONTINUOUS LOCATION BY D.C. OPTIMIZATION
• Super-fast distributed algorithms for metric facility location
• Fast primal-dual distributed algorithms for scheduling and matching problems
• A distributed O(1)-approximation algorithm for the uniform facility location problem

This page was built for publication: Facility location, distributed approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5177232)