A Randomized -Competitive Algorithm for the Online Connected Facility Location Problem

被引：0

作者：

San Felice, Mario Cesar ^{[1
]}

Williamson, David P. ^{[2
]}

Lee, Orlando ^{[1
]}

机构：

[1] Univ Estadual Campinas, Inst Comp, BR-13083852 Campinas, SP, Brazil

[2] Cornell Univ, Sch Operat Res & Informat Engn, Ithaca, NY 14853 USA

来源：

ALGORITHMICA | 2016年 / 76卷 / 04期

基金：

美国国家科学基金会; 巴西圣保罗研究基金会;

关键词：

Online algorithms; Competitive analysis; Connected facility location; Steiner tree; Approximation algorithms; Randomized algorithms; APPROXIMATION ALGORITHMS;

D O I：

10.1007/s00453-016-0115-1

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The Connected Facility Location (CFL) is a network design problem that arises from a combination of the Uncapacitated Facility Location (FL) and the Steiner Tree (ST) problems. The Online Connected Facility Location problem (OCFL) is an online version of the CFL. San Felice et al. (2014) presented a randomized algorithm for the OCFL and proved that it is -competitive, where n is the number of clients. That algorithm combines the sample-and-augment framework of Gupta, Kumar, Pal, and Roughgarden with previous algorithms for the Online Facility Location (OFL) and the Online Steiner Tree (OST) problems. In this paper we use a more precise analysis to show that the same algorithm is -competitive. Since there is a lower bound of for this problem, our result achieves the best possible competitive ratio, asymptotically.

引用

页码：1139 / 1157

页数：19

共 23 条

[1]

[Anonymous], 2010, The Design of Approximation Algorithms, DOI DOI 10.1017/CBO9780511921735

[2]

Bartal Y, 1995, J COMPUT SYST SCI, V51, P341, DOI 10.1006/jcss.1995.1073

[3]

Borodin A., 1998, Online Computation and Competitive Analysis

[4] The Design of Competitive Online Algorithms via a Primal Dual Approach [J].

Buchbinder, Niv ;

Naor, Joseph .

FOUNDATIONS AND TRENDS IN THEORETICAL COMPUTER SCIENCE, 2007, 3 (2-3) :93-263

[5] AN OPTIMAL BIFACTOR APPROXIMATION ALGORITHM FOR THE METRIC UNCAPACITATED FACILITY LOCATION PROBLEM [J].

Byrka, Jaroslaw ;

Aardal, Karen .

SIAM JOURNAL ON COMPUTING, 2010, 39 (06) :2212-2231

[6] Connected facility location via random facility sampling and core detouring [J].

Eisenbrand, Friedrich ;

Grandoni, Fabrizio ;

Rothvoss, Thomas ;

Schafer, Guido .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2010, 76 (08) :709-726

[7]

Fotakis Dimitris, 2011, SIGACT News, V42, P97, DOI 10.1145/1959045.1959065

[8] A primal-dual algorithm for online non-uniform facility location [J].

Fotakis, Dimitris .

JOURNAL OF DISCRETE ALGORITHMS, 2007, 5 (01) :141-148

[9] On the competitive ratio for Online Facility Location [J].

Fotakis, Dimitris .

ALGORITHMICA, 2008, 50 (01) :1-57

[10] Approximation via cost sharing:: Simpler and better approximation algorithms for network design [J].

Gupta, Anupam ;

Kumar, Amit ;

Pal, Martin ;

Roughgarden, Tim .

JOURNAL OF THE ACM, 2007, 54 (03)

← 1 2 3 →