Faster kinetic heaps and their use in broadcast scheduling

Haim Kaplan, Robert E. Tarjan, Kostas Tsioutsiouliklis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

Abstract

We describe several implementations of the kinetic heap, a heap (priority gueue) 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages836-844
Number of pages9
StatePublished - 2001
Event2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States
Duration: Apr 30 2001May 1 2001

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other2001 Operating Section Proceedings, American Gas Association
CountryUnited States
CityDallas, TX
Period4/30/015/1/01

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Keywords

  • Algorithms
  • Theory

Fingerprint Dive into the research topics of 'Faster kinetic heaps and their use in broadcast scheduling'. Together they form a unique fingerprint.

Cite this