5 papers · 1 filter
The Sync Heap: Delete First, Ask Questions Later
Benjamin Aram Berendsohn, Egor Gorbachev, László Kozma
Heaps (priority queues) are among the best-studied data structures in computer science. In this paper, we critically revisit the textbook assumption that in the comparison model at…
The price of incrementality in k-center clustering
László Kozma
The -center problem is one of the best-studied and most intuitive clustering formulations. It asks, given a set of points in a metric space, for of the points to be desi…
Optimization with pattern-avoiding input
Benjamin Aram Berendsohn, László Kozma, Michal Opler
Permutation pattern-avoidance is a central concept of both enumerative and extremal combinatorics. In this paper we study the effect of permutation pattern-avoidance on the complex…
Compact representations of pattern-avoiding permutations
László Kozma, Michal Opler
Pattern-avoiding permutations are a central object of study in both combinatorics and theoretical computer science. In this paper we design a data structure that can store any size…
Non-adaptive Bellman-Ford: Yen's improvement is optimal
Jialu Hu, László Kozma
The Bellman-Ford algorithm for single-source shortest paths repeatedly updates tentative distances in an operation called relaxing an edge. In several important applications a non-…