Randomized algorithms for online bounded bidding

被引：2

作者：

Epstein, Leah ^{[1
]}

Levin, Asaf ^{[2
]}

机构：

[1] Univ Haifa, Dept Math, IL-31905 Haifa, Israel

[2] Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel

来源：

INFORMATION PROCESSING LETTERS | 2010年 / 110卷 / 12-13期

关键词：

On-line algorithms; Online bidding; Competitive analysis;

D O I：

10.1016/j.ipl.2010.03.016

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In the online bidding problem, a bidder is trying to guess a positive number T. by placing bids until the value of the bid is at least T. The bidder is charged with the sum of the bids. In the bounded online bidding problem, a parameter k is given, and the bidder is charged only with the largest k bids. It is known that the online bidding problem admits a 4-competitive deterministic algorithm, and an e-competitive randomized algorithm, and these results are best possible. The deterministic best possible competitive ratio for the online bounded bidding problem is also known, for any value of k. We study the randomized bounded online bidding problem, and show that for any k > 2, randomization is helpful, that is, it allows to design an algorithm of a smaller competitive ratio compared to the best deterministic algorithm. In contrast, for k = 2, we show a lower bound of 2 on the competitive ratio of any randomized algorithms, matching the upper bound achieved by a trivial deterministic algorithm, which tests all possible bids sequentially. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：503 / 506

页数：4

共 6 条

[1] On-line routing of virtual circuits with applications to load balancing and machine scheduling [J].