101 citations · 211 across the 45 of their papers we have counts for
51 papers
Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations
Hannaneh Akrami, Kurt Mehlhorn, Masoud Seddighin +1
We consider the problem of guaranteeing maximin-share (MMS) when allocating a set of indivisible items to a set of agents with fractionally subadditive (XOS) valuations. For XOS va…
Fair and Efficient Allocation of Indivisible Chores with Surplus
Hannaneh Akrami, Bhaskar Ray Chaudhury, Jugal Garg +2
We study fair division of indivisible chores among agents with additive disutility functions. Two well-studied fairness notions for indivisible items are envy-freeness up to on…
Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability
Hannaneh Akrami, Bhaskar Ray Chaudhury, Martin Hoefer +6
We study the problem of allocating a set of indivisible goods among a set of agents with \emph{2-value additive valuations}. In this setting, each good is valued either or $p/q…
Noise-induced network topologies
Frederic Folz, Kurt Mehlhorn, Giovanna Morigi
We analyze transport on a graph with multiple constraints and where the weight of the edges connecting the nodes is a dynamical variable. The network dynamics results from the inte…
Improving Order with Queues
Andreas Karrenbauer, Kurt Mehlhorn, Pranabendu Misra +4
Given a sequence of numbers and parallel First-in-First-Out (FIFO) queues, how close can one bring the sequence to sorted order? It is known that queues suffice to sort…
EFX Allocations: Simplifications and Improvements
Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury +3
The existence of EFX allocations is a fundamental open problem in discrete fair division. Given a set of agents and indivisible goods, the goal is to determine the existence of an…
Physarum Inspired Dynamics to Solve Semi-Definite Programs
Yuan Gao, Hamidreza Kamkari, Andreas Karrenbauer +2
Physarum Polycephalum is a slime mold that can solve shortest path problems. A mathematical model based on Physarum's behavior, known as the Physarum Directed Dynamics, can solve p…
Interplay of periodic dynamics and noise: insights from a simple adaptive system
Frederic Folz, Kurt Mehlhorn, Giovanna Morigi
We study the dynamics of a simple adaptive system in the presence of noise and periodic damping. The system is composed by two paths connecting a source and a sink, the dynamics is…
Maximizing Nash Social Welfare in 2-Value Instances
Hannaneh Akrami, Bhaskar Ray Chaudhury, Martin Hoefer +6
We consider the problem of maximizing the Nash social welfare when allocating a set of indivisible goods to a set of agents. We study instances, in whic…
Nash Social Welfare for 2-value Instances
Hannaneh Akrami, Bhaskar Ray Chaudhury, Kurt Mehlhorn +2
This paper is merged with arXiv:2107.08965v2. We refer the reader to the full and updated version. We study the problem of allocating a set of indivisible goods among agents with 2…
Improving EFX Guarantees through Rainbow Cycle Number
Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn +2
We study the problem of fairly allocating a set of indivisible goods among agents with additive valuations. Envy-freeness up to any good (EFX) is arguably the most compelling f…
Physarum-Inspired Multi-Commodity Flow Dynamics
Vincenzo Bonifaci, Enrico Facca, Frederic Folz +6
In wet-lab experiments, the slime mold Physarum polycephalum has demonstrated its ability to solve shortest path problems and to design efficient networks. For the shortest path pr…
The Maximum-Level Vertex in an Arrangement of Lines
Dan Halperin, Sariel Har-Peled, Kurt Mehlhorn +2
Let be a set of lines in the plane, not necessarily in general position. We present an efficient algorithm for finding all the vertices of the arrangement of maximum…
EFX Exists for Three Agents
Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn
We study the problem of distributing a set of indivisible items among agents with additive valuations in a manner. The fairness notion under consideration is Envy-f…
Trustworthy Graph Algorithms
Mohammad Abdulaziz, Kurt Mehlhorn, Tobias Nipkow
The goal of the LEDA project was to build an easy-to-use and extendable library of correct and efficient data structures, graph algorithms and geometric algorithms. We report on th…
A Little Charity Guarantees Almost Envy-Freeness
Bhaskar Ray Chaudhury, Tellikepalli Kavitha, Kurt Mehlhorn +1
Fair division of indivisible goods is a very well-studied problem. The goal of this problem is to distribute goods to agents in a "fair" manner, where every agent has a val…
Convergence of the Non-Uniform Directed Physarum Model
Enrico Facca, Andreas Karrenbauer, Pavel Kolev +1
The directed Physarum dynamics is known to solve positive linear programs: minimize subject to and for a positive cost vector . The directed Physarum…
Ratio-Balanced Maximum Flows
Hannaneh Akrami, Kurt Mehlhorn, Tommy Odland
When a loan is approved for a person or company, the bank is subject to \emph{credit risk}; the risk that the lender defaults. To mitigate this risk, a bank will require some form…
Convergence of the Non-Uniform Physarum Dynamics
Andreas Karrenbauer, Pavel Kolev, Kurt Mehlhorn
Let , , and . We show under fairly general conditions that the non-uniform Physarum dynamics \[ \dot{x}_…
The Query Complexity of a Permutation-Based Variant of Mastermind
Peyman Afshani, Manindra Agrawal, Benjamin Doerr +3
We study the query complexity of a permutation-based variant of the guessing game Mastermind. In this variant, the secret is a pair which consists of a binary string $z \in…
Combinatorial Algorithms for General Linear Arrow-Debreu Markets
Bhaskar Ray Chaudhury, Kurt Mehlhorn
We present a combinatorial algorithm for determining the market clearing prices of a general linear Arrow-Debreu market, where every agent can own multiple goods. The existing comb…
Multi-finger binary search trees
Parinya Chalermsook, Mayank Goswami, László Kozma +2
We study multi-finger binary search trees (BSTs), a far-reaching extension of the classical BST model, with connections to the well-studied -server problem. Finger search is a p…
On testing substitutability
Cosmina Croitoru, Kurt Mehlhorn
The papers~\cite{hatfimmokomi11} and~\cite{azizbrilharr13} propose algorithms for testing whether the choice function induced by a (strict) preference list of length over a uni…
On Fair Division of Indivisible Items
Bhaskar Chaudhury, Yun Kuen Cheung, Jugal Garg +3
We consider the task of assigning indivisible goods to a set of agents in a fair manner. Our notion of fairness is Nash social welfare, i.e., the goal is to maximize the geometric…