MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Krysta, Piotr
Solis-Oba, Roberto
dblp
dblp
Editor(s):
Asano, T.
Imai, H.
Lee, D. T.
Nakano, S.
Tokuyama, T.
dblp
dblp
dblp
dblp
dblp
BibTeX cite key*:
Solis-Oba1999h
Title, Booktitle
Title*:
Approximation algorithms for bounded facility location
Booktitle*:
Proceedings of the 5th Annual International Conference on Computing and Combinatorics (COCOON-99)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Tokyo, Japan
Language:
English
Event Date*
(no longer used):
July, 26 - July, 28
Organization:
Event Start Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Event End Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Publisher
Name*:
Springer
URL:
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1627
Number:
Month:
July
Pages:
241-250
Year*:
1999
VG Wort Pages:
ISBN/ISSN:
3-540-66200-6
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
The bounded $k$-median problem is to select in an undirected graph $G=(V,E)
$ a set $S$ of $k$
vertices such that the maximum distance from a vertex $v \in V$ to $S$ is at mos
t a given bound $d$
and the average distance from vertices $V$ to $S$ is minimized. We present random
ized
algorithms for several versions of this problem.
We also study the bounded version of the uncapacitated facility location problem.

For this latter problem we
present extensions of known deterministic algorithms for the unbounded version, a
nd we prove some inapproximability results.
Keywords:
facility location, approximation algorithms, linear programming
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Solis-Oba1999h,
AUTHOR = {Krysta, Piotr and Solis-Oba, Roberto},
EDITOR = {Asano, T. and Imai, H. and Lee, D. T. and Nakano, S. and Tokuyama, T.},
TITLE = {Approximation algorithms for bounded facility location},
BOOKTITLE = {Proceedings of the 5th Annual International Conference on Computing and Combinatorics (COCOON-99)},
PUBLISHER = {Springer},
YEAR = {1999},
VOLUME = {1627},
PAGES = {241--250},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Tokyo, Japan},
MONTH = {July},
ISBN = {3-540-66200-6},
}


Entry last modified by Christine Kiesel, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Roberto Solis-Oba
Created
08/18/1999 05:28:47 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Christine Kiesel
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Edit Dates
02.05.2007 17:14:40
07.04.2000 09:44:23
30.03.2000 12:26:46
29.03.2000 14:52:47
18/02/2000 19:49:34