Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Bounding the Fragmentation of B-Trees Subject to Batched Insertions
Michael A. Bender, Aaron Bernstein, Nairen Cao +5
The issue of internal fragmentation in data structures is a fundamental challenge in database design. A seminal result of Yao in this field shows that evenly splitting the leaves o…
cs.DS2024
Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
Vikrant Ashvinkumar, Aaron Bernstein, Adam Karczmarz
In the restricted shortest paths problem, we are given a graph whose edges are assigned two non-negative weights: lengths and delays, a source , and a delay threshold . T…
cs.DS2024
Low Sensitivity Hopsets
Vikrant Ashvinkumar, Aaron Bernstein, Chengyuan Deng +2
Given a weighted graph , a -hopset is an edge set such that for any , where can reach in , there is a path from to in $G \…