From the 1 of 6 linked papers with an AI index.
6 papers
Adaptive Sampling for Minimum-Norm -Clustering
Haripriya Pulyassary, Chaitanya Swamy
The paper introduces an adaptive‑sampling algorithm that provides a bicriteria constant‑factor approximation for general minimum‑norm k‑clustering, and an O(log k) approximation fo…
Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture
Stephen Arndt, Benjamin Moseley, Kirk Pruhs +2
We study algorithmic matroid intersection coloring. Given matroids on a common ground set of elements, the goal is to partition into the fewest number of color clas…
Almost Tight Additive Guarantees for -Edge-Connectivity
Nikhil Kumar, Chaitanya Swamy
We consider the \emph{-edge connected spanning subgraph} (kECSS) problem, where we are given an undirected graph with nonnegative edge costs , and…
Unsplittable Cost Flows from Unweighted Error-Bounded Variants
Chaitanya Swamy, Vera Traub, Laura Vargas Koch +1
A famous conjecture of Goemans on single-source unsplittable flows states that one can turn any fractional flow into an unsplittable one of no higher cost, while increasing the loa…
Tight Guarantees for Cut-Relative Survivable Network Design via a Decomposition Technique
Nikhil Kumar, JJ Nan, Chaitanya Swamy
In the classical \emph{survivable-network-design problem} (SNDP), we are given an undirected graph , non-negative edge costs, and some tuples, where $s_…
Constant-Factor Distortion Mechanisms for -Committee Election
Haripriya Pulyassary, Chaitanya Swamy
In the -committee election problem, we wish to aggregate the preferences of agents over a set of alternatives and select a committee of alternatives that minimizes the c…