Computer Science – Data Structures and Algorithms
Scientific paper
2011-04-15
Computer Science
Data Structures and Algorithms
Scientific paper
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)\in F$ so that each open facility serves {\em at least $M$ clients}, where $M$ is an input parameter. The cost of such a solution is $\sum_{i\in F}f_i+\sum_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.
Ahmadian Sara
Swamy Chaitanya
No associations
LandOfFree
Improved Approximation Guarantees for Lower-Bounded Facility Location does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Improved Approximation Guarantees for Lower-Bounded Facility Location, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Approximation Guarantees for Lower-Bounded Facility Location will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-9440