Online median problem and its competitive algorithm analysis

Wen Qiang Dai; Yin Feng Xu; Guo Liang He

Online median problem and its competitive algorithm analysis

Wen Qiang Dai
, Yin Feng Xu
, Guo Liang He

School of Management

University of Electronic Science and Technology of China

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

Based on the actual constrain in locating facility, that is, the decision-maker must determine where to locate the initial facilities when the final number of facilities is uncertain, and, the constructed facilities can not be removed when the new facility is built, we studies the dynamics facility location problem with the uncertain number of facilities from the online theory view. We present a polynomial competitive algorithm, whose competitive ratio is better than the existed results.

Original language	English
Pages (from-to)	159-164
Number of pages	6
Journal	Xitong Gongcheng Lilun yu Shijian/System Engineering Theory and Practice
Volume	27
Issue number	10
State	Published - Oct 2007

Keywords

Algorithm
Competitive ratio
Facility location
Online median

Cite this

@article{4bdcf095547d4bdfa347fb697ecf5220,

title = "Online median problem and its competitive algorithm analysis",

abstract = "Based on the actual constrain in locating facility, that is, the decision-maker must determine where to locate the initial facilities when the final number of facilities is uncertain, and, the constructed facilities can not be removed when the new facility is built, we studies the dynamics facility location problem with the uncertain number of facilities from the online theory view. We present a polynomial competitive algorithm, whose competitive ratio is better than the existed results.",

keywords = "Algorithm, Competitive ratio, Facility location, Online median",

author = "Dai, \{Wen Qiang\} and Xu, \{Yin Feng\} and He, \{Guo Liang\}",

year = "2007",

month = oct,

language = "英语",

volume = "27",

pages = "159--164",

journal = "Xitong Gongcheng Lilun yu Shijian/System Engineering Theory and Practice",

issn = "1000-6788",

publisher = "Systems Engineering Society of China",

number = "10",

}

TY - JOUR

T1 - Online median problem and its competitive algorithm analysis

AU - Dai, Wen Qiang

AU - Xu, Yin Feng

AU - He, Guo Liang

PY - 2007/10

Y1 - 2007/10

N2 - Based on the actual constrain in locating facility, that is, the decision-maker must determine where to locate the initial facilities when the final number of facilities is uncertain, and, the constructed facilities can not be removed when the new facility is built, we studies the dynamics facility location problem with the uncertain number of facilities from the online theory view. We present a polynomial competitive algorithm, whose competitive ratio is better than the existed results.

AB - Based on the actual constrain in locating facility, that is, the decision-maker must determine where to locate the initial facilities when the final number of facilities is uncertain, and, the constructed facilities can not be removed when the new facility is built, we studies the dynamics facility location problem with the uncertain number of facilities from the online theory view. We present a polynomial competitive algorithm, whose competitive ratio is better than the existed results.

KW - Algorithm

KW - Competitive ratio

KW - Facility location

KW - Online median

UR - https://www.scopus.com/pages/publications/36549007417

M3 - 文章

AN - SCOPUS:36549007417

SN - 1000-6788

VL - 27

SP - 159

EP - 164

JO - Xitong Gongcheng Lilun yu Shijian/System Engineering Theory and Practice

JF - Xitong Gongcheng Lilun yu Shijian/System Engineering Theory and Practice

IS - 10

ER -

Online median problem and its competitive algorithm analysis

Abstract

Keywords

Other files and links

Fingerprint

Cite this