Online Optimization with Uncertain Information

被引：35

作者：

Mahdian, Mohammad ^{[1
]}

Nazerzadeh, Hamid ^{[1
]}

Saberi, Amin ^{[1
]}

机构：

[1] Stanford Univ, Huang Engn Ctr, Stanford, CA 94305 USA

来源：

ACM TRANSACTIONS ON ALGORITHMS | 2012年 / 8卷 / 01期

基金：

美国国家科学基金会;

关键词：

Online algorithms; competitive analysis; online advertising; ALGORITHMS;

D O I：

10.1145/2071379.2071381

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We introduce a new framework for designing online algorithms that can incorporate additional information about the input sequence, while maintaining a reasonable competitive ratio if the additional information is incorrect. Within this framework, we present online algorithms for several problems including allocation of online advertisement space, load balancing, and facility location.

引用

页数：29

共 21 条

[1]

ALBERS S., 2003, MATH PROG

[2]

Alon Noga, 2003, P STOC, P100

[3]

[Anonymous], 2001, Approximation algorithms

[4]

ASCHEUER N., 1998, OPER RES P

[5]

Aspnes J., 1993, Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, P623, DOI 10.1145/167088.167248

[6] On-line generalized Steiner problem [J].

Awerbuch, B ;

Azar, Y ;

Bartal, Y .

THEORETICAL COMPUTER SCIENCE, 2004, 324 (2-3) :313-324

[7] ONLINE LOAD BALANCING [J].

AZAR, Y ;

BRODER, AZ ;

KARLIN, AR .

THEORETICAL COMPUTER SCIENCE, 1994, 130 (01) :73-84

[8]

Azar Yossi., 1996, Online Algorithms, P178, DOI DOI 10.1007/BFB0029569

[9]

BERMAN P., 1997, P 29 ANN ACM S THEOR

[10]

Buchbinder Niv, 2007, P 15 ANN EUR S ALG

← 1 2 3 →