Large-scale distributed algorithms for facility location with outliers

DOI10.4230/LIPICS.OPODIS.2018.5MaRDI QIDQ5091075zbMATH OpenFDO

Authors Tanmay Inamdar, Shreyas Pai, Sriram Pemmaraju

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1811.06494

zbMATH Keywords

\(k\)-machine modelclustering with outlierscongested cliquedistributed algorithmsmassively parallel computationmetric facility location

Mathematics Subject Classification ID

Distributed systems (68M14) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• Super-fast distributed algorithms for metric facility location
• Algorithms for facility location problems with outliers. (Extended abstract)
• Sub-logarithmic distributed algorithms for metric facility location
• A distributed approximation algorithm for fault-tolerant metric facility location
• A distributed O(1)-approximation algorithm for the uniform facility location problem

Cites work

• ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)
• A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
• Algorithms for facility location problems with outliers. (Extended abstract)
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation of distances and shortest paths in the broadcast congest clique
• Communication steps for parallel query processing
• Data stream clustering
• Distributed approximation algorithms for weighted shortest paths
• Distributed computation of large-scale graph problems
• Distributed MIS via all-to-all communication
• scientific article; zbMATH DE number 1256715 (Why is no real title available?)
• scientific article; zbMATH DE number 6297759 (Why is no real title available?)
• Improved massively parallel computation algorithms for MIS, matching, and vertex cover
• Lagrangian relaxation for the \(k\)-median problem: new insights and continuity properties
• Lessons from the congested clique applied to MapReduce
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• MST in \(O(1)\) rounds of congested clique
• Near-optimal approximate shortest paths and transshipment in distributed and streaming models
• Optimal deterministic routing and sorting on the congested clique
• Parallel algorithms for geometric graph problems
• Quick k-Median, k-Center, and Facility Location for Sparse Graphs
• Sorting, searching, and simulation in the MapReduce framework
• Sub-logarithmic distributed algorithms for metric facility location
• Super-fast distributed algorithms for metric facility location
• The communication complexity of distributed task allocation
• The Online Median Problem
• The round complexity of distributed sorting, extended abstract

Cited in

(2)

• Exact algorithms for handling outliers in center location problems on networks using \(k\)-max functions
• The distributed algorithms for the lower-bounded \(k\)-center clustering in metric space

This page was built for publication: Large-scale distributed algorithms for facility location with outliers

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