Chaitanya Swamy

FOCS Conference 2025 Conference Paper

Almost Tight Additive Guarantees for k-Edge-Connectivity

• Nikhil Kumar 0001
• Chaitanya Swamy

We consider the $\boldsymbol{k}$-edge connected spanning subgraph (k-ECSS) problem, where we are given an undirected graph $G=(V, E)$ with nonnegative edge costs $\left\{c_{e}\right\}_{e \in E}$, and the goal is to find a minimum-cost subgraph H of G that is k edge connected, i. e. , there exist at least k edge-disjoint paths between every pair of vertices in H. For even k, we present a polynomial time algorithm that computes a ($k-2$)-edge connected subgraph of cost at most that of the optimal k-edge connected subgraph of G; for odd k, we obtain a $(k-3)$ edge connected subgraph of cost at most the optimum. In fact, the cost of our solution does not exceed the optimal value, $\mathbf{L P}_{\boldsymbol{k} \text {-ECSSLP }}^{\boldsymbol{*}}$ of the natural LP-relaxation for $\boldsymbol{k}$-ECSS. Since k-ECSS is $A P X$-hard for all values of $k \geq 2$, our results are nearly optimal. They also significantly improve upon the recent work of Hershkowitz, Klein, and Zenklusen [1], both in terms of solution quality and the simplicity of algorithm and its analysis. Interestingly, our techniques also yield an alternate guarantee, where we obtain a($k-1$)-edge connected subgraph of cost at most $1. 5 \cdot \mathrm{LP}_{\boldsymbol{k}-\mathrm{ECSSLP}}^{*}$; with unit edge costs, the cost guarantee improves to $\left(1+\frac{4}{3 k}\right) \cdot$ LP $_{\boldsymbol{k} \text {-ECSSLP }}^{\boldsymbol{*}}$, which improves upon the state-of-the-art approximation guarantee for unit edge costs [2], albeit with a unit loss in edge connectivity. Our k-ECSS-result also yields results for the k-edge connected spanning multigraph (k-ECSM) problem, where multiple copies of an edge can be selected. For $\boldsymbol{k}$-ECSM, we obtain a $\left(1+\frac{2}{k}\right)$-approximation algorithm for even k, and $\mathbf{a}\left(1+\frac{3}{k}\right)$ approximation algorithm for odd $\boldsymbol{k}$. Finally, our techniques extend to the degree-bounded versions of k-ECSS and k-ECSM, wherein we also impose degree lower- and upper- bounds on the nodes. Our results for k-ECSS and k-ECSM extend to yield the same cost and connectivity guarantees for these degree-bounded versions with an additive violation of (roughly) 2 for the degree bounds. These are the first results for degree-bounded $\{k$-ECSS, k-ECSM $\}$ of the form where the cost of the solution obtained is at most the optimum, and the connectivity constraints are violated by an additive constant. Work done while N. Kumar was a postdoc in the $C \& O$ department at the University of Waterloo. Supported in part by C. Swamy’s NSERC Discovery grant.

AAAI Conference 2025 Conference Paper

Constant-Factor Distortion Mechanisms for k-Committee Election

• Haripriya Pulyassary
• Chaitanya Swamy

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.

FOCS Conference 2020 Conference Paper

Approximation Algorithms for Stochastic Minimum-Norm Combinatorial Optimization

• Sharat Ibrahimpur
• Chaitanya Swamy

