Constant factor approximation algorithm for uniform hard capacitated knapsack median problem

DOI10.4230/LIPIcs.FSTTCS.2018.23OpenAlexW2908278191MaRDI QIDQ5090959

Aditya Pancholi, Samir Khuller, Sapna Grover, Neelima Gupta

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2018.23

zbMATH Keywords

capacitated \(k\)-facility locationcapacitated knapsack Median

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Related Items (3)

LP-based approximation for uniform capacitated facility location problem ⋮ Capacitated facility location with outliers/penalties ⋮ Respecting lower bounds in uniform lower and upper bounded facility location problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A 3-approximation algorithm for the facility location problem with uniform capacities
• LP-based approximation algorithms for capacitated facility location
• Centrality of trees for capacitated \(k\)-center
• Approximation algorithms for hard capacitated \(k\)-facility location problems
• A constant-factor approximation algorithm for the k -median problem (extended abstract)
• A Dependent LP-Rounding Approach for the k-Median Problem
• A 5-Approximation for Capacitated Facility Location
• An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem
• Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications
• An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation
• An Improved Approximation Algorithm for Knapsack Median Using Sparsification
• The Capacitated K-Center Problem
• Analysis of a Local Search Heuristic for Facility Location Problems
• Approximating capacitated k-median with (1 + ∊)k open facilities
• Constant approximation for k-median and k-means with outliers via iterative rounding
• Improved Combinatorial Algorithms for Facility Location Problems
• On Uniform Capacitated k-Median Beyond the Natural LP Relaxation
• Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems

This page was built for publication: Constant factor approximation algorithm for uniform hard capacitated knapsack median problem