research
∙
08/28/2023
Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations
We consider the problem of guaranteeing a fraction of the maximin-share ...
share
research
∙
05/08/2023
Fair and Efficient Allocation of Indivisible Chores with Surplus
We study fair division of indivisible chores among n agents with additiv...
research
∙
07/22/2022
Maximizing Nash Social Welfare in 2-Value Instances: The Half-Integer Case
We consider the problem of maximizing the Nash social welfare when alloc...
research
∙
07/06/2022
Improving Order with Queues
Patience Sort sorts a sequence of numbers with a minimal number of queue...
research
∙
05/16/2022
EFX Allocations: Simplifications and Improvements
The existence of EFX allocations is a fundamental open problem in discre...
research
∙
07/19/2021
Maximizing Nash Social Welfare in 2-Value Instances
We consider the problem of maximizing the Nash social welfare when alloc...
research
∙
06/28/2021
Nash Social Welfare for 2-value Instances
We study the problem of allocating a set of indivisible goods among agen...
research
∙
03/02/2021
Improving EFX Guarantees through Rainbow Cycle Number
We study the problem of fairly allocating a set of indivisible goods amo...
research
∙
09/03/2020
Physarum Multi-Commodity Flow Dynamics
In wet-lab experiments, the slime mold Physarum polycephalum has demonst...
research
∙
03/01/2020
The Maximum-Level Vertex in an Arrangement of Lines
Let L be a set of n lines in the plane, not necessarily in general posit...
research
∙
02/12/2020
EFX Exists for Three Agents
We study the problem of allocating a set of indivisible items among agen...
research
∙
07/10/2019
A Little Charity Guarantees Almost Envy-Freeness
Fair division of indivisible goods is a very well-studied problem. The g...
research
∙
07/09/2019
Trustworthy Graph Algorithms
The goal of the LEDA project was to build an easy-to-use and extendable ...
research
∙
06/18/2019
Convergence of the Non-Uniform Directed Physarum Model
The directed Physarum dynamics is known to solve positive linear program...
research
∙
02/28/2019
Ratio-Balanced Maximum Flows
When a loan is approved for a person or company, the bank is subject to ...
research
∙
01/22/2019
Convergence of the Non-Uniform Physarum Dynamics
Let c ∈Z^m_> 0, A ∈Z^n× m, and b ∈Z^n. We show under fairly general cond...
research
∙
12/20/2018
The Query Complexity of a Permutation-Based Variant of Mastermind
We study the query complexity of a permutation-based variant of the gues...
research
∙
10/02/2018
Combinatorial Algorithms for General Linear Arrow-Debreu Markets
We present a combinatorial algorithm for determining the market clearing...
research
∙
09/05/2018
Multi-finger binary search trees
We study multi-finger binary search trees (BSTs), a far-reaching extensi...
research
∙
05/19/2018
On testing substitutability
The papers hatfimmokomi11 and azizbrilharr13 propose algorithms for test...
research
∙
05/16/2018