5 papers · 1 filter
Minimizing Envy and Maximizing Happiness in Graphical House Allocation
Anubhav Dhar, Ashlesha Hota, Palash Dey +1
We study the house allocation problem in a setting where agents are connected by a graph representing friendships. In this model, two agents can only envy each other if they are ne…
Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
Aritra Banik, Sujoy Bhore, Palash Dey +1
The kidney exchange mechanism allows many patient-donor pairs who are otherwise incompatible with each other to come together and exchange kidneys along a cycle. However, due to in…
Knapsack on Graphs with Relaxed Neighborhood Constraints
Palash Dey, Ashlesha Hota, Sudeshna Kolay
In the knapsack problems with neighborhood constraints that were studied before, the input is a graph on a set of items, each item h…
Maximizing Value in Challenge the Champ Tournaments
Umang Bhaskar, Juhi Chaudhary, Palash Dey
A tournament is a method to decide the winner in a competition, and describes the overall sequence in which matches between the players are held. While deciding a worthy winner is…
Knapsack with Vertex Cover, Set Cover, and Hitting Set
Palash Dey, Ashlesha Hota, Sudeshna Kolay +1
Given an undirected graph , with vertex weights , vertex values , a knapsack size , a…