C. Swamy

collaborators

Showing cs.DSShow all

5 papers · 1 filter

cs.DS2026

Adaptive Sampling for Minimum-Norm $k$ -Clustering

Haripriya Pulyassary, Chaitanya Swamy

In $k$ -clustering problems, we are given a metric space $(C, d)$ , and must choose a set $S$ of $k$ centers to open. Each client $j \in C$ incurs an assignment c…

cs.DS2026

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 $k$ matroids on a common ground set $U$ of $n$ elements, the goal is to partition $U$ into the fewest number of color clas…

cs.DS2025

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…

cs.DS2025

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 $G = (V, E)$ , non-negative edge costs, and some $(s_{i}, t_{i}, r_{i})$ tuples, where $s_…

cs.DS2025

Almost Tight Additive Guarantees for $k$ -Edge-Connectivity

Nikhil Kumar, Chaitanya Swamy

We consider the \emph{ $k$ -edge connected spanning subgraph} (kECSS) problem, where we are given an undirected graph $G = (V, E)$ with nonnegative edge costs ${c_{e}}_{e \in E}$ , and…

Adaptive Sampling for Minimum-Norm k-Clustering

Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture

Unsplittable Cost Flows from Unweighted Error-Bounded Variants

Tight Guarantees for Cut-Relative Survivable Network Design via a Decomposition Technique

Almost Tight Additive Guarantees for k-Edge-Connectivity

Adaptive Sampling for Minimum-Norm $k$ -Clustering

Almost Tight Additive Guarantees for $k$ -Edge-Connectivity