English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Approximation algorithms for bounded facility location

Krysta, P., & Solis-Oba, R. (1999). Approximation algorithms for bounded facility location. In T. Asano, H. Imai, D. T. Lee, S. Nakano, & T. Tokuyama (Eds.), Proceedings of the 5th Annual International Conference on Computing and Combinatorics (COCOON-99) (pp. 241-250). Berlin: Springer.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-35A2-D Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-35A4-9
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Krysta, Piotr1, Author           
Solis-Oba, Roberto1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-021999
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 518026
Other: Local-ID: C1256428004B93B8-CD419356E819B403C12567D100550892-Solis-Oba1999h
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Tokyo, Japan
Start-/End Date: -

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the 5th Annual International Conference on Computing and Combinatorics (COCOON-99)
Source Genre: Proceedings
 Creator(s):
Asano, T.1, Editor           
Imai, H., Editor
Lee, D. T., Editor
Nakano, S., Editor
Tokuyama, T., Editor
Affiliations:
1 Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 241 - 250 Identifier: ISBN: 3-540-66200-6

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 1627 Sequence Number: - Start / End Page: - Identifier: -