Facility Location with Dynamic Distance Functions
| dc.contributor.author | en_US | |
| dc.contributor.author | Bhatia, Randeep | en_US |
| dc.contributor.author | Guha, Sudipto | en_US |
| dc.contributor.author | Khuller, Samir | en_US |
| dc.contributor.author | Sussmann, Yoram J. | en_US |
| dc.date.accessioned | 2004-05-31T22:47:54Z | |
| dc.date.available | 2004-05-31T22:47:54Z | |
| dc.date.created | 1997-10 | en_US |
| dc.date.issued | 1998-10-15 | en_US |
| dc.description.abstract | 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) | en_US |
| dc.format.extent | 253206 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/917 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-3834 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-97-70 | en_US |
| dc.title | Facility Location with Dynamic Distance Functions | en_US |
| dc.type | Technical Report | en_US |