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

DOI10.1137/1.9781611974331.CH56zbMATH Open1418.90141arXiv1411.5630OpenAlexW4256246662MaRDI QIDQ4575635FDOQ4575635

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)

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.

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

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

zbMATH Keywords

capacitated \(k\)-median problemopen facilities

Mathematics Subject Classification ID

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

Cited In (27)

• On the fixed-parameter tractability of capacitated clustering
• Generalized center problems with outliers
• On parameterized approximation algorithms for balanced clustering
• On colorful vertex and edge cover problems
• 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
• Title not available (Why is that?)
• 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
• On uniform capacitated \(k\)-median beyond the natural LP relaxation
• Constant approximation for capacitated \(k\)-median with \((1+\epsilon)\)-capacity violation
• 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
• Approximation algorithms for clustering with dynamic points
• Capacitated facility location with outliers/penalties
• Constant approximation algorithm for nonuniform capacitated multi-item lot sizing via strong covering inequalities
• FPT Approximation for Constrained Metric k-Median/Means
• Improved parameterized approximation for balanced \(k\)-median
• 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)