Chaitanya Swamy
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Chaitanya Swamy has a total of 27 co-authors. Here are the top co-authors by number of shared publications:
- Zachary Friggstad
University of Alberta
5 shared publications - André Linhares
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada
4 shared publications - Rico Zenklusen
Department of Mathematics, ETH Zürich, Zürich, Switzerland
4 shared publications - Neil Olver
London School of Economics and Political Science, London, United Kingdom
3 shared publications - Ian Post
Department of Combinatorics and Optimization University of Waterloo CA
2 shared publications - Sara Ahmadian
Department of Clinical and Experimental Pharmacology, Center for Preclinical Research and Technology (CePT), Medical University of Warsaw, Banacha 1B, 02-097, Warsaw, Poland
2 shared publications
Latest Publications
- Open Access
Unsplittable Cost Flows from Unweighted Error-Bounded Variants
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 load on any arc by at most the maximum demand. Despite extensive work on the topic, only limited progress has been made. Recently, Morell and Skutella suggested an alternative conjecture, stating that one can turn any fractional flow into an unsplittable one without changing the load on any arc by more than the maximum demand. We show that their conjecture implies Goemans' conjecture (with a violation of twice the maximum demand). To this end, we generalize a technique of Linhares and Swamy, used to obtain a low-cost chain-constrained spanning tree from an algorithm without cost guarantees. Whereas Linhares and Swamy's proof relies on Langrangian duality, we provide a very simple elementary proof of a generalized version, which we hope to be of independent interest. Moreover, we show how this technique can also be used in the context of the weighted ring loading problem, showing that cost-unaware approximation algorithms can be transformed into approximation algorithms with additional cost guarantees.
Open AccessUnsplittable Cost Flows from Unweighted Error-Bounded Variants
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 load on any arc by at most the maximum demand. Despite extensive work on the topic, only limited progress has been made. Recently, Morell and Skutella suggested an alternative conjecture, stating that one can turn any fractional flow into an unsplittable one without changing the load on any arc by more than the maximum demand. We show that their conjecture implies Goemans' conjecture (with a violation of twice the maximum demand). To this end, we generalize a technique of Linhares and Swamy, used to obtain a low-cost chain-constrained spanning tree from an algorithm without cost guarantees. Whereas Linhares and Swamy's proof relies on Langrangian duality, we provide a very simple elementary proof of a generalized version, which we hope to be of independent interest. Moreover, we show how this technique can also be used in the context of the weighted ring loading problem, showing that cost-unaware approximation algorithms can be transformed into approximation algorithms with additional cost guarantees.
- Open Access
- 2 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 599
An O (log log n )-approximate budget feasible mechanism for subadditive valuations
- 2 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 599
Open AccessAn O (log log n )-approximate budget feasible mechanism for subadditive valuations
- Open Access
- 11 April 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 39 (13) , 14062-14069
Constant-Factor Distortion Mechanisms for k-Committee Election
In the k-committee election problem, we wish to aggregate the preferences of n agents over a set of alternatives and select a committee of k alternatives that minimizes the cost incurred by the agents. While we typically assume that agent preferences are captured by a cardinal utility function, in many contexts we only have access to ordinal information, namely the agents' rankings over the outcomes. As preference rankings are not as expressive as cardinal utilities, a loss of efficiency is inevitable, and is quantified by the notion of distortion. We study the problem of electing a k-committee that minimizes the sum of the \ell-largest costs incurred by the agents, when agents and candidates are embedded in a metric space. This problem is called the \ell-centrum problem and captures both the utilitarian and egalitarian objectives. When k >= 2, it is not possible to compute a bounded-distortion committee using purely ordinal information. We develop the first algorithms (that we call mechanisms) for the \ell-centrum problem (when k >= 2), which achieve O(1)-distortion while eliciting only a very limited amount of cardinal information via value queries. We obtain two types of query-complexity guarantees: O(log k log n) queries per agent, and O(k^2 log^2 n) queries in total (while achieving O(1)-distortion in both cases). En route, we give a simple adaptive-sampling algorithm for the \ell-centrum k-clustering problem.
- 11 April 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 39 (13) , 14062-14069
Open AccessConstant-Factor Distortion Mechanisms for k-Committee Election
In the k-committee election problem, we wish to aggregate the preferences of n agents over a set of alternatives and select a committee of k alternatives that minimizes the cost incurred by the agents. While we typically assume that agent preferences are captured by a cardinal utility function, in many contexts we only have access to ordinal information, namely the agents' rankings over the outcomes. As preference rankings are not as expressive as cardinal utilities, a loss of efficiency is inevitable, and is quantified by the notion of distortion. We study the problem of electing a k-committee that minimizes the sum of the \ell-largest costs incurred by the agents, when agents and candidates are embedded in a metric space. This problem is called the \ell-centrum problem and captures both the utilitarian and egalitarian objectives. When k >= 2, it is not possible to compute a bounded-distortion committee using purely ordinal information. We develop the first algorithms (that we call mechanisms) for the \ell-centrum problem (when k >= 2), which achieve O(1)-distortion while eliciting only a very limited amount of cardinal information via value queries. We obtain two types of query-complexity guarantees: O(log k log n) queries per agent, and O(k^2 log^2 n) queries in total (while achieving O(1)-distortion in both cases). En route, we give a simple adaptive-sampling algorithm for the \ell-centrum k-clustering problem.
- 1 June 2022
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 126, 44-58
A constant-factor approximation for directed latency in quasi-polynomial time
- 1 June 2022
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 126, 44-58
A constant-factor approximation for directed latency in quasi-polynomial time
- 27 May 2022
- Published by Springer Nature
- p. 195-209
Combinatorial Algorithms for Rooted Prize-Collecting Walks and Applications to Orienteering and Minimum-Latency Problems
- 27 May 2022
- Published by Springer Nature
- p. 195-209
Combinatorial Algorithms for Rooted Prize-Collecting Walks and Applications to Orienteering and Minimum-Latency Problems
- 15 June 2020
- Published by Springer Nature in Mathematical Programming
- Vol. 183 (1-2) , 397-418
Approximate multi-matroid intersection via iterative refinement
- 15 June 2020
- Published by Springer Nature in Mathematical Programming
- Vol. 183 (1-2) , 397-418
Approximate multi-matroid intersection via iterative refinement
- Open Access
A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time
We give the first constant-factor approximation for the Directed Latency problem in quasi-polynomial time. Here, the goal is to visit all nodes in an asymmetric metric with a single vehicle starting at a depot $r$ to minimize the average time a node waits to be visited by the vehicle. The approximation guarantee is an improvement over the polynomial-time $O(\log n)$-approximation [Friggstad, Salavatipour, Svitkina, 2013] and no better quasi-polynomial time approximation algorithm was known. To obtain this, we must extend a recent result showing the integrality gap of the Asymmetric TSP-Path LP relaxation is bounded by a constant [K\"{o}hne, Traub, and Vygen, 2019], which itself builds on the breakthrough result that the integrality gap for standard Asymmetric TSP is also a constant [Svensson, Tarnawsi, and Vegh, 2018]. We show the standard Asymmetric TSP-Path integrality gap is bounded by a constant even if the cut requirements of the LP relaxation are relaxed from $x(\delta^{in}(S)) \geq 1$ to $x(\delta^{in}(S)) \geq \rho$ for some constant $1/2 < \rho \leq 1$. We also give a better approximation guarantee in the special case of Directed Latency in regret metrics where the goal is to find a path $P$ minimize the average time a node $v$ waits in excess of $c_{rv}$, i.e. $\frac{1}{|V|} \cdot \sum_{v \in V} (c_v(P)-c_{rv})$.Open AccessA Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time
We give the first constant-factor approximation for the Directed Latency problem in quasi-polynomial time. Here, the goal is to visit all nodes in an asymmetric metric with a single vehicle starting at a depot $r$ to minimize the average time a node waits to be visited by the vehicle. The approximation guarantee is an improvement over the polynomial-time $O(\log n)$-approximation [Friggstad, Salavatipour, Svitkina, 2013] and no better quasi-polynomial time approximation algorithm was known. To obtain this, we must extend a recent result showing the integrality gap of the Asymmetric TSP-Path LP relaxation is bounded by a constant [K\"{o}hne, Traub, and Vygen, 2019], which itself builds on the breakthrough result that the integrality gap for standard Asymmetric TSP is also a constant [Svensson, Tarnawsi, and Vegh, 2018]. We show the standard Asymmetric TSP-Path integrality gap is bounded by a constant even if the cut requirements of the LP relaxation are relaxed from $x(\delta^{in}(S)) \geq 1$ to $x(\delta^{in}(S)) \geq \rho$ for some constant $1/2 < \rho \leq 1$. We also give a better approximation guarantee in the special case of Directed Latency in regret metrics where the goal is to find a path $P$ minimize the average time a node $v$ waits in excess of $c_{rv}$, i.e. $\frac{1}{|V|} \cdot \sum_{v \in V} (c_v(P)-c_{rv})$. - Open Access
- 13 April 2019
- Published by Springer Nature
- p. 299-312
Approximate Multi-matroid Intersection via Iterative Refinement
- 13 April 2019
- Published by Springer Nature
- p. 299-312
Open AccessApproximate Multi-matroid Intersection via Iterative Refinement
- Open Access
Approximate Multi-Matroid Intersection via Iterative Refinement
We introduce a new iterative rounding technique to round a point in a matroid polytope subject to further matroid constraints. This technique returns an independent set in one matroid with limited violations of the other ones. On top of the classical steps of iterative relaxation approaches, we iteratively refine/split involved matroid constraints to obtain a more restrictive constraint system, that is amenable to iterative relaxation techniques. Hence, throughout the iterations, we both tighten constraints and later relax them by dropping constrains under certain conditions. Due to the refinement step, we can deal with considerably more general constraint classes than existing iterative relaxation/rounding methods, which typically round on one matroid polytope with additional simple cardinality constraints that do not overlap too much. We show how our rounding method, combined with an application of a matroid intersection algorithm, yields the first $2$-approximation for finding a maximum-weight common independent set in $3$ matroids. Moreover, our $2$-approximation is LP-based, and settles the integrality gap for the natural relaxation of the problem. Prior to our work, no better upper bound than $3$ was known for the integrality gap, which followed from the greedy algorithm. We also discuss various other applications of our techniques, including an extension that allows us to handle a mixture of matroid and knapsack constraints.Open AccessApproximate Multi-Matroid Intersection via Iterative Refinement
We introduce a new iterative rounding technique to round a point in a matroid polytope subject to further matroid constraints. This technique returns an independent set in one matroid with limited violations of the other ones. On top of the classical steps of iterative relaxation approaches, we iteratively refine/split involved matroid constraints to obtain a more restrictive constraint system, that is amenable to iterative relaxation techniques. Hence, throughout the iterations, we both tighten constraints and later relax them by dropping constrains under certain conditions. Due to the refinement step, we can deal with considerably more general constraint classes than existing iterative relaxation/rounding methods, which typically round on one matroid polytope with additional simple cardinality constraints that do not overlap too much. We show how our rounding method, combined with an application of a matroid intersection algorithm, yields the first $2$-approximation for finding a maximum-weight common independent set in $3$ matroids. Moreover, our $2$-approximation is LP-based, and settles the integrality gap for the natural relaxation of the problem. Prior to our work, no better upper bound than $3$ was known for the integrality gap, which followed from the greedy algorithm. We also discuss various other applications of our techniques, including an extension that allows us to handle a mixture of matroid and knapsack constraints. - Open Access
Interpolating between $k$-Median and $k$-Center: Approximation Algorithms for Ordered $k$-Median
We consider a generalization of $k$-median and $k$-center, called the {\em ordered $k$-median} problem. In this problem, we are given a metric space $(\mathcal{D},\{c_{ij}\})$ with $n=|\mathcal{D}|$ points, and a non-increasing weight vector $w\in\mathbb{R}_+^n$, and the goal is to open $k$ centers and assign each point each point $j\in\mathcal{D}$ to a center so as to minimize $w_1\cdot\text{(largest assignment cost)}+w_2\cdot\text{(second-largest assignment cost)}+\ldots+w_n\cdot\text{($n$-th largest assignment cost)}$. We give an $(18+\epsilon)$-approximation algorithm for this problem. Our algorithms utilize Lagrangian relaxation and the primal-dual schema, combined with an enumeration procedure of Aouad and Segev. For the special case of $\{0,1\}$-weights, which models the problem of minimizing the $\ell$ largest assignment costs that is interesting in and of by itself, we provide a novel reduction to the (standard) $k$-median problem showing that LP-relative guarantees for $k$-median translate to guarantees for the ordered $k$-median problem; this yields a nice and clean $(8.5+\epsilon)$-approximation algorithm for $\{0,1\}$ weights.Open AccessInterpolating between $k$-Median and $k$-Center: Approximation Algorithms for Ordered $k$-Median
We consider a generalization of $k$-median and $k$-center, called the {\em ordered $k$-median} problem. In this problem, we are given a metric space $(\mathcal{D},\{c_{ij}\})$ with $n=|\mathcal{D}|$ points, and a non-increasing weight vector $w\in\mathbb{R}_+^n$, and the goal is to open $k$ centers and assign each point each point $j\in\mathcal{D}$ to a center so as to minimize $w_1\cdot\text{(largest assignment cost)}+w_2\cdot\text{(second-largest assignment cost)}+\ldots+w_n\cdot\text{($n$-th largest assignment cost)}$. We give an $(18+\epsilon)$-approximation algorithm for this problem. Our algorithms utilize Lagrangian relaxation and the primal-dual schema, combined with an enumeration procedure of Aouad and Segev. For the special case of $\{0,1\}$-weights, which models the problem of minimizing the $\ell$ largest assignment costs that is interesting in and of by itself, we provide a novel reduction to the (standard) $k$-median problem showing that LP-relative guarantees for $k$-median translate to guarantees for the ordered $k$-median problem; this yields a nice and clean $(8.5+\epsilon)$-approximation algorithm for $\{0,1\}$ weights.