research
∙
03/22/2023
On Fair Allocation of Indivisible Goods to Submodular Agents
We consider the problem of fair allocation of indivisible goods to agent...
share
research
∙
11/25/2022
On picking sequences for chores
We consider the problem of allocating m indivisible chores to n agents w...
research
∙
05/16/2022
Fair Shares: Feasibility, Domination and Incentives
We consider fair allocation of a set M of indivisible goods to n equally...
research
∙
05/11/2022
Improved maximin fair allocation of indivisible items to three agents
We consider the problem of approximate maximin share (MMS) allocation of...
research
∙
04/14/2022
On allocations that give intersecting groups their fair share
We consider item allocation to individual agents who have additive valua...
research
∙
12/11/2021
A tight bound for the clique query problem in two rounds
We consider a problem introduced by Feige, Gamarnik, Neeman, Rácz and Te...
research
∙
04/11/2021
A tight negative example for MMS fair allocations
We consider the problem of allocating indivisible goods to agents with a...
research
∙
03/07/2021
Fair-Share Allocations for Agents with Arbitrary Entitlements
We consider the problem of fair allocation of indivisible goods to n age...
research
∙
02/26/2021
Are Gross Substitutes a Substitute for Submodular Valuations?
The class of gross substitutes (GS) set functions plays a central role i...
research
∙
02/09/2021
Best-of-Both-Worlds Fair-Share Allocations
We consider the problem of fair allocation of indivisible items among n ...
research
∙
06/16/2020
Quantitative Group Testing and the rank of random matrices
Given a random Bernoulli matrix A∈{0,1}^m× n, an integer 0< k < n and th...
research
∙
04/26/2020
How to hide a clique?
In the well known planted clique problem, a clique (or alternatively, an...
research
∙
02/25/2020
Fair and Truthful Mechanisms for Dichotomous Valuations
We consider the problem of allocating a set on indivisible items to play...
research
∙
11/19/2019
On the path partition number of 6-regular graphs
A path partition (also referred to as a linear forest) of a graph G is a...
research
∙
09/25/2019
A New Approach to Fair Distribution of Welfare
We consider transferable-utility profit-sharing games that arise from se...
research
∙
09/08/2019
Target Set Selection for Conservative Populations
Let G = (V,E) be a graph on n vertices, where d_v denotes the degree of ...
research
∙
01/23/2019
A randomized strategy in the mirror game
Alice and Bob take turns (with Alice playing first) in declaring numbers...
research
∙
12/31/2018
Tighter bounds for online bipartite matching
We study the online bipartite matching problem, introduced by Karp, Vazi...
research
∙
09/18/2018
Finding cliques using few probes
Consider algorithms with unbounded computation time that probe the entri...
research
∙
07/25/2018
A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time
We consider the classic scheduling problem of minimizing the total weigh...
research
∙
03/14/2018
Max-Min Greedy Matching
A bipartite graph G(U,V;E) that admits a perfect matching is given. One ...
research
∙
06/19/2014