6 citations · 13 across the 8 of their papers we have counts for
8 papers
Tight Approximations for Graphical House Allocation
Hadi Hosseini, Andrew McGregor, Rik Sengupta +2
The Graphical House Allocation problem asks: how can houses (each with a fixed non-negative value) be assigned to the vertices of an undirected graph , so as to minimize the…
Time Fairness in Online Knapsack Problems
Adam Lechowicz, Rik Sengupta, Bo Sun +2
The online knapsack problem is a classic problem in the field of online algorithms. Its canonical version asks how to pack items of different values and weights arriving online int…
Multi-Structural Games and Beyond
Marco Carmosino, Ronald Fagin, Neil Immerman +3
Multi-structural (MS) games are combinatorial games that capture the number of quantifiers of first-order sentences. On the face of their definition, MS games differ from Ehrenfeuc…
Graphical House Allocation
Hadi Hosseini, Justin Payan, Rik Sengupta +2
The classical house allocation problem involves assigning houses (or items) to agents according to their preferences. A key criterion in such problems is satisfying some fa…
Relaxations of Envy-Freeness Over Graphs
Justin Payan, Rik Sengupta, Vignesh Viswanathan
When allocating a set of indivisible items among agents, the ideal condition of envy-freeness cannot always be achieved. Envy-freeness up to any good (EFX), and envy-freeness with…
The -Dimensional Weisfeiler-Leman Algorithm
Neil Immerman, Rik Sengupta
In this note, we provide details of the -dimensional Weisfeiler-Leman Algorithm and its analysis from Immerman-Lander (1990). In particular, we present an optimized version of t…
Minimum Degrees of Minimal Ramsey Graphs for Almost-Cliques
Andrey Grinshpun, Raj Raina, Rik Sengupta
For graphs and , we say is Ramsey for if every -coloring of the edges of contains a monochromatic copy of . The graph is Ramsey -minimal if is R…
On a Subposet of the Tamari Lattice
Sebastian A. Csar, Rik Sengupta, Warut Suksompong
We explore some of the properties of a subposet of the Tamari lattice introduced by Pallo, which we call the comb poset. We show that three binary functions that are not well-behav…