Approximating capacitated k-median with (1 + )k open facilities

DOI10.1137/1.9781611974331.CH56MaRDI QIDQ4575635zbMATH OpenOpenAlexFDO

Authors Shi Li

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.5630

zbMATH Keywords

capacitated \(k\)-median problemopen facilities

Mathematics Subject Classification ID

Approximation algorithms (68W25) Discrete location and assignment (90B80)

Abstract: In the capacitated $k$-median (CKM) problem, we are given a set $F$ of facilities, each facility $iinF$ with a capacity $u_i$, a set $C$ of clients, a metric $d$ over $FcupC$ and an integer $k$. The goal is to open $k$ facilities in $F$ and connect the clients $C$ to the open facilities such that each facility $i$ is connected by at most $u_i$ clients, so as to minimize the total connection cost. In this paper, we give the first constant approximation for CKM, that only violates the cardinality constraint by a factor of $1+epsilon$. This generalizes the result of [Li15], which only works for the uniform capacitated case. Moreover, the approximation ratio we obtain is $$, which is an exponential improvement over the ratio of $exp(O(1/epsilo{n}^2))$ in [Li15]. The natural LP relaxation for the problem, which almost all previous algorithms for CKM are based on, has unbounded integrality gap even if $(2-epsilon)k$ facilities can be opened. We introduce a novel configuration LP for the problem, that overcomes this integrality gap.

Recommendations

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

Cited in

(27)

• On the fixed-parameter tractability of capacitated clustering
• Generalized center problems with outliers
• On parameterized approximation algorithms for balanced clustering
• A technique for obtaining true approximations for \(k\)-center with covering constraints
• To close is easier than to open: dual parameterization to \(k\)-median
• A technique for obtaining true approximations for \(k\)-center with covering constraints
• On colorful vertex and edge cover problems
• scientific article; zbMATH DE number 7651201 (Why is no real title available?)
• Constant factor approximation algorithm for uniform hard capacitated knapsack median problem
• 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
• On uniform capacitated \(k\)-median beyond the natural LP relaxation
• Approximation algorithms for clustering with dynamic points
• On the cost of essentially fair clusterings
• Robust \(k\)-center with two types of radii
• Robust \(k\)-center with two types of radii
• Approximation algorithms for clustering with dynamic points
• Constant approximation algorithm for nonuniform capacitated multi-item lot sizing via strong covering inequalities
• Capacitated facility location with outliers/penalties
• Improved parameterized approximation for balanced \(k\)-median
• FPT Approximation for Constrained Metric k-Median/Means
• Approximating \(k\)-median with non-uniform capacities
• LP-based approximation for uniform capacitated facility location problem
• Constant-Factor FPT Approximation for Capacitated k-Median
• An approximation algorithm for soft capacitated k-facility location problem
• On uniform capacitated \(k\)-median beyond the natural LP relaxation
• Better guarantees for \(k\)-median with service installation costs

This page was built for publication: Approximating capacitated \(k\)-median with \((1 + \epsilon)k\) open facilities

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