Sanjeev Khanna

most citedPerfect Matchings in Õ(n^{1.5}) Time in Regular Bipartite Graphs

4 citations · 5 across the 4 of their papers we have counts for

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2009★ 4 cited

Perfect Matchings in Õ(n^{1.5}) Time in Regular Bipartite Graphs

Ashish Goel, Michael Kapralov, Sanjeev Khanna

We consider the well-studied problem of finding a perfect matching in $d$ -regular bipartite graphs with $2 n$ vertices and $m = n d$ edges. While the best-known algorithm for general…

cs.DS2009

On Allocating Goods to Maximize Fairness

Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna

Given a set of $m$ agents and a set of $n$ items, where agent $A$ has utility $u_{A, i}$ for item $i$ , our goal is to allocate items to agents to maximize fairness. Specifically, th…

cs.DS2008★ 1 cited

An $O (k^{3} l o g n)$ -Approximation Algorithm for Vertex-Connectivity Survivable Network Design

Julia Chuzhoy, Sanjeev Khanna

In the Survivable Network Design problem (SNDP), we are given an undirected graph $G (V, E)$ with costs on edges, along with a connectivity requirement $r (u, v)$ for each pair $u, v$ o…

Perfect Matchings in Õ(n^{1.5}) Time in Regular Bipartite Graphs

On Allocating Goods to Maximize Fairness

An O(k3logn)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design

An $O (k^{3} l o g n)$ -Approximation Algorithm for Vertex-Connectivity Survivable Network Design