A Lower Bound for Scheduling Mechanisms

被引：38

作者：

Christodoulou, George ^{[1
]}

Koutsoupias, Elias ^{[2
]}

Vidali, Angelina ^{[2
]}

机构：

[1] Max Planck Inst Informat, Saarbrucken, Germany

[2] Univ Athens, Dept Informat, Athens, Greece

来源：

ALGORITHMICA | 2009年 / 55卷 / 04期

关键词：

Algorithmic mechanism design; Scheduling unrelated machines; Lower bound; DESIGN;

D O I：

10.1007/s00453-008-9165-3

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We study the mechanism design problem of scheduling tasks on n unrelated machines in which the machines are the players of the mechanism. The problem was proposed and studied in the seminal paper of Nisan and Ronen on algorithmic mechanism design, where it was shown that the approximation ratio of mechanisms is between 2 and n. We improve the lower bound to 1 + root 2 for 3 or more machines.

引用

页码：729 / 740

页数：12

共 24 条

[1]

[Anonymous], 22 ANN S THEOR ASP C

[2]

[Anonymous], THESIS U SAARLANDES

[3]

Archer A, 2003, SIAM PROC S, P205

[4]

Archer A, 2001, ANN IEEE SYMP FOUND, P482

[5]

ARCHER A, 2004, THESIS CORNELL U

[6]

Babaioff M., 2005, AAAI, V5, P241

[7]

Bartal Y., 2003, P 9 C THEOR ASP RAT, P72, DOI DOI 10.1145/846241.846250

[8]

Briest P., 2005, STOC 05 P THIRTYSEVE, P39, DOI DOI 10.1145/1060590.1060597

[9]

Christodoulou G, 2007, PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P1163

[10]

Christodoulou G, 2007, LECT NOTES COMPUT SC, V4596, P40

← 1 2 3 →