Constant factor approximation algorithm for uniform hard capacitated knapsack median problem
From MaRDI portal
Publication:5090959
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
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