Combinatorial Algorithm for Restricted Max-Min Fair Allocation

Publications associées (31)

À propos
Confidentialité
Mentions légales

Graph Chatbot

Tight 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 Informatik2022

Motif Cut Sparsifiers

Mikhail Kapralov, Mikhail Makarov, Jakab Tardos

A motif is a frequently occurring subgraph of a given directed or undirected graph G (Milo et al.). Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clusterin ...

IEEE COMPUTER SOC2022

Approximate 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 SCIENCE2022

Formula Normalizations in Verification

Viktor Kuncak, Simon Guilloud, Mario Bucev, Dragana Milovancevic

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 ...

2023

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

Akash Kumar

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...

IEEE COMPUTER SOC2022

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Viktor Kuncak, Simon Guilloud

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 ...

Springer2022

Space-Efficient Representations of Graphs

Jakab Tardos

With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a single machine. Many highly successful approaches have emer ...

EPFL2022

Fast deterministic and randomized algorithms for low-rank approximation, matrix functions, and trace estimation

Alice Cortinovis

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 ...

EPFL2022

Geometrical Treatise on the Modelling of 3D Particulate Inclusion-Matrix Microstructures with an Application to Historical Stone Masonry Walls

Mahmoud S. M. Shaqfa

As historical stone masonry structures are vulnerable and prone to damage in earthquakes, investigating their structural integrity is important to reduce injuries and casualties while preserving their historical value. Stone masonry is a composite material ...

EPFL2022

Variational Methods For Continuous-Domain Inverse Problems: the Quest for the Sparsest Solution

Thomas Jean Debarre

The goal of this thesis is to study continuous-domain inverse problems for the reconstruction of sparse signals and to develop efficient algorithms to solve such problems computationally. The task is to recover a signal of interest as a continuous function ...

EPFL2022

Page 3 sur 4

Geometrical Treatise on the Modelling of 3D Particulate Inclusion-Matrix Microstructures with an Application to Historical Stone Masonry Walls

Mahmoud S. M. Shaqfa

EPFL2022