MPI-INF D1 Publications: Proceedings Article: Approximation algorithms for bounded facility location

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

Options:

Goto entry point

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

URL of the conference:
URL for downloading the paper:
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:


(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

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

Attachment Section