Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

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

Action:

login to update

Options:








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:




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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section