Nithin Varma

2 accepted papers

2025

(Almost Full) EFX for Three (and More) Types of Agents

Pratik Ghosal, Vishwa Prakash HV, Prajakta Nimbhorkar, Nithin Varma

AAAI 2025technical

We study the problem of determining an envy-free allocation of indivisible goods among multiple agents with additive valuations. EFX, which stands for envy-freeness up to any good, is a well-studied relaxation of the envy-free allocation problem and has been shown to exist for specific scenarios. EF…

Cited by 10 Source ↗PDF ↗Scholar ↗

2025

Towards Better-than-2 Approximation for Constrained Correlation Clustering

Andreas Kalavas, Evangelos Kipouridis, Nithin Varma

ICML 2025spotlight

In the Correlation Clustering problem, we are given an undirected graph and are tasked with computing a clustering (partition of the nodes) that minimizes the sum of the number of edges across different clusters and the number of non-edges within clusters. In the constrained version of this problem,…

Cited by 0 Source ↗PDF ↗Scholar ↗