4 papers · 1 filter
A Tight ()-Approximation Algorithm for Demand Strip Packing
Franziska Eberle, Felix Hommelsheim, Malin Rau +1
We consider the Demand Strip Packing problem (DSP), in which we are given a set of jobs, each specified by a processing time and a demand. The task is to schedule all jobs such tha…
ShockHash: Towards Optimal-Space Minimal Perfect Hashing Beyond Brute-Force
Hans-Peter Lehmann, Peter Sanders, Stefan Walzer
A minimal perfect hash function (MPHF) maps a set of keys to the first integers without collisions. There is a lower bound of bits of space needed…
Sliding Block Hashing (Slick) -- Basic Algorithmic Ideas
Hans-Peter Lehmann, Peter Sanders, Stefan Walzer
We present {\bf Sli}ding Blo{\bf ck} Hashing (Slick), a simple hash table data structure that combines high performance with very good space efficiency. This preliminary report out…
Optimal Uncoordinated Unique IDs
Peter C. Dillinger, Martín Farach-Colton, Guido Tagliavini +1
In the Uncoordinated Unique Identifiers Problem (UUIDP) there are independent instances of an algorithm that generates IDs from a universe , and…