An improved approximation algorithm for knapsack median using sparsification

DOI10.1007/S00453-017-0294-4MaRDI QIDQ1751085zbMATH OpenOpenAlexFDO

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

Publication date 23 May 2018

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

combinatorial optimizationrandomized algorithmapproximation algorithmfacility-location problems

Mathematics Subject Classification ID

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

Recommendations

• An improved approximation algorithm for knapsack median using sparsification
• Constant factor approximation algorithm for the knapsack median problem
• Improved approximation algorithms for matroid and knapsack median problems and applications
• Approximation algorithms for the lower-bounded knapsack median problem
• Improved approximation algorithms for matroid and knapsack median problems and applications

Cites work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• A dependent LP-rounding approach for the \(k\)-median problem
• An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
• Approximating k-median via pseudo-approximation
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Constant factor approximation algorithm for the knapsack median problem
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Improved approximation algorithms for matroid and knapsack median problems and applications
• The design of approximation algorithms
• The matroid median problem

Cited in

(5)

• Approximation algorithms for the lower-bounded \(k\)-median and its generalizations
• Approximation algorithms for the lower-bounded knapsack median problem
• Constant approximation for fault-tolerant median problems via iterative rounding
• Constant factor approximation algorithm for the knapsack median problem
• An improved approximation algorithm for knapsack median using sparsification

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

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