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

Recommendations

• On uniform capacitated \(k\)-median beyond the natural LP relaxation
• On uniform capacitated \(k\)-median beyond the natural LP relaxation
• Bi-factor approximation algorithms for hard capacitated \(k\)-median problems
• An approximation algorithm for uniform capacitated \(k\)-median problem with \(1+\epsilon\) capacity violation
• Constant approximation for capacitated \(k\)-median with \((1+\epsilon)\)-capacity violation

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
• The matroid median problem
• 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
• Constant factor approximation algorithm for the knapsack median problem
• 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
• Constant approximation for capacitated \(k\)-median with \((1+\epsilon)\)-capacity violation
• 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 + \epsilon)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)