Capacitated facility location with outliers/penalties

DOI10.1007/978-3-031-22105-7_49arXiv2012.07135OpenAlexW4313343286MaRDI QIDQ6168979FDOQ6168979

Authors: Rajni Dabas, Neelima Gupta 

Publication date: 10 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: In this paper, we present a framework to design approximation algorithms for capacitated facility location problems with penalties/outliers using LP-rounding. Primal-dual technique, which has been particularly successful in dealing with outliers and penalties, has not been very successful in dealing with capacities. On the other hand, no primal-dual solution has been able to break the hardness of capacitated facility location problem(CFLP). LP-rounding techniques had also not been very successful in dealing with capacities until a recent work by Grover et al. cite{GroverGKP18}. Their constant factor approximation violating the capacities by a small factor ($1+epsilon$) is promising while dealing with capacities.Though LP-rounding has not been very promising while dealing with penalties and outliers, we successfully apply it to deal with them along with capacities. That is, our results are obtained by rounding the solution to the natural LP once again exhibiting the power of LP-rounding technique. Solutions obtained by LP-rounding are easy to integrate with other LP-based algorithms.In this paper, we apply our framework to obtain first constant factor approximations for capacitated facility location problem with outlier (CFLPO) and capacitated $k$-facility location problem with penalty(C$k$FLPP) for hard uniform capacities using LP-rounding. Our solutions incur slight violations in capacities, ($1+epsilon$) for the problems without cardinality($k$) constraint and ($2+epsilon$) for the problems with the cardinality constraint. For the outlier variant, we also incur a small loss ($1+epsilon$) in outliers. Due to the hardness of the underlying problems, the violations are inevitable. Thus we achieve the best possible by rounding the solution of natural LP for these problems. To the best of our knowledge, no results are known for CFLPO and C$k$FLPP.

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

zbMATH Keywords

outliersapproximationfacility location\(k\)-medianpenalties

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• Algorithms for facility location problems with outliers. (Extended abstract)
• Title not available (Why is that?)
• A 3-approximation for facility location with uniform capacities
• LP-based approximation algorithms for capacitated facility location
• A 5-approximation for capacitated facility location
• LP-based algorithms for capacitated facility location
• Approximation algorithms for hard capacitated \(k\)-facility location problems
• Local search algorithms for the red-blue median problem
• An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme
• Constant approximation for capacitated \(k\)-median with \((1+\epsilon)\)-capacity violation
• Bi-factor approximation algorithms for hard capacitated \(k\)-median problems
• Constant Factor Approximation for Capacitated k-Center with Outliers
• Approximating capacitated \(k\)-median with \((1 + \epsilon)k\) open facilities
• Approximation Schemes for Clustering with Outliers
• Constant factor approximation algorithm for uniform hard capacitated knapsack median problem
• Capacitated facility location with outliers/penalties

Cited In (4)

• Capacitated center problems with two-sided bounds and outliers
• Capacitated facility location with outliers/penalties
• Constant Factor Approximation for Capacitated k-Center with Outliers
• FPT approximation for capacitated clustering with outliers

This page was built for publication: Capacitated facility location with outliers/penalties

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