𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Optimal Bounds for the Predecessor Problem and Related Problems

✍ Scribed by Paul Beame; Faith E. Fich

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
269 KB
Volume
65
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We obtain matching upper and lower bounds for the amount of time to find the predecessor of a given element among the elements of a fixed compactly stored set. Our algorithms are for the unit-cost word RAM with multiplication and are extended to give dynamic algorithms. The lower bounds are proved for a large class of problems, including both static and dynamic predecessor problems, in a much stronger communication game model, but they apply to the cell probe and RAM models.

πŸ“œ SIMILAR VOLUMES

Asymptotically Optimal Bounds for OBDDs
Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems
✍ Beate Bollig; Ingo Wegener πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 262 KB

Ordered binary decision diagrams (OBDDs) are nowadays the most common dynamic data structure or representation type for Boolean functions. Among the many areas of application are verification, model checking, and computer aided design. For many functions it is easy to estimate the OBDD size but asym

Generalized solution of interdiffusion p
Generalized solution of interdiffusion problem: Optimal approach for multicomponent bounded systems
✍ Danielewski, M.; Filipek, R. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 797 KB

Darken's phenomenological scheme for diffusion in binary systems is used for a description of interdiffusion in multicomponent ( r 2 2) mixtures. The mathematical model of interdiffusion in the bounded mixture (i.e., layer of finite thickness) showing constant concentration (e.g., in solid or liquid

Uniqueness theorems for a nonlinear Tric
Uniqueness theorems for a nonlinear Tricomi problem and the related evolution problem
✍ N. A. Lar'kin; M. Schneider πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 355 KB

## Abstract We consider an initial‐boundary value problem for the non‐linear evolution equation equation image in a cylinder __Q~t~__ = Ξ© Γ— (0, __t__), where __T__[__u__] = __yu~xx~__ + __u~yy~__ is the Tricomi operator and __l__(__u__) a special differential operator of first order. In [10] we p

Branch and bound methods for a search pr
Branch and bound methods for a search problem
✍ Alan R. Washburn πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 116 KB

The problem of searching for randomly moving targets such as children and submarines is known to be fundamentally difficult, but finding efficient methods for generating optimal or near optimal solutions is nonetheless an important practical problem. This paper investigates the efficiency of Branch