Showing 2024Show all
3 papers · 1 filter
cs.DS2024
When to Give Up on a Parallel Implementation
Nathan S. Sheffield, Alek Westover
In the Serial Parallel Decision Problem (SPDP), introduced by Kuszmaul and Westover [SPAA'24], an algorithm receives a series of tasks online, and must choose for each between a se…
cs.CC2024
Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree
Brian Liu, Nathan S. Sheffield, Alek Westover
We study the following generalization of the Hamiltonian cycle problem: Given integers and graph , does there exist a closed walk in that visits every vertex at least…
cs.DS2024
A Nearly Quadratic Improvement for Memory Reallocation
Martin Farach-Colton, William Kuszmaul, Nathan Sheffield +1
In the Memory Reallocation Problem a set of items of various sizes must be dynamically assigned to non-overlapping contiguous chunks of memory. It is guaranteed that the sum of the…