An improved approximation algorithm for knapsack median using sparsification

DOI10.1007/s00453-017-0294-4zbMath1390.68759OpenAlexW2787947809MaRDI QIDQ1751085

Joachim Spoerhase, Khoa Trinh, Aravind Srinivasan, Bartosz Rybicki, Jaroslaw Byrka, Thomas W. Pensyl

Publication date: 23 May 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-017-0294-4

zbMATH Keywords

combinatorial optimizationapproximation algorithmrandomized algorithmfacility-location problems

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Constant approximation for fault-tolerant median problems via iterative rounding ⋮ Approximation algorithms for the lower-bounded \(k\)-median and its generalizations ⋮ Approximation algorithms for the lower-bounded knapsack median problem

Cites Work

• Unnamed Item
• Unnamed Item
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A constant-factor approximation algorithm for the k -median problem (extended abstract)
• A Dependent LP-Rounding Approach for the k-Median Problem
• Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications
• The Design of Approximation Algorithms
• 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
• An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
• Approximating k-median via pseudo-approximation

This page was built for publication: An improved approximation algorithm for knapsack median using sparsification