Faster kinetic heaps and their use in broadcast scheduling
Lists
Only you see this
Abstract
We describe several implementations of the kinetic heap, a heap (priority queue) in which the key of each item, instead of being fixed, is a linear function of time. The kinetic heap is a simple example of a kinetic data structure of the kind considered by Basch, Guibas, and Hershberger. Kinetic heaps have many applications in computational geometry, and previous implementations were designed to address these applications. We describe an additional application, to broadcast scheduling. Each of our kinetic heap implementations improves on previous implementations by being simpler or asymptotically faster for some or all applications.
BibTeX
@inproceedings{kaplan2001faster,
author = {Haim Kaplan and Robert Endre Tarjan and Kostas Tsioutsiouliklis},
title = {{Faster kinetic heaps and their use in broadcast scheduling}},
booktitle = {SODA},
year = {2001},
url = {https://openreview.net/forum?id=uO0IM5oSg9Wa},
}Loading related content...