Improved approximation guarantees for lower-bounded facility location

DOI10.1007/978-3-642-38016-7_21zbMATH Open1395.68332arXiv1104.3128OpenAlexW1680732213MaRDI QIDQ2848930FDOQ2848930

Authors: Sara Ahmadian, Chaitanya Swamy 

Publication date: 13 September 2013

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Abstract: We consider the {em lower-bounded facility location} (lbfl) problem (also sometimes called {em load-balanced facility location}), which is a generalization of {em uncapacitated facility location} (ufl), where each open facility is required to serve a certain {em minimum} amount of demand. More formally, an instance $I$ of lbfl is specified by a set $F$ of facilities with facility-opening costs $f_i$, a set $D$ of clients, and connection costs $c_{ij}$ specifying the cost of assigning a client $j$ to a facility $i$, where the $c_{ij}$s form a metric. A feasible solution specifies a subset $F$ of facilities to open, and assigns each client $j$ to an open facility $i(j)inF$ so that each open facility serves {em at least $M$ clients}, where $M$ is an input parameter. The cost of such a solution is $su{m}_{iinF}{f}_i+su{m}_j{c}_{i(j)j}$, and the goal is to find a feasible solution of minimum cost. The current best approximation ratio for lbfl is 448 cite{Svitkina08}. We substantially advance the state-of-the-art for lbfl by devising an approximation algorithm for lbfl that achieves a significantly-improved approximation guarantee of 82.6. Our improvement comes from a variety of ideas in algorithm design and analysis, which also yield new insights into lbfl.

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

Recommendations

• On facility location with general lower bounds
• Lower-bounded facility location
• scientific article; zbMATH DE number 6263680
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem

Mathematics Subject Classification ID

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

Cited In (20)

• Lower-bounded facility location
• On facility location with general lower bounds
• Approximation algorithms for clustering problems with lower bounds and outliers
• On coresets for fair clustering in metric and Euclidean spaces and their applications
• Upper Bound for the Competitive Facility Location Problem with Quantile Criterion
• Approximation algorithms for the lower-bounded \(k\)-median and its generalizations
• On the cost of essentially fair clusterings
• Combinatorial approximation algorithms for buy-at-bulk connected facility location problems
• Faster balanced clusterings in high dimension
• Connected \(k\)-center and \(k\)-diameter clustering
• Approximation algorithms for the lower-bounded knapsack median problem
• An approximation framework for bounded facility location problems
• Improved complexity bounds for location problems on the real line
• Approximation algorithms for a combined facility location buy-at-bulk network design problem
• An improved lower bound for the multimedian location problem
• Approximate the lower-bounded connected facility location problem
• Approximating connected facility location with lower and upper bounds via LP rounding
• Improved bounds for metric capacitated covering problems
• Respecting lower bounds in uniform lower and upper bounded facility location problem
• Approximation algorithms for the lower bounded correlation clustering problem

This page was built for publication: Improved approximation guarantees for lower-bounded facility location

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