Browsing by Author "Sussmann, Yoram J."
Now showing 1 - 3 of 3
Results Per Page
Sort Options
Item The Capacitated K-Center Problem(1998-10-15) Khuller, Samir; Sussmann, Yoram J.The capacitated $K$-center problem is a fundamental facility location problem, where we are asked to locate $K$ facilities in a graph, and to assign vertices to facilities, so as to minimize the maximum distance from a vertex to the facility to which it is assigned. Moreover, each facility may be assigned at most $L$ vertices. This problem is known to be NP-hard. We give polynomial time approximation algorithms for two different versions of this problem that achieve approximation factors of 5 and 6. We also study some generalizations of this problem. (Also cross-referenced as UMIACS-TR-96-39)Item Facility Location with Dynamic Distance Functions(1998-10-15) ; Bhatia, Randeep; Guha, Sudipto; Khuller, Samir; Sussmann, Yoram J.Facility location problems have always been studied with the assumption that the edge lengths in the network are {\em static} and do not change over time. The underlying network could be used to model a city street network for emergency facility location/hospitals, or an electronic network for locating information centers. In any case, it is clear that due to traffic congestion the traversal time on links {\em changes} with time. Very often, we have some estimates as to how the edge lengths change over time, and our objective is to choose a set of locations (vertices) as centers, such that at {\em every} time instant each vertex has a center close to it (clearly, the center close to a vertex may change over time). We also provide approximation algorithms as well as hardness results for the $K$-center problem under this model. This is the first comprehensive study regarding approximation algorithms for facility location for good time-invariant solutions. (Also cross-references as UMIACS-TR-97-70)Item Fault Tolerant K-Center Problems(1998-10-15) Khuller, Samir; Pless, Robert; Sussmann, Yoram J.The basic $K$-center problem is a fundamental facility location problem, where we are asked to locate $K$ facilities in a graph, and to assign vertices to facilities, so as to minimize the maximum distance from a vertex to the facility to which it is assigned. This problem is known to be NP-hard, and several optimal approximation algorithms that achieve a factor of $2$ have been developed for it. We focus our attention on a generalization of this problem, where each vertex is required to have a set of $\alpha$ ($\alpha \le K$) centers close to it. In particular, we study two different versions of this problem. In the first version, each vertex is required to have at least $\alpha$ centers close to it. In the second version, each vertex that {\em does not have a center placed on it} is required to have at least $\alpha$ centers close to it. For both these versions we are able to provide polynomial time approximation algorithms that achieve constant approximation factors for {\em any} $\alpha$. For the first version we give an algorithm that achieves an approximation factor of $3$ for any $\alpha$, and achieves an approximation factor of $2$ for $\alpha < 4$. For the second version, we provide algorithms with approximation factors of $2$ for any $\alpha$. The best possible approximation factor for even the basic $K$-center problem is 2. In addition, we give a polynomial time approximation algorithm for a generalization of the $K$-supplier problem where a subset of at most $K$ supplier nodes must be selected as centers so that every demand node has at least $\alpha$ centers close to it. We also provide polynomial time approximation algorithms for all the above problems for generalizations when cost and weight functions are defined on the set of vertices. (Also cross-referenced as UMIACS-TR-96-40)