An Improved Approximation Algorithm for Knapsack Median Using Sparsification

DOI10.1007/978-3-662-48350-3_24zbMath1386.68216OpenAlexW2273315864MaRDI QIDQ3452792

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

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48350-3_24

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 factor approximation algorithm for uniform hard capacitated knapsack median problem

Cites Work

• 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
• 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