SELF-IMPROVING ALGORITHMS

被引:22
作者
Ailon, Nir [1 ]
Chazelle, Bernard [2 ]
Clarkson, Kenneth L. [3 ]
Liu, Ding [2 ]
Mulzer, Wolfgang [2 ]
Seshadhri, C. [3 ]
机构
[1] Technion Israel Inst Technol, Fac Comp Sci, Haifa, Israel
[2] Princeton Univ, Dept Comp Sci, Princeton, NJ 08544 USA
[3] IBM Almaden Res Ctr, San Jose, CA USA
基金
美国国家科学基金会;
关键词
average case analysis; Delaunay triangulation; low entropy; sorting; LIST UPDATE; TIME;
D O I
10.1137/090766437
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We investigate ways in which an algorithm can improve its expected performance by fine-tuning itself automatically with respect to an unknown input distribution D. We assume here that D is of product type. More precisely, suppose that we need to process a sequence I-1, I-2, ... of inputs I = (x(1), x(2), ... , x(n)) of some fixed length n, where each x(i) is drawn independently from some arbitrary, unknown distribution D-i. The goal is to design an algorithm for these inputs so that eventually the expected running time will be optimal for the input distribution D = Pi(i) D-i. We give such self-improving algorithms for two problems: (i) sorting a sequence of numbers and (ii) computing the Delaunay triangulation of a planar point set. Both algorithms achieve optimal expected limiting complexity. The algorithms begin with a training phase during which they collect information about the input distribution, followed by a stationary regime in which the algorithms settle to their optimized incarnations.
引用
收藏
页码:350 / 375
页数:26
相关论文
共 46 条
[1]   Instance-Optimal Geometric Algorithms [J].
Afshani, Peyman ;
Barbay, Jeremy ;
Chan, Timothy M. .
2009 50TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: FOCS 2009, PROCEEDINGS, 2009, :129-138
[2]  
Agarwal P., 1998, ADV DISCRETE COMPUTA, V23, P1
[3]   A LINEAR-TIME ALGORITHM FOR COMPUTING THE VORONOI DIAGRAM OF A CONVEX POLYGON [J].
AGGARWAL, A ;
GUIBAS, LJ ;
SAXE, J ;
SHOR, PW .
DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (06) :591-604
[4]   Average case analyses of list update algorithms, with applications to data compression [J].
Albers, S ;
Mitzenmacher, M .
ALGORITHMICA, 1998, 21 (03) :312-318
[5]  
Albers S, 1998, LECT NOTES COMPUT SC, V1442, P13, DOI 10.1007/BFb0029563
[6]   SELF-ORGANIZING BINARY SEARCH TREES [J].
ALLEN, B ;
MUNRO, I .
JOURNAL OF THE ACM, 1978, 25 (04) :526-535
[7]  
Alon N., 2000, WILEY INTERSCIENCE S
[8]  
[Anonymous], 1998, Online Computation and Competitive Analysis
[9]  
[Anonymous], 1991, ELEMENTS INFORM THEO, DOI [DOI 10.1002/0471200611, 10.1002/0471200611]
[10]   Self-customized BSP trees for collision detection [J].
Ar, S ;
Chazelle, B ;
Tal, A .
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2000, 15 (1-3) :91-102