101 citations · 211 across the 45 of their papers we have counts for
5 papers · 1 filter
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…