4 papers
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…
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…
Balanced TSP partitioning
Benjamin Aram Berendsohn, Hwi Kim, László Kozma
The traveling salesman problem (TSP) famously asks for a shortest tour that a salesperson can take to visit a given set of cities in any order. In this paper, we ask how much faste…