Constant-Factor FPT Approximation for Capacitated k-Median.
Marek AdamczykJaroslaw ByrkaJan MarcinkowskiSyed Mohammad MeesumMichal WlodarczykPublished in: ESA (2019)
Keyphrases
- constraint satisfaction problems
- constant factor
- np hard
- approximation algorithms
- lower bound
- worst case
- np complete
- approximation ratio
- approximation guarantees
- minimum cost
- special case
- scheduling problem
- upper bound
- linear programming
- primal dual
- integer programming
- knapsack problem
- linear program
- sample complexity
- data sets
- theoretical analysis