5 papers
Low-Cost Arborescence Under Edge Faults
Dipan Dey, Telikepalli Kavitha
Our input is a directed graph on vertices and edges with a designated root vertex and a function . The problem is t…
Condorcet Dimension and Pareto Optimality for Matchings and Beyond
Telikepalli Kavitha, Jannik Matuschke, Ulrike Schmidt-Kraepelin
We study matching problems in which agents form one side of a bipartite graph and have preferences over objects on the other side. A central solution concept in this setting is pop…
Fault-Tolerant Approximate Distance Oracles with a Source Set
Dipan Dey, Telikepalli Kavitha
Our input is an undirected weighted graph on vertices along with a source set . The problem is to preprocess and build a compact data structure su…
Best-of-Both-Worlds Guarantees with Fairer Endings
Telikepalli Kavitha, Surya Panchapakesan, Rohit Vaish +2
Fair allocation of indivisible goods is a fundamental problem at the interface of economics and computer science. Traditional approaches focus either on randomized allocations that…
Perfect Matchings and Popularity in the Many-to-Many Setting
Telikepalli Kavitha, Kazuhisa Makino
We consider a matching problem in a bipartite graph where every vertex has a capacity and a strict preference order on its neighbors. Furthermore, there is a cost function on t…