A Constant Factor Approximation Algorithm for Fault-Tolerant k -Median

DOI10.1145/2854153zbMath1421.68228OpenAlexW1863013115MaRDI QIDQ4962613

Shi Li, Wei Hu, Jian Li, Barna Saha, Mohammad Taghi Hajiaghayi

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

facility locationfault-toleranceapproximation algorithms\(k\)-median

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items (10)

Constant approximation for fault-tolerant median problems via iterative rounding ⋮ Approximation algorithms for clustering with dynamic points ⋮ Fault-tolerant covering problems in metric spaces ⋮ Improved PTAS for the constrained \(k\)-means problem ⋮ Conference Program Design with Single-Peaked and Single-Crossing Preferences ⋮ Tight FPT approximation for socially fair clustering ⋮ Unnamed Item ⋮ Proportional Approval Voting, Harmonic k-median, and Negative Association ⋮ A unified framework of FPT approximation algorithms for clustering problems ⋮ FPT Approximation for Constrained Metric k-Median/Means

This page was built for publication: A Constant Factor Approximation Algorithm for Fault-Tolerant k -Median