Publications
Detailed Information
Probabilistic Analysis of a Relaxation for the K-Median Problem -The Euclidean Model in the Plane
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ahn, Sang-Hyung | - |
dc.date.accessioned | 2010-02-10T05:34:14Z | - |
dc.date.available | 2010-02-10T05:34:14Z | - |
dc.date.issued | 1986-09 | - |
dc.identifier.citation | 경영논집, Vol.20 No.3, pp. 46-62 | - |
dc.identifier.issn | 1229-0491 | - |
dc.identifier.uri | https://hdl.handle.net/10371/54164 | - |
dc.description | 1986-09 | - |
dc.description.abstract | The k-median problem has been widely studied both from the theoretical
point of view and for its applications. An interesting theoretical development was the successful probabilistic analysis of several heuristics for this problem (e.g. Fisher and Hochbaum (8) and Papadimitriou(22). On the other hand, the literature on the k-median problem abounds in exact algorithms. Most are based on the solution of a certain relaxation to be defined later. The computational experience reported in the literature seems to indicate that this particular relaxation yields impressively tight bounds compared to what can usually be expected in integer programming. In this paper we analyze to what extent this relaxation is tight. We perform our analysis for a classical Euclidean model in the plane and show that the relaxation can be expected to provide a bound within one third of one percent of the optimum value of the k-median problem. | - |
dc.language.iso | en | - |
dc.publisher | 서울대학교 경영대학 경영연구소 | - |
dc.subject | 46-62 | - |
dc.title | Probabilistic Analysis of a Relaxation for the K-Median Problem -The Euclidean Model in the Plane | - |
dc.type | SNU Journal | - |
dc.contributor.AlternativeAuthor | 安相炯 | - |
dc.contributor.AlternativeAuthor | 안상형 | - |
dc.citation.journaltitle | 경영논집 | - |
dc.citation.endpage | 62 | - |
dc.citation.number | 3 | - |
dc.citation.pages | 46-62 | - |
dc.citation.startpage | 46 | - |
dc.citation.volume | 20 | - |
- Appears in Collections:
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.