14 papers
MLN-EIGS: A multilayer network framework for solving Stackelberg escape interdiction games on dynamic transportation networks
Sukanya Samanta, Kei Kimura, Makoto Yokoo +1
Interdicting an escaping criminal with limited police resources on large-scale transportation networks is a challenging problem due to the dynamic nature of both attacker movement…
Fair, Efficient and Connected Allocations on Graphs
Susobhan Bandopadhyay, Anish Datta, Palash Dey +2
We study the classical and parameterized complexity of efficient connected allocation problems on graphs, where efficiency is measured by egalitarian and utilitarian welfare maximi…
Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
Palash Dey, Anubhav Dhar, Ashlesha Hota +2
In this paper, we study the Maximum Common Vertex Subgraph problem: Given two input graphs and a non-negative integer , is there a common subgraph on at least …
Fair Distribution of Digital Payments: Balancing Transaction Flows for Regulatory Compliance
Ashlesha Hota, Shashwat Kumar, Daman Deep Singh +3
The concentration of digital payment transactions in just two UPI apps like PhonePe and Google Pay has raised concerns of duopoly in India s digital financial ecosystem. To address…
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…
Shift Bribery over Social Networks
Ashlesha Hota, Susobhan Bandopadhyay, Palash Dey
In shift bribery, a briber seeks to promote his preferred candidate by paying voters to raise their ranking. Classical models of shift bribery assume voters act independently, over…
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…
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…
Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints
Dhruv Sarkar, Aprameyo Chakrabartty, Subhamon Supantha +2
We study a generalization of the Online Convex Optimization (OCO) framework with time-varying adversarial constraints. In this setting, at each round, the learner selects an action…
Voter Participation Control in Online Polls
Koustav De, Palash Dey, Swagato Sanyal
News outlets, surveyors, and other organizations often conduct polls on social networks to gain insights into public opinion. Such a poll is typically started by someone on a socia…
Solving a Stackelberg Game on Transportation Networks in a Dynamic Crime Scenario: A Mixed Approach on Multi-Layer Networks
Sukanya Samanta, Kei Kimura, Makoto Yokoo +1
Interdicting a criminal with limited police resources is a challenging task as the criminal changes location over time. The size of the large transportation network further adds to…
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 , an…
Evaluating District-based Election Surveys with Synthetic Dirichlet Likelihood
Adway Mitra, Palash Dey
In district-based multi-party elections, electors cast votes in their respective districts. In each district, the party with maximum votes wins the corresponding seat in the govern…