Motivated by the need for, and growing interest in, modeling uncertainty in data, we introduce and study stochastic minimum-norm optimization. We have an underlying combinatorial optimization problem where the costs involved are random variables with given distributions; each feasible solution induces a random multidimensional cost vector, and given a certain objective function, the goal is to find a solution (that does not depend on the realizations of the costs) that minimizes the expected objective value. For instance, in stochastic load balancing, jobs with random processing times need to be assigned to machines, and the induced cost vector is the machine-load vector. The choice of objective is typically the maximum- or sum-of the entries of the cost vector, or in some cases some other lp norm of the cost vector. Recently, in the deterministic setting, Chakrabarty and Swamy [7] considered a much broader suite of objectives, wherein we seek to minimize the f-norm of the cost vector under a given arbitrary monotone, symmetric norm f. In stochastic minimum-norm optimization, we work with this broad class of objectives, and seek a solution that minimizes the expected f-norm of the induced cost vector. The class of monotone, symmetric norms is versatile and includes lp-norms, and Topl-norms (sum of l largest coordinates in absolute value), and enjoys various closure properties; in particular, it can be used to incorporate multiple norm budget constraints, fl(x) ≤ B l, l = 1, .. ., k. We give a general framework for devising algorithms for stochastic minimum-norm combinatorial optimization, using which we obtain approximation algorithms for the stochastic minimum-norm versions of the load balancing and spanning tree problems. We obtain the following concrete results. (a) An O(1)-approximation for stochastic minimum-norm load balancing on unrelated machines with: (i) arbitrary monotone symmetric norms and job sizes that are Bernoulli random variables; and (ii) Topl norms and arbitrary job-size distributions. (b) An O(log m/log log m)-approximation for the general stochastic minimum-norm load balancing problem, where m is the number of machines. (c) An O(1)-approximation for stochastic minimum-norm spanning tree with arbitrary monotone symmetric norms and arbitrary edge-weight distributions; this guarantee extends to the stochastic minimum-norm matroid basis problem. Two key technical contributions of this work are: (1) a structural result of independent interest connecting stochastic minimum-norm optimization to the simultaneous optimization of a (small) collection of expected Top l -norms; and (2) showing how to tackle expected Top l -norm minimization by leveraging techniques used to deal with minimizing the expected maximum, circumventing the difficulties posed by the non-separable nature of Top l norms.

STOC Conference 2019 Conference Paper

Approximation algorithms for distributionally-robust stochastic optimization with black-box distributions

• André Linhares
• Chaitanya Swamy

Two-stage stochastic optimization is a widely used framework for modeling uncertainty, where we have a probability distribution over possible realizations of the data, called scenarios, and decisions are taken in two stages: we make first-stage decisions knowing only the underlying distribution and before a scenario is realized, and may take additional second-stage recourse actions after a scenario is realized. The goal is typically to minimize the total expected cost. A common criticism levied at this model is that the underlying probability distribution is itself often imprecise! To address this, an approach that is quite versatile and has gained popularity in the stochastic-optimization literature is the distributionally robust 2-stage model : given a collection D of probability distributions, our goal now is to minimize the maximum expected total cost with respect to a distribution in D . We provide a framework for designing approximation algorithms in such settings when the collection D is a ball around a central distribution and the central distribution is accessed only via a sampling black box . We first show that one can utilize the sample average approximation (SAA) method—solve the distributionally robust problem with an empirical estimate of the central distribution—to reduce the problem to the case where the central distribution has polynomial-size support. Complementing this, we show how to approximately solve a fractional relaxation of the SAA (i.e., polynomial-scenario central-distribution) problem. Unlike in 2-stage stochastic- or robust- optimization, this turns out to be quite challenging. We utilize the ellipsoid method in conjunction with several new ideas to show that this problem can be approximately solved provided that we have an (approximation) algorithm for a certain max-min problem that is akin to, and generalizes, the k -max-min problem—find the worst-case scenario consisting of at most k elements—encountered in 2-stage robust optimization. We obtain such a procedure for various discrete-optimization problems; by complementing this via LP-rounding algorithms that provide local (i.e., per-scenario) approximation guarantees, we obtain the first approximation algorithms for the distributionally robust versions of a variety of discrete-optimization problems including set cover, vertex cover, edge cover, facility location, and Steiner tree, with guarantees that are, except for set cover, within O (1)-factors of the guarantees known for the deterministic version of the problem.

STOC Conference 2019 Conference Paper

Approximation algorithms for minimum norm and ordered optimization problems

• Deeparnab Chakrabarty
• Chaitanya Swamy

In many optimization problems, a feasible solution induces a multi-dimensional cost vector. For example, in load-balancing a schedule induces a load vector across the machines. In k -clustering, opening k facilities induces an assignment cost vector across the clients. Typically, one seeks a solution which either minimizes the sum- or the max- of this vector, and these problems (makespan minimization, k -median, and k -center) are classic NP-hard problems which have been extensively studied. In this paper we consider the minimum-norm optimization problem. Given an arbitrary monotone, symmetric norm, the problem asks to find a solution which minimizes the norm of the induced cost-vector. Such norms are versatile and include ℓ p norms, Top-ℓ norm (sum of the ℓ largest coordinates in absolute value), and ordered norms (non-negative linear combination of Top-ℓ norms), and consequently, the minimum-norm problem models a wide variety of problems under one umbrella, We give a general framework to tackle the minimum-norm problem, and illustrate its efficacy in the unrelated machine load balancing and k -clustering setting. Our concrete results are the following. (a) We give constant factor approximation algorithms for the minimum norm load balancing problem in unrelated machines, and the minimum norm k -clustering problem. To our knowledge, our results constitute the first constant-factor approximations for such a general suite of objectives. (b) For load balancing on unrelated machines, we give a (2+ε)-approximation for ordered load balancing (i.e., min-norm load-balancing under an ordered norm). (c) For k -clustering, we give a (5+ε)-approximation for the ordered k -median problem, which significantly improves upon the previous-best constant-factor approximation (Chakrabarty and Swamy (ICALP 2018); Byrka, Sornat, and Spoerhase (STOC 2018)). (d) Our techniques also imply O (1) approximations to the instance-wise best simultaneous approximation factor for unrelated-machine load-balancing and k -clustering. To our knowledge, these are the first positive simultaneous approximation results in these settings. At a technical level, one of our chief insights is that minimum-norm optimization can be reduced to a special case that we call min-max ordered optimization . Both the reduction, and the task of devising algorithms for the latter problem, require a sparsification idea that we develop, which is of interest for ordered optimization problems. The main ingredient in solving min-max ordered optimization is a deterministic, oblivious rounding procedure (that we devise) for suitable LP relaxations of the load-balancing and k -clustering problem; this may be of independent interest.

SODA Conference 2015 Conference Paper

Improved Region-Growing and Combinatorial Algorithms for k -Route Cut Problems (Extended Abstract)

• Guru Guruganesh
• Laura Sanità
• Chaitanya Swamy

We study the k-route generalizations of various cut problems, the most general of which is k-route multicut ( k -MC) problem, wherein we have r source-sink pairs and the goal is to delete a minimum-cost set of edges to reduce the edge-connectivity of every source-sink pair to below k. The k -route extensions of multiway cut ( k -MWC), and the minimum s-t cut problem ( k- ( s, t )-Cut), are similarly defined. We present various approximation and hardness results for k -MC, k -MWC, and k -( s, t )-Cut that improve the state-of-the-art for these problems in several cases. Our contributions are threefold. For k-route multiway cut, we devise simple, but surprisingly effective, combinatorial algorithms that yield bicriteria approximation guarantees that markedly improve upon the previous-best guarantees. For k-route multicut, we design algorithms that improve upon the previous-best approximation factors by roughly an -factor, when k = 2, and for general k and unit costs and any fixed violation of the connectivity threshold k. The main technical innovation is the definition of a new, powerful region growing lemma that allows us to perform region-growing in a recursive fashion even though the LP solution yields a different metric for each source-sink pair, and without incurring an O (log 2 r ) blow-up in the cost that is inherent in some previous applications of region growing to k -route cuts. We obtain the same benefits as [15] do in their divide-and-conquer algorithms, and thereby obtain an O (ln r ln ln r )-approximation to the cost. We also obtain some extensions to k -route node-multicut problems. We complement these results by showing that the k-route s-t cut problem is at least as hard to approximate as the densest-k-subgraph (D k S) problem on uniform hypergraphs. In particular, this implies that one cannot avoid a poly( k )-factor if one seeks a unicriterion approximation, without improving the state-of-the-art for D k S on graphs, and proving the existence of a family of one-way functions. Previously, only NP -hardness of k -( s; t )-Cut was known.

STOC Conference 2015 Conference Paper

Learning Arbitrary Statistical Mixtures of Discrete Distributions

• Jian Li 0015
• Yuval Rabani
• Leonard J. Schulman
• Chaitanya Swamy

We study the problem of learning from unlabeled samples very general statistical mixture models on large finite sets. Specifically, the model to be learned, mix, is a probability distribution over probability distributions p, where each such p is a probability distribution over [n] = {1,2,...,n}. When we sample from mix, we do not observe p directly, but only indirectly and in very noisy fashion, by sampling from [n] repeatedly, independently K times from the distribution p. The problem is to infer mix to high accuracy in transportation (earthmover) distance.

SODA Conference 2015 Conference Paper

Linear Programming-based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems (Extended Abstract)

• Ian Post
• Chaitanya Swamy

We consider various multi-vehicle versions of the minimum latency problem. There is a fleet of k vehicles located at one or more depot nodes, and we seek a collection of routes for these vehicles that visit all nodes so as to minimize the total latency incurred, which is the sum of the client waiting times. We obtain an 8. 497-approximation for the version where vehicles may be located at multiple depots and a 7. 183-approximation for the version where all vehicles are located at the same depot, both of which are the first improvements on this problem in a decade. Perhaps more significantly, our algorithms exploit various LP relaxations for minimum-latency problems. We show how to effectively leverage two classes of LPs— configuration LPs and bidirected LP relaxations —that are often believed to be quite powerful but have only sporadically been effectively leveraged for network-design and vehicle-routing problems. This gives the first concrete evidence of the effectiveness of LP relaxations for this class of problems. The 8. 497-approximation the multiple-depot version is obtained by rounding a near-optimal solution to an underlying configuration LP for the problem. The 7. 183-approximation can be obtained both via rounding a bidirected LP for the single-depot problem or via more combinatorial means. The latter approach uses a bidirected LP to obtain the following key result that is of independent interest: for any k, we can efficiently compute a rooted tree that is at least as good, with respect to the prize-collecting objective (i. e. , edge cost + number of uncovered nodes) as the best collection of k rooted paths. This substantially generalizes a result of Chaudhuri et al. [11] for k = 1, yet our proof is significantly simpler. Our algorithms are versatile and extend easily to handle various extensions involving: (i) weighted sum of latencies, (ii) constraints specifying which depots may serve which nodes, (iii) node service times. Finally, we propose a configuration LP that sheds further light on the power of LP relaxations for minimum-latency problems. We prove that the integrality gap of this LP is at most 3. 592, even for the multi-depot problem, both via an efficient rounding procedure, and by showing that it is at least as powerful as a stroll-based lower bound that is oft-used for minimum-latency problems; the latter result implies an integrality gap of at most 3. 03 when k = 1. Although, we do not know how to solve this LP in general, it can be solved (near-optimally) when k = 1, and this yields an LP-relative 3. 592-approximation for the single-vehicle problem, matching (essentially) the current-best approximation ratio for this problem.

FOCS Conference 2014 Conference Paper

Achieving Target Equilibria in Network Routing Games without Knowing the Latency Functions

• Umang Bhaskar
• Katrina Ligett
• Leonard J. Schulman
• Chaitanya Swamy

The analysis of network routing games typically assumes, right at the onset, precise and detailed information about the latency functions. Such information may, however, be unavailable or difficult to obtain. Moreover, one is often primarily interested in enforcing a desirable target flow as the equilibrium by suitably influencing player behavior in the routing game. We ask whether one can achieve target flows as equilibria without knowing the underlying latency functions. Our main result gives a crisp positive answer to this question. We show that, under fairly general settings, one can efficiently compute edge tolls that induce a given target multicommodity flow in a nonatomic routing game using a polynomial number of queries to an oracle that takes candidate tolls as input and returns the resulting equilibrium flow. This result is obtained via a novel application of the ellipsoid method, and applies to arbitrary multicommodity settings and non-linear latency functions. Our algorithm extends easily to many other settings, such as (i) when certain edges cannot be tolled or there is an upper bound on the total toll paid by a user, and (ii) general nonatomic congestion games. We obtain tighter bounds on the query complexity for series-parallel networks, and single-commodity routing games with linear latency functions, and complement these with a query-complexity lower bound applicable even to single-commodity routing games on parallel-link graphs with linear latency functions. We also explore the use of Stackelberg routing to achieve target equilibria and obtain strong positive results for series-parallel graphs. Our results build upon various new techniques that we develop pertaining to the computation of, and connections between, different notions of approximate equilibrium, properties of multicommodity flows and tolls in series-parallel graphs, and sensitivity of equilibrium flow with respect to tolls. Our results demonstrate that one can indeed circumvent the potentially-onerous task of modeling latency functions, and yet obtain meaningful results for the underlying routing game.

STOC Conference 2014 Conference Paper

Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing

• Zachary Friggstad
• Chaitanya Swamy

SODA Conference 2013 Conference Paper

Local-Search based Approximation Algorithms for Mobile Facility Location Problems

• Sara Ahmadian
• Zachary Friggstad
• Chaitanya Swamy

SODA Conference 2012 Conference Paper

Black-box reductions for cost-sharing mechanism design

• Konstantinos Georgiou
• Chaitanya Swamy

SODA Conference 2011 Conference Paper

Risk-Averse Stochastic Optimization: Probabilistically-Constrained Models and Algorithms for Black-Box Distributions

• Chaitanya Swamy

We consider various stochastic models that incorporate the notion of risk-averseness into the standard 2-stage recourse model, and develop novel techniques for solving the algorithmic problems arising in these models. A key notable feature of our work that distinguishes it from work in some other related models, such as the (standard) budget model and the (demand-) robust model, is that we obtain results in the black-box setting, that is, where one is given only sampling access to the underlying distribution. Our first model, which we call the risk-averse budget model, incorporates the notion of risk-averseness via a probabilistic constraint that restricts the probability (according to the underlying distribution) with which the second-stage cost may exceed a given budget B to at most a given input threshold ρ. We also a consider a closely-related model that we call the risk-averse robust model, where we seek to minimize the first-stage cost and the (1 − ρ)-quantile (according to the distribution) of the second-stage cost. We obtain approximation algorithms for a variety of combinatorial optimization problems including the set cover, vertex cover, multicut on trees, and facility location problems, in the risk-averse budget and robust models with black-box distributions. Our main contribution is to devise a fully polynomial approximation scheme for solving the LP-relaxations of a wide-variety of risk-averse budgeted problems. Complementing this, we give a simple rounding procedure that shows that one can exploit existing LP-based approximation algorithms for the 2-stage-stochastic and/or deterministic counterpart of the problem to round the fractional solution and obtain an approximation algorithm for the risk-averse problem. To the best of our knowledge, these are the first approximation results for problems involving probabilistic constraints and black-box distributions. A notable feature of our scheme is that it extends easily to handle a significantly richer class of risk-averse problems, where we impose a joint probabilistic budget constraint on different components of the second-stage cost. Consequently, we also obtain approximation algorithms in the setting where we have a joint budget constraint on different portions of the second-stage cost.

SODA Conference 2008 Conference Paper

Approximation algorithms for labeling hierarchical taxonomies

• Yuval Rabani
• Leonard J. Schulman
• Chaitanya Swamy

FOCS Conference 2008 Conference Paper

Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply

• Maurice Cheung
• Chaitanya Swamy

We present the first polynomial-time approximation algorithms for single-minded envy-free profit-maximization problems (Guruswami et al. , 2005) with limited supply. Our algorithms return a pricing scheme and a subset of customers that are designated the winners, which satisfy the envy-freeness constraint, whereas in our analyses, we compare the profit of our solution against the optimal value of the corresponding social-welfare-maximization (SWM) problem of finding a winner-set with maximum total value. Our algorithms take any LP-based alpha-approximation algorithm for the corresponding SWM problem as input and return a solution that achieves profit at least OPT/O (alpha ldr log u max ), where OPT is the optimal value of the SWM problem, and u max is the maximum supply of an item. This immediately yields approximation guarantees of O(radicmlog u max ) for the general single-minded envy-free problem; and O(log u max ) for the tollbooth and highway problems (Guruswami et al. , 2005), and the graph-vertex pricing problem (Balcan and Blum, 2006) (alpha = O(1) for all the corresponding SWM problems). Since OPT is an upper bound on the maximum profit achievable by any solution (i. e. , irrespective of whether the solution satisfies the envy-freeness constraint), our results directly carry over to the non-envy-free versions of these problems too. Our result also thus (constructively) establishes an upper bound of O(alpha ldr log u max ) on the ratio of (i) the optimum value of the profit-maximization problem and OPT; and (ii) the optimum profit achievable with and without the constraint of envy-freeness.

SODA Conference 2007 Conference Paper

Approximation algorithms for prize collecting forest problems with submodular penalty functions

• Yogeshwer Sharma
• Chaitanya Swamy
• David P. Williamson

SODA Conference 2007 Conference Paper

The effectiveness of Stackelberg strategies and tolls for network congestion games

• Chaitanya Swamy

FOCS Conference 2006 Conference Paper

The Effectiveness of Lloyd-Type Methods for the k-Means Problem

• Rafail Ostrovsky
• Yuval Rabani
• Leonard J. Schulman
• Chaitanya Swamy

We investigate variants of Lloyd's heuristic for clustering high dimensional data in an attempt to explain its popularity (a half century after its introduction) among practitioners, and in order to suggest improvements in its application. We propose and justify a clusterability criterion for data sets. We present variants of Lloyd's heuristic that quickly lead to provably near-optimal clustering solutions when applied to well-clusterable instances. This is the first performance guarantee for a variant of Lloyd's heuristic. The provision of a guarantee on output quality does not come at the expense of speed: some of our algorithms are candidates for being faster in practice than currently used variants of Lloyd's method. In addition, our other algorithms are faster on well-clusterable instances than recently proposed approximation algorithms, while maintaining similar guarantees on clustering quality. Our main algorithmic contribution is a novel probabilistic seeding process for the starting configuration of a Lloyd-type iteration

SODA Conference 2005 Conference Paper

Network design for information networks

• Ara Hayrapetyan
• Chaitanya Swamy
• Éva Tardos

FOCS Conference 2005 Conference Paper

Sampling-based Approximation Algorithms for Multi-stage Stochastic

• Chaitanya Swamy
• David B. Shmoys

Stochastic optimization problems provide a means to model uncertainty in the input data where the uncertainty is modeled by a probability distribution over the possible realizations of the actual data. We consider a broad class of these problems in which the realized input is revealed through a series of stages, and hence are called multi-stage stochastic programming problems. Our main result is to give the first fully polynomial approximation scheme for a broad class of multi-stage stochastic linear programming problems with any constant number of stages. The algorithm analyzed, known as the sample average approximation (SAA) method, is quite simple, and is the one most commonly used in practice. The algorithm accesses the input by means of a "black box" that can generate, given a series of outcomes for the initial stages, a sample of the input according to the conditional probability distribution (given those outcomes). We use this to obtain the first polynomial-time approximation algorithms for a variety of k-stage generalizations of basic combinatorial optimization problems.

