3 citations · 3 across the 5 of their papers we have counts for
7 papers
Online sorting and online TSP: randomized, stochastic, and high-dimensional
Mikkel Abrahamsen, Ioana O. Bercea, Lorenzo Beretta +2
In the online sorting problem, items are revealed one by one and have to be placed (immediately and irrevocably) into empty cells of a size- array. The goal is to minimize t…
Approximate Earth Mover's Distance in Truly-Subquadratic Time
Lorenzo Beretta, Aviad Rubinstein
We design an additive approximation scheme for estimating the cost of the min-weight bipartite matching problem: given a bipartite graph with non-negative edge costs and $\varepsil…
Locally Uniform Hashing
Ioana O. Bercea, Lorenzo Beretta, Jonas Klausen +2
Hashing is a common technique used in data processing, with a strong impact on the time and resources spent on computation. Hashing also affects the applicability of theoretical re…
Online Sorting and Translational Packing of Convex Polygons
Anders Aamand, Mikkel Abrahamsen, Lorenzo Beretta +1
We investigate several online packing problems in which convex polygons arrive one by one and have to be placed irrevocably into a container, while the aim is to minimize the used…
An Optimal Algorithm for Finding Champions in Tournament Graphs
Lorenzo Beretta, Franco Maria Nardini, Roberto Trani +1
A tournament graph is a complete directed graph, which can be used to model a round-robin tournament between players. In this paper, we address the problem of finding a champio…
Better Sum Estimation via Weighted Sampling
Lorenzo Beretta, Jakub Tětek
Given a large set where each item has weight , we want to estimate the total weight to within factor of with some consta…
Online Packing to Minimize Area or Perimeter
Mikkel Abrahamsen, Lorenzo Beretta
We consider online packing problems where we get a stream of axis-parallel rectangles. The rectangles have to be placed in the plane without overlapping, and each rectangle must be…