An Optimal Cache-Oblivious Priority Queue and Its Application to Graph Algorithms
We develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and delete-min operations in $O(\frac{1}{B}\log_{M/B}\frac{N}{B})$ amortized memory transfers, whe...
We develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and delete-min operations in $O(\frac{1}{B}\log_{M/B}\frac{N}{B})$ amortized memory transfers, whe...
Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help
We consider the following scheduling problem. The input is a set of jobs with equal processing times, where each job is specified by its release time and deadline. The goal is to determine a single-p...
We consider the following scheduling problem. The input is a set of jobs with equal processing times, where each job is specified by its release time and deadline. The goal is to determine a single-p...
You are not logged in to this journal. Log in
Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets
SIAM J. Comput. Volume 36, Issue 6, pp. 1696-1708 (2007)
Published March 19, 2007
Connotea
CiteULike
del.icio.us
BibSonomy
We establish a relationship between the online mistake-bound model of learning and resource-bounded dimension. This connection is combined with the Winnow algorithm to obtain new results about the density of hard sets under adaptive reductions. This improves previous work of Fu [SIAM J. Comput., 24 (1995), pp. 1082–1090] and Lutz and Zhao [SIAM J. Comput., 30 (2000), pp. 1197–1210], and solves one of Lutz and Mayordomo's “twelve problems in resource-bounded measure” [Bull. Eur. Assoc. Theor. Comput. Sci. EATSC, 68 (1999), pp. 64–80].
©2007 Society for Industrial and Applied Mathematics| History: | Received December 13, 2005; accepted September 20, 2006; published March 19, 2007 |
| Permalink: | http://dx.doi.org/10.1137/050647517 |
KEYWORDS and AMS
PUBLICATION DATA
0097-5397 (print)
1095-7111 (online)
SIAM