Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userApproximating Soft-Capacitated Facility Location Problem With Uncertainty
158
0
0.0
(
0
)
Added by
Shuxin Cai Mr.
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We first show that a better analysis of the algorithm for The Two-Sage Stochastic Facility Location Problem from Srinivasan cite{sri07} and the algorithm for The Robust Fault Tolerant Facility Location Problem from Byrka et al cite{bgs10} can render improved approximation factors of 2.206 and alpha+4 where alpha is the maximum number an adversary can close, respectively, and which are the best ratios so far. We then present new models for the soft-capacitated facility location problem with uncertainty and design constant factor approximation algorithms to solve them. We devise the stochastic and robust approaches to handle the uncertainty incorporated into the original model. Explicitly, in this paper we propose two new problem, named The 2-Stage Soft-Capacitated Facility Location Problem and The Robust Soft-Capacitated Facility Location Problem respectively, and present constant factor approximation algorithms for them both. Our method uses reductions between facility location problems and linear-cost models, the randomized thresholding technique of Srinivasan cite{sri07} and the filtering and clustering technique of Byrka et al cite{bgs10}.
rate research
Read More
In this paper we study three previously unstudied variants of the online Facility Location problem, considering an intrinsic scenario when the clients and facilities are not only allowed to arrive to the system, but they can also depart at any moment. We begin with the study of a natural fully-dynamic online uncapacitated model where clients can be both added and removed. When a client arrives, then it has to be assigned either to an existing facility or to a new facility opened at the clients location. However, when a client who has been also one of the open facilities is to be removed, then our model has to allow to reconnect all clients that have been connected to that removed facility. In this model, we present an optimal O(log n_act / log log n_act)-competitive algorithm, where n_act is the number of active clients at the end of the input sequence. Next, we turn our attention to the capacitated Facility Location problem. We first note that if no deletions are allowed, then one can achieve an optimal competitive ratio of O(log n/ log log n), where n is the length of the sequence. However, when deletions are allowed, the capacitated version of the problem is significantly more challenging than the uncapacitated one. We show that still, using a more sophisticated algorithmic approach, one can obtain an online O(log m + log c log n)-competitive algorithm for the capacitated Facility Location problem in the fully dynamic model, where m is number of points in the input metric and c is the capacity of any open facility.
We study a variant of the uncapacitated facility location problem (UFL), where connection costs of clients are defined by (client specific) concave nondecreasing functions of the connection distance in the underlying metric. A special case capturing the complexity of this variant is the setting called facility location with penalties where clients may either connect to a facility or pay a (client specific) penalty. We show that the best known approximation algorithms for UFL may be adapted to the concave connection cost setting. The key technical contribution is an argument that the JMS algorithm for UFL may be adapted to provide the same approximation guarantee for the more general concave connection cost variant. We also study the star inventory routing with facility location (SIRPFL) problem that was recently introduced by Jiao and Ravi, which asks to jointly optimize the task of clustering of demand points with the later serving of requests within created clusters. We show that the problem may be reduced to the concave connection cost facility location and substantially improve the approximation ratio for all three variants of SIRPFL.
In this paper we initiate the study of the heterogeneous capacitated $k$-center problem: given a metric space $X = (F cup C, d)$, and a collection of capacities. The goal is to open each capacity at a unique facility location in $F$, and also to assign clients to facilities so that the number of clients assigned to any facility is at most the capacity installed; the objective is then to minimize the maximum distance between a client and its assigned facility. If all the capacities $c_i$s are identical, the problem becomes the well-studied uniform capacitated $k$-center problem for which constant-factor approximations are known. The additional choice of determining which capacity should be installed in which location makes our problem considerably different from this problem, as well the non-uniform generalizations studied thus far in literature. In fact, one of our contributions is in relating the heterogeneous problem to special-cases of the classical Santa Claus problem. Using this connection, and by designing new algorithms for these special cases, we get the following results: (a)A quasi-polynomial time $O(log n/epsilon)$-approximation where every capacity is violated by $1+varepsilon$, (b) A polynomial time $O(1)$-approximation where every capacity is violated by an $O(log n)$ factor. We get improved results for the {em soft-capacities} version where we can place multiple facilities in the same location.
The uncapacitated facility location has always been an important problem due to its connection to operational research and infrastructure planning. Byrka obtained an algorithm that is parametrized by $gamma$ and proved that it is optimal when $gamma>1.6774$. He also proved that the algorithm achieved an approximation ratio of 1.50. A later work by Shi Li achieved an approximation factor of 1.488. In this research, we studied these algorithms and several related works. Although we didnt improve upon the algorithm of Shi Li, our work did provide some insight into the problem. We also reframed the problem as a vector game, which provided a framework to design balanced algorithms for this problem.
In the streaming model, the order of the stream can significantly affect the difficulty of a problem. A $t$-semirandom stream was introduced as an interpolation between random-order ($t=1$) and adversarial-order ($t=n$) streams where an adversary intercepts a random-order stream and can delay up to $t$ elements at a time. IITK Sublinear Open Problem #15 asks to find algorithms whose performance degrades smoothly as $t$ increases. We show that the celebrated online facility location algorithm achieves an expected competitive ratio of $O(frac{log t}{log log t})$. We present a matching lower bound that any randomized algorithm has an expected competitive ratio of $Omega(frac{log t}{log log t})$. We use this result to construct an $O(1)$-approximate streaming algorithm for $k$-median clustering that stores $O(k log t)$ points and has $O(k log t)$ worst-case update time. Our technique generalizes to any dissimilarity measure that satisfies a weak triangle inequality, including $k$-means, $M$-estimators, and $ell_p$ norms. The special case $t=1$ yields an optimal $O(k)$ space algorithm for random-order streams as well as an optimal $O(nk)$ time algorithm in the RAM model, closing a long line of research on this problem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