FOCS Conference 2005 Conference Paper

Truthful and Near-Optimal Mechanism Design via Linear Programming

• Ron Lavi
• Chaitanya Swamy

We give a general technique to obtain approximation mechanisms that are truthful in expectation. We show that for packing domains, any /spl alpha/-approximation algorithm that also bounds the integrality gap of the IF relaxation of the problem by a can be used to construct an /spl alpha/-approximation mechanism that is truthful in expectation. This immediately yields a variety of new and significantly improved results for various problem domains and furthermore, yields truthful (in expectation) mechanisms with guarantees that match the best known approximation guarantees when truthfulness is not required. In particular, we obtain the first truthful mechanisms with approximation guarantees for a variety of multi-parameter domains. We obtain truthful (in expectation) mechanisms achieving approximation guarantees of O(/spl radic/m) for combinatorial auctions (CAs), (1 + /spl epsi/ ) for multiunit CAs with B = /spl Omega/(log m) copies of each item, and 2 for multiparameter knapsack problems (multiunit auctions). Our construction is based on considering an LP relaxation of the problem and using the classic VCG mechanism by W. Vickrey (1961), E. Clarke (1971) and T. Groves (1973) to obtain a truthful mechanism in this fractional domain. We argue that the (fractional) optimal solution scaled down by a, where a is the integrality gap of the problem, can be represented as a convex combination of integer solutions, and by viewing this convex combination as specifying a probability distribution over integer solutions, we get a randomized, truthful in expectation mechanism. Our construction can be seen as a way of exploiting VCG in a computational tractable way even when the underlying social-welfare maximization problem is NP-hard.

SODA Conference 2004 Conference Paper

Correlation Clustering: maximizing agreements via semidefinite programming

• Chaitanya Swamy

SODA Conference 2004 Conference Paper

Facility location with Service Installation Costs

• David B. Shmoys
• Chaitanya Swamy
• Retsef Levi

FOCS Conference 2004 Conference Paper

Optimal Power-Down Strategies

• John Augustine 0001
• Sandy Irani
• Chaitanya Swamy

We consider the problem of selecting threshold times to transition a device to low-power sleep states during an idle period. The two-state case in which there is a single active and a single sleep state is a continuous version of the ski-rental problem. We consider a generalized version in which there is more than one sleep state, each with its own power consumption rate and transition costs. We give an algorithm that, given a system, produces a deterministic strategy whose competitive ratio is arbitrarily close to optimal. We also give an algorithm to produce the optimal online strategy given a system and a probability distribution that generates the length of the idle period. We also give a simple algorithm that achieves a competitive ratio of 3 + 2/spl radic/2 /spl ap/ 5. 828 for any system.

FOCS Conference 2004 Conference Paper

Stochastic Optimization is (Almost) as easy as Deterministic Optimization

• David B. Shmoys
• Chaitanya Swamy

Stochastic optimization problems attempt to model uncertainty in the data by assuming that (part of) the input is specified in terms of a probability distribution. We consider the well-studied paradigm of 2-stage models with recourse: first, given only distributional information about (some of) the data one commits on initial actions, and then once the actual data is realized (according to the distribution), further (recourse) actions can be taken. We give the first approximation algorithms for 2-stage discrete stochastic optimization problems with recourse for which the underlying random data is given by a "black box" and no restrictions are placed on the costs in the two stages, based on an FPRAS for the LP relaxation of the stochastic problem (which has exponentially many variables and constraints). Among the range of applications we consider are stochastic versions of the set cover, vertex cover, facility location, multicut (on trees), and multicommodity flow problems.

SODA Conference 2003 Conference Paper

Fault-tolerant facility location

• Chaitanya Swamy
• David B. Shmoys