Bucket game with applications to set multicover and dynamic page migration

被引：0

作者：

Bienkowski, M ^{[1
]}

Byrka, J

机构：

[1] Univ Gesamthsch Paderborn, Int Grad Sch Dynam Intelligent Syst, D-4790 Paderborn, Germany

[2] Ctr Wiskunde & Informat, NL-1098 SJ Amsterdam, Netherlands

来源：

ALGORITHMS - ESA 2005 | 2005年 / 3669卷

关键词：

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present a simple two-person Bucket Game, based on throwing balls into buckets, and we discuss possible players' strategies. We use these strategies to create an approximation algorithm for a generalization of the well known Set Cover problem, where we need to cover each element by at least k sets. Furthermore, we apply these strategies to construct a randomized algorithm for Dynamic Page Migration problem achieving the optimal competitive ratio against an oblivious adversary.

引用

页码：815 / 826

页数：12

共 14 条

[1]

Bartal Y, 1997, PROCEEDINGS OF THE EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P43

[2]

BENDAVID S, 1990, PROCEEDINGS OF THE TWENTY SECOND ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, P379, DOI 10.1145/100216.100268

[3]

BERMAN P, 2004, P 7 INT WORKSH APPR, P39

[4]

BIENKOWSKI M, 2005, P 22 S THEOR ASP COM, P365

[5]

Bienkowski M., 2004, P 16 ACM S PAR ALG A, P64

[6]

Black D.L., 1989, COMPETITIVE ALGORITH

[7]

Guha S, 1998, P 9 ACM SIAM S DISCR, P228

[8]

Johnson D.S., 1973, J COMPUT SYST SCI, P38, DOI DOI 10.1145/800125.804034

[9] RATIO OF OPTIMAL INTEGRAL AND FRACTIONAL COVERS [J].

LOVASZ, L .

DISCRETE MATHEMATICS, 1975, 13 (04) :383-390

[10]

Mahdian M, 2002, LECT NOTES COMPUT SC, V2462, P229

← 1 2 →