Facility location with dynamic functions distance

Randeep Bhatia, Sudipto Guha, Samir Khuller, Yoram J. Sussmann

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Facility location problems have always been studied with the assumption that the edge lengths in the network are 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 changes with time. Very often, we have 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 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 Kcenter problem under this model. This is the first comprehensive study regarding approximation algorithms for facility location for good timeinvariant solutions.

Original languageEnglish (US)
Title of host publicationAlgorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings
EditorsStefan Arnborg, Lars Ivansson
PublisherSpringer Verlag
Pages23-34
Number of pages12
ISBN (Print)3540646825, 9783540646822
DOIs
StatePublished - 1998
Event6th Scandinavian Workshop on Algorithm Theory, SWAT 1998 - Stockholm, Sweden
Duration: Jul 8 1998Jul 10 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1432
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th Scandinavian Workshop on Algorithm Theory, SWAT 1998
CountrySweden
CityStockholm
Period7/8/987/10/98

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Facility location with dynamic functions distance'. Together they form a unique fingerprint.

Cite this