Constant approximation for fault-tolerant median problems via iterative rounding

DOI10.1016/j.orl.2022.05.002OpenAlexW4280620389WikidataQ114143876 ScholiaQ114143876MaRDI QIDQ2157915

Shichuan Deng

Publication date: 22 July 2022

Published in: Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmmatroid constraintknapsack constraintfault-tolerant clustering

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matroid and knapsack center problems
• LP-rounding algorithms for the fault-tolerant facility placement problem
• An improved approximation algorithm for knapsack median using sparsification
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• An approximation algorithm for the fault tolerant metric facility location problem
• A Dependent LP-Rounding Approach for the k-Median Problem
• Fault-Tolerant Facility Location: A Randomized Dependent LP-Rounding Algorithm
• A Constant Factor Approximation Algorithm for Fault-Tolerant k -Median
• Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications
• Fault-tolerant facility location
• Constant approximation for k-median and k-means with outliers via iterative rounding

This page was built for publication: Constant approximation for fault-tolerant median problems via iterative rounding