Browse

Probabilistic Analysis of a Relaxation for the K-Median Problem -The Euclidean Model in the Plane

Cited 0 time in Web of Science Cited 0 time in Scopus
Authors
Ahn, Sang-Hyung
Issue Date
1986-09
Publisher
서울대학교 경영대학 경영연구소
Citation
경영논집, Vol.20 No.3, pp. 46-62
Keywords
46-62
Description
1986-09
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.
ISSN
1229-0491
Language
English
URI
http://hdl.handle.net/10371/54164
Files in This Item:
Appears in Collections:
College of Business Administration/Business School (경영대학/대학원)Institute of Management Research (경영연구소)경영논집경영논집 vol.20 (1986)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse