Constant factor approximation algorithm for uniform hard capacitated knapsack median problem

DOI10.4230/LIPICS.FSTTCS.2018.23OpenAlexW2908278191MaRDI QIDQ5090959FDOQ5090959

Authors: Sapna Grover, Samir Khuller, Aditya Pancholi, 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)

Cites Work

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

Cited In (4)

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

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

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