Windows scheduling problems arise in minimizing the bandwidth required in push systems. In addition, the windows scheduling problems arise in minimizing the startup delay for a fixed bandwidth in media-on-demand systems. A windows scheduling problem is defined by the positive integers w_1,w_2,...,w_n and h . The window w_i is associated with page i and h is the number of slotted channels available for broadcasting the pages. A schedule that solves the problem assigns pages to slots such that the gap between any two consecutive appearances of page i is at most w_i slots. We study two optimization problems. (i) The optimal windows scheduling problem: given w_1,...,w_n find a schedule in which h is minimized. (ii) The optimal harmonic windows scheduling problem: given h find a schedule for the windows w_i = i in which n is maximized. For the optimal windows scheduling problem we present an algorithm that constructs asymptotically close to optimal schedules and for the optimal harmonic windows scheduling problem, we show how to achieve the largest known n's for all values of h. This is joint work with Amotz Bar-Noy.

Brief Bio

Richard E. Ladner, Professor, graduated from St. Mary's College of California with a B.S. in 1965 and received a Ph.D. in mathematics from the University of California, Berkeley in 1971, at which time he joined the faculty of the University of Washington. In addition to his appointment in the Department of Computer Science and Engineering, he is an Adjunct Professor in the Department of Electrical Engineering.

His research interests are in theoretical computer science. He is currently investigating design and analysis of algorithms, both parallel and sequential. He has a particular interest in the cache performance of algorithms. He has continuing interests in automata based computational complexity theory, distributed computing, and data compression.

He has supervised or co-supervised thirteen students on their Ph.D. dissertations and five on their M.S. theses. He was a Guggenheim Fellow in 1985-86 and a Fulbright in 1993. He has served as an Area Editor for the Journal of the Association of Computing Machinery and and Editor for SIAM Journal on Computing. He is currently an Associate Editor of the Journal of Computer and System Sciences. He is a Fellow of the ACM.