Concept
Application sous-linéaire
Publications associées (21)
Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost
We study the basic problem of assigning memoryless workers to tasks with dynamically changing demands. Given a set of w workers and a multiset T ⊆ [t] of |T| = w tasks, a memoryless worker-task assignment function is any function ϕ that assigns the workers ...
Schloss Dagstuhl -- Leibniz-Zentrum fur Informatik2022On compact representations of Voronoi cells of lattices
Matthias Schymura, Christoph Hunkenschröder
In a seminal work, Micciancio and Voulgaris (SIAM J Comput 42(3):1364-1391, 2013) described a deterministic single-exponential time algorithm for the closest vector problem (CVP) on lattices. It is based on the computation of the Voronoi cell of the given ...
SPRINGER HEIDELBERG2020On compact representations of Voronoi cells of lattices
Matthias Schymura, Christoph Hunkenschröder
In a seminal work, Micciancio & Voulgaris (2010) described a deterministic single-exponential time algorithm for the Closest Vector Problem (CVP) on lattices. It is based on the computation of the Voronoi cell of the given lattice and thus may need exponen ...
SPRINGER INTERNATIONAL PUBLISHING AG2018