Publication
New Results in Integer and Lattice Programming
Related publications (250)
Discrete Optimal Transport with Independent Marginals is #P-Hard
Daniel Kuhn, Soroosh Shafieezadeh Abadeh, Bahar Taskesen
We study the computational complexity of the optimal transport problem that evaluates the Wasser- stein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in th ...
2022Fast deterministic and randomized algorithms for low-rank approximation, matrix functions, and trace estimation
In this thesis we propose and analyze algorithms for some numerical linear algebra tasks: finding low-rank approximations of matrices, computing matrix functions, and estimating the trace of matrices.In the first part, we consider algorithms for building l ...
EPFL2022Streaming and Matching Problems with Submodular Functions
Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...
EPFL2022On Polynomial Algorithms for Normalizing Formulas
Viktor Kuncak, Simon Guilloud, Mario Bucev
We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem ...
2022Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs
Adam Teodor Polak, Alexandra Anna Lassota
We solve the Bin Packing problem in O^*(2^k) time, where k is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. O ...
Schloss Dagstuhl – Leibniz-Zentrum fur Informatik2022Approximate CVPp in time 2(0.802n)
Friedrich Eisenbrand, Moritz Andreas Venzin
We show that a constant factor approximation of the shortest and closest lattice vector problem in any l(p)-norm can be computed in time 2((0.802 + epsilon)n). This matches the currently fastest constant factor approximation algorithm for the shortest vect ...
ACADEMIC PRESS INC ELSEVIER SCIENCE2022On the Mordell-Weil lattice of y(2) = x(3) + bx plus t(3n+1) in characteristic 3
We study the elliptic curves given by y(2) = x(3) + bx + t(3n+1) over global function fields of characteristic 3 ; in particular we perform an explicit computation of the L-function by relating it to the zeta function of a certain superelliptic curve u(3) ...
SPRINGER INT PUBL AG2022Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time
We present a quasilinear time algorithm to decide the word problem on a natural algebraic structures we call orthocomplemented bisemilattices, a subtheory of boolean algebra. We use as a base a variation of Hopcroft, Ullman and Aho algorithm for tree isomo ...
Springer2022A smooth basis for atomistic machine learning
Michele Ceriotti, Kevin Kazuki Huguenin-Dumittan, Filippo Bigi
Machine learning frameworks based on correlations of interatomic positions begin with a discretized description of the density of other atoms in the neighborhood of each atom in the system. Symmetry considerations support the use of spherical harmonics to ...
AIP Publishing2022A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine
Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. The input consists of a set of jobs, characterized by their processing times, release time ...
ASSOC COMPUTING MACHINERY2021