Dynamic Monotone Priorities on Planar Sets (Extended Abstract).

Abstract

A monotonic priority set is a new data structure which supports maximum-finding and deletions over a set of weighted points in the plane. Global updates to the weights can also be made, incrementing the weights of all points above a given threshold in one of the coordinates. The weights are assumed to be always monotonic in both coordinates. An efficient implementation of this structure is presented and two main applications are described. The first is to the problem of optimal assembly of code for computers with two kinds of jump instruction: long and short. The task in the second application is the implementation of a queuing discipline based on the ranks with respect to two different criteria.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1985
Accession Number
ADA158610

Entities

People

  • M. J. Fischer
  • M. S. Paterson

Organizations

  • Yale University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Assembly
  • Classification
  • Computer Science
  • Computers
  • Contracts
  • Engineering
  • Instructions
  • Military Research
  • Numbers
  • Organizational Structure
  • Program Management
  • Real Numbers
  • Standards
  • Technical Information Centers
  • Trees (Data Structures)

Readers

  • Approximation Theory.
  • Mathematical Modeling and Probability Theory.
  • Operations Research