Browse

A Probabilistic Analysis of a relaxation for the K-median Problem -A Graphical Model

Cited 0 time in Web of Science Cited 0 time in Scopus
Authors
Ahn, Sang-Hyung
Issue Date
1987-09
Publisher
서울대학교 경영대학 경영연구소
Citation
경영논집, Vol.21 No.3, pp. 1-15
Keywords
1-15
Description
1987-09
Abstract
This paper is sequal to the paper(l), where we performed probabilistic analysis

for the Euclidean k-median problem in the plane. In this paper, our

analysis is concerned with the following graphical k-median problem Let G; (p) be a random graph with n nodes, where each edge occurs independently with probability p, and C;j is the minimum number of edges on a

path joining i to j for where the minimum is taken over all paths joining i to i. Thus C;j is the shortest distance between i and j, assuming that all edges have length one.
ISSN
1229-0491
Language
English
URI
http://hdl.handle.net/10371/54194
Files in This Item:
Appears in Collections:
College of Business Administration/Business School (경영대학/대학원)Institute of Management Research (경영연구소)경영논집경영논집 vol.21 (1987)
  • mendeley

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

Browse