Constant factor approximation algorithm for uniform hard capacitated knapsack median problem

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

Cites work

scientific article; zbMATH DE number 1559542 (Why is no real title available?)
A 3-approximation algorithm for the facility location problem with uniform capacities
A 5-approximation for capacitated facility location
A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
A dependent LP-rounding approach for the \(k\)-median problem
An approximation algorithm for uniform capacitated \(k\)-median problem with \(1+\epsilon\) capacity violation
An improved approximation algorithm for knapsack median using sparsification
An improved approximation algorithm for the hard uniform capacitated \(k\)-median problem
Analysis of a Local Search Heuristic for Facility Location Problems
Approximating capacitated \(k\)-median with \((1 + \epsilon)k\) open facilities
Approximation algorithms for hard capacitated \(k\)-facility location problems
Bi-factor approximation algorithms for hard capacitated \(k\)-median problems
Centrality of trees for capacitated \(k\)-center
Constant approximation for \(k\)-median and \(k\)-means with outliers via iterative rounding
Constant approximation for capacitated \(k\)-median with \((1+\epsilon)\)-capacity violation
Constant factor approximation algorithm for the knapsack median problem
Improved Combinatorial Algorithms for Facility Location Problems
Improved approximation algorithms for matroid and knapsack median problems and applications
LP-based approximation algorithms for capacitated facility location
On uniform capacitated \(k\)-median beyond the natural LP relaxation
The Capacitated K-Center Problem
The matroid median problem

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)