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

approximation algorithmcombinatorial optimizationfacility-location problemsrandomized algorithm

Mathematics Subject Classification ID

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

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

(10)

• 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
• An improved approximation algorithm for knapsack median using sparsification
• Constant factor approximation algorithm for the knapsack median problem
• Clustering under a knapsack constraint: parameterized approximation for the knapsack median problem
• Improved approximation algorithms for matroid and knapsack means problems
• Structural iterative rounding for generalized k-median problems
• Clustering with a knapsack constraint: parameterized approximation algorithms for the knapsack median problem
• Structural iterative rounding for generalized \(k\)-median problems

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)