Arrow Research search

Author name cluster

Adam L. Buchsbaum

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers
2 author rows

Possible papers

12

TCS Journal 2003 Journal Article

On finding common neighborhoods in massive graphs

  • Adam L. Buchsbaum
  • Raffaele Giancarlo
  • Jeffery R. Westbrook

We consider the problem of finding pairs of vertices that share large common neighborhoods in massive graphs. We prove lower bounds on the resources needed to solve this problem on resource-bounded models of computation. In streaming models, in which algorithms can access the input only a constant number of times and only sequentially, we show that, even with randomization, any algorithm that determines if there exists any pair of vertices with a large common neighborhood must essentially store and process the input graph off line. In sampling models, in which algorithms can only query an oracle for the common neighborhoods of specified vertex pairs, we show that any algorithm must sample almost every pair of vertices for their respective common neighborhoods.

Details DOI

STOC Conference 2003 Conference Paper

OPT versus LOAD in dynamic storage allocation

  • Adam L. Buchsbaum
  • Howard J. Karloff
  • Claire Mathieu
  • Nick Reingold
  • Mikkel Thorup

DYNAMIC STORAGE ALLOCATION is the problem of packing given axis-aligned rectangles into a horizontal strip of minimum height by sliding the rectangles vertically but not horizontally. Where L=LOAD is the maximum sum of heights of rectangles that intersect any vertical line and OPT is the minimum height of the enclosing strip, it is obvious that OPT≥LOAD ; previous work showed that OPT≤ 3• LOAD . We continue the study of the relationship between OPT and LOAD , proving that OPT=L+O((h max /L) 1/7 )L , where h max is the maximum job height. Conversely, we prove that for any ε>0 , there exists a c>0 such that for all sufficiently large integers h max , there is a DYNAMIC STORAGE ALLOCATION instance with maximum job height h max , maximum load at most L , and OPT≥ L+c(h max /L) 1/2+ε L , for infinitely many integers L . En route, we construct several new polynomial-time approximation algorithms for DYNAMIC STORAGE ALLOCATION.

Details

FOCS Conference 1992 Conference Paper

Data Structural Bootstrapping, Linear Path Compression, and Catenable Heap Ordered Double Ended Queues

  • Adam L. Buchsbaum
  • Rajamani Sundar
  • Robert Endre Tarjan

The authors provide an efficient implementation of catenable mindeques. To prove that the resulting data structure achieves constant amortized time per operation, they consider order preserving path compression. They prove a linear bound on deque ordered spine-only path compression, a case of order persevering path compression employed by the data structure. >

Details
v2026.09.13