In k-clustering problems, we are given a metric space (𝒞, d), and must choose a set S of k centers to open. Each client j ∈ 𝒞 incurs an assignment cost, which is the distance between j and center in S that it has been assigned to. In this work, we study the minimum-norm k-clustering problem, where we are given an arbitrary monotone symmetric norm f, and wish to open k centers so as to minimize f(assignment-cost vector). This is a powerful generalization, encompassing many classical k-clustering problems including the k-median, k-means, and k-center problems. A simple and efficient algorithmic idea is that of adaptive sampling, wherein we randomly choose the location of the next center to open with probability proportional to its "cost" under the currently chosen set. While this has yielded fast algorithms for some k-clustering problem, little is known for settings without "min-sum" objectives. We devise the first adaptive-sampling-based bicriteria constant-factor approximation algorithm for general minimum-norm k-clustering, vastly expanding the scope of problems handled by adaptive sampling. For the special case of Top_ℓ norms, which form a building block of monotone symmetric norms, we show that adaptive sampling yields an O(log k)-approximation algorithm.

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.

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.

We consider the {\em correlated knapsack orienteering} (CSKO) problem: we are given a travel budget $B$, processing-time budget $W$, finite metric space $(V,d)$ with root $ρ\in V$, where each vertex is associated with a job with possibly correlated random size and random reward that become known only when the job completes. Random variables are independent across different vertices. The goal is to compute a $ρ$-rooted path of length at most $B$, in a possibly adaptive fashion, that maximizes the reward collected from jobs that are processed by time $W$. To our knowledge, CSKO has not been considered before, though prior work has considered the uncorrelated problem, {\em stochastic knapsack orienteering}, and {\em correlated orienteering}, which features only one budget constraint on the {\em sum} of travel-time and processing-times. We show that the {\em adaptivity gap of CSKO is not a constant, and is at least $Ω\bigl(\max\sqrt{\log{B}},\sqrt{\log\log{W}}\}\bigr)$}. Complementing this, we devise {\em non-adaptive} algorithms that obtain: (a) $O(\log\log W)$-approximation in quasi-polytime; and (b) $O(\log W)$-approximation in polytime. We obtain similar guarantees for CSKO with cancellations, wherein a job can be cancelled before its completion time, foregoing its reward. We also consider the special case of CSKO, wherein job sizes are weighted Bernoulli distributions, and more generally where the distributions are supported on at most two points (2-CSKO). Although weighted Bernoulli distributions suffice to yield an $Ω(\sqrt{\log\log B})$ adaptivity-gap lower bound for (uncorrelated) {\em stochastic orienteering}, we show that they are easy instances for CSKO. We develop non-adaptive algorithms that achieve $O(1)$-approximation in polytime for weighted Bernoulli distributions, and in $(n+\log B)^{O(\log W)}$-time for the more general case of 2-CSKO.

We investigate a genre of vehicle-routing problems (VRPs), that we call max-reward VRPs, wherein nodes located in a metric space have associated rewards that depend on their visiting times, and we seek a path that earns maximum reward. A prominent problem in this genre is deadline TSP, where nodes have deadlines and we seek a path that visits all nodes by their deadlines and earns maximum reward. Our main result is a constant-factor approximation for deadline TSP running in time O(n^O(log(nΔ))) in metric spaces with integer distances at most Δ. This is the first improvement over the approximation factor of O(log n) due to Bansal et al. [N. Bansal et al., 2004] in over 15 years (but is achieved in super-polynomial time). Our result provides the first concrete indication that log n is unlikely to be a real inapproximability barrier for deadline TSP, and raises the exciting possibility that deadline TSP might admit a polytime constant-factor approximation. At a high level, we obtain our result by carefully guessing an appropriate sequence of O(log (nΔ)) nodes appearing on the optimal path, and finding suitable paths between any two consecutive guessed nodes. We argue that the problem of finding a path between two consecutive guessed nodes can be relaxed to an instance of a special case of deadline TSP called point-to-point (P2P) orienteering. Any approximation algorithm for P2P orienteering can then be utilized in conjunction with either a greedy approach, or an LP-rounding approach, to find a good set of paths overall between every pair of guessed nodes. While concatenating these paths does not immediately yield a feasible solution, we argue that it can be covered by a constant number of feasible solutions. Overall our result therefore provides a novel reduction showing that any α-approximation for P2P orienteering can be leveraged to obtain an O(α)-approximation for deadline TSP in O(n^O(log nΔ)) time. Our results extend to yield the same guarantees (in approximation ratio and running time) for a substantial generalization of deadline TSP, where the reward obtained by a client is given by an arbitrary non-increasing function (specified by a value oracle) of its visiting time. Finally, we discuss applications of our results to variants of deadline TSP, including settings where both end-nodes are specified, nodes have release dates, and orienteering with time windows.

We consider the minimum-norm load-balancing (MinNormLB) problem, wherein there are n jobs, each of which needs to be assigned to one of m machines, and we are given the processing times {p_{ij}} of the jobs on the machines. We also have a monotone, symmetric norm f:ℝ^m → ℝ_{≥ 0}. We seek an assignment σ of jobs to machines that minimizes the f-norm of the induced load vector load->_σ ∈ ℝ_{≥ 0}^m, where load_σ(i) = ∑_{j:σ(j) = i}p_{ij}. This problem was introduced by [Deeparnab Chakrabarty and Chaitanya Swamy, 2019], and the current-best result for MinNormLB is a (4+ε)-approximation [Deeparnab Chakrabarty and Chaitanya Swamy, 2019]. In the stochastic version of MinNormLB, the job processing times are given by nonnegative random variables X_{ij}, and jobs are independent; the goal is to find an assignment σ that minimizes the expected f-norm of the induced random load vector. We obtain results that (essentially) match the best-known guarantees for deterministic makespan minimization (MinNormLB with 𝓁_∞ norm). For MinNormLB, we obtain a (2+ε)-approximation for unrelated machines, and a PTAS for identical machines. For stochastic MinNormLB, we consider the setting where the X_{ij}s are Poisson random variables, denoted PoisNormLB. Our main result here is a novel and powerful reduction showing that, for any machine environment (e.g., unrelated/identical machines), any α-approximation algorithm for MinNormLB in that machine environment yields a randomized α(1+ε)-approximation for PoisNormLB in that machine environment. Combining this with our results for MinNormLB, we immediately obtain a (2+ε)-approximation for PoisNormLB on unrelated machines, and a PTAS for PoisNormLB on identical machines. The latter result substantially generalizes a PTAS for makespan minimization with Poisson jobs obtained recently by [Anindya De et al., 2020].

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) ≤ Bl, 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 Topl-norms; and (2) showing how to tackle expected Topl-norm minimization by leveraging techniques used to deal with minimizing the expected maximum, circumventing the difficulties posed by the non-separable nature of Toplnorms.

This special section comprises nine fully refereed papers whose extended abstracts were presented at the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017) in Berkeley, California, on October 15--17, 2017. The preliminary conference versions of these papers were published by in the FOCS 2017 proceedings. The regular conference program consisted of 90 papers chosen from among 323 submissions. They were selected by a program committee consisting of Aditya Bhaskara, Andrej Bogdanov, Vladimir Braverman, Shiri Chechik, Gil Cohen, Anindya De, Ankit Garg, Josh Grochow, Sean Hallgren, Valentine Kabanets, Gillat Kol, Ravi Kumar, Chris Peikert, Sofya Raskhodnikova, Rahul Santhanam, Yaron Singer, Chaitanya Swamy, Amnon Ta-Shma, Chris Umans (chair), Vinod Vaikuntanathan, Emanuele Viola, Omri Weinstein, and Amir Yehudayoff. The papers invited to this special section were also chosen with the input of the program committee. The nine papers in this section span a broad range of topics, including cryptography, approximation algorithms, hardness of approximation, complexity theory, communication complexity, graph sparsification, and error-correcting codes. Each paper underwent an extensive refereeing process. We thank the authors and the anonymous referees for their efforts. In addition, we would like to thank SICOMP Editors-in-Chief Leonard Schulman and Robert Krauthgamer and SIAM Senior Publications Coordinator Heather Blythe for their help in preparing this special section.

Recently, Chakrabarty and Swamy (STOC 2019) introduced the {\em minimum-norm load-balancing} problem on unrelated machines, wherein we are given a set $J$ of jobs that need to be scheduled on a set of $m$ unrelated machines, and a monotone, symmetric norm; We seek an assignment $\sg:J\mapsto[m]$ that minimizes the norm of the resulting load vector $\lvec_\sg\in\R_+^m$, where $\lvec_\sg(i)$ is the load on machine $i$ under the assignment $\sg$. Besides capturing all $\ell_p$ norms, symmetric norms also capture other norms of interest including top-$\ell$ norms, and ordered norms. Chakrabarty and Swamy (STOC 2019) give a $(38+\ve)$-approximation algorithm for this problem via a general framework they develop for minimum-norm optimization that proceeds by first carefully reducing this problem (in a series of steps) to a problem called \minmax ordered load balancing, and then devising a so-called deterministic oblivious LP-rounding algorithm for ordered load balancing. We give a direct, and simple $4$-approximation algorithm for the minimum-norm load balancing based on rounding a (near-optimal) solution to a novel convex-programming relaxation for the problem. Whereas the natural convex program encoding minimum-norm load balancing problem has a large non-constant integrality gap, we show that this issue can be remedied by including a key constraint that bounds the "norm of the job-cost vector." Our techniques also yield a (essentially) $4$-approximation for: (a) {\em multi-norm load balancing}, wherein we are given multiple monotone symmetric norms, and we seek an assignment respecting a given budget for each norm; (b) the best {\em simultaneous approximation factor} achievable for all symmetric norms for a given instance.

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.

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 study inverse optimization problems, wherein the goal is to map given solutions to an underlying optimization problem to a cost vector for which the given solutions are the (unique) optimal solutions. Inverse optimization problems find diverse applications and have been widely studied. A prominent problem in this field is the inverse shortest path (ISP) problem [D. Burton and Ph.L. Toint, 1992; W. Ben-Ameur and E. Gourdin, 2004; A. Bley, 2007], which finds applications in shortest-path routing protocols used in telecommunications. Here we seek a cost vector that is positive, integral, induces a set of given paths as the unique shortest paths, and has minimum l_infty norm. Despite being extensively studied, very few algorithmic results are known for inverse optimization problems involving integrality constraints on the desired cost vector whose norm has to be minimized. Motivated by ISP, we initiate a systematic study of such integral inverse optimization problems from the perspective of designing polynomial time approximation algorithms. For ISP, our main result is an additive 1-approximation algorithm for multicommodity ISP with node-disjoint commodities, which we show is tight assuming P!=NP. We then consider the integral-cost inverse versions of various other fundamental combinatorial optimization problems, including min-cost flow, max/min-cost bipartite matching, and max/min-cost basis in a matroid, and obtain tight or nearly-tight approximation guarantees for these. Our guarantees for the first two problems are based on results for a broad generalization, namely integral inverse polyhedral optimization, for which we also give approximation guarantees. Our techniques also give similar results for variants, including l_p-norm minimization of the integral cost vector, and distance-minimization from an initial cost vector.

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+ε)$-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+ε)$-approximation algorithm for $\{0,1\}$ weights.

We study the problem of automatically and efficiently generating itineraries for users who are on vacation. We focus on the common case, wherein the trip duration is more than a single day. Previous efficient algorithms based on greedy heuristics suffer from two problems. First, the itineraries are often unbalanced, with excellent days visiting top attractions followed by days of exclusively lower-quality alternatives. Second, the trips often re-visit neighborhoods repeatedly in order to cover increasingly low-tier points of interest. Our primary technical contribution is an algorithm that addresses both these problems by maximizing the quality of the worst day. We give theoretical results showing that this algorithm»s competitive factor is within a factor two of the guarantee of the best available algorithm for a single day, across many variations of the problem. We also give detailed empirical evaluations using two distinct datasets:(a) anonymized Google historical visit data and(b) Foursquare public check-in data. We show first that the overall utility of our itineraries is almost identical to that of algorithms specifically designed to maximize total utility, while the utility of the worst day of our itineraries is roughly twice that obtained from other approaches. We then turn to evaluation based on human raters who score our itineraries only slightly below the itineraries created by human travel experts with deep knowledge of the area.

Motivated by the popularity of online ride and delivery services, we study natural variants of classical multi-vehicle minimum latency problems where the objective is to route a set of vehicles located at depots to serve requests located on a metric space so as to minimize the total latency. In this paper, we consider point-to-point requests that come with source-destination pairs and release-time constraints that restrict when each request can be served. The point-to-point requests and release-time constraints model taxi rides and deliveries. For all the variants considered, we show constant-factor approximation algorithms based on a linear programming framework. To the best of our knowledge, these are the first set of results for the aforementioned variants of the minimum latency problems. Furthermore, we provide an empirical study of heuristics based on our theoretical algorithms on a real data set of taxi rides.

We consider a facility-location problem that abstracts settings where the cost of serving the clients assigned to a facility is incurred by the facility. Formally, we consider the minimum-load k-facility location (ML k FL) problem, which is defined as follows. We have a set F of facilities, a set C of clients, and an integer k ≥ 0. Assigning client j to a facility f incurs a connection cost d ( f , j ). The goal is to open a set F ⊆ F of k facilities and assign each client j to a facility f ( j )∈ F so as to minimize max f ∈ F ∑ j ∈ C : f ( j )= f d ( f , j ); we call ∑ j ∈ C : f ( j )= f d ( f , j ) the load of facility f . This problem was studied under the name of min-max star cover in References [3, 7], who (among other results) gave bicriteria approximation algorithms for ML k FL for when F = C . ML k FL is rather poorly understood, and only an O ( k )-approximation is currently known for ML k FL, even for line metrics . Our main result is the first polytime approximation scheme (PTAS) for ML k FL on line metrics (note that no non-trivial true approximation of any kind was known for this metric). Complementing this, we prove that ML k FL is strongly NP -hard on line metrics. We also devise a quasi-PTAS for ML k FL on tree metrics. ML k FL turns out to be surprisingly challenging even on line metrics and resilient to attack by a variety of techniques that have been successfully applied to facility-location problems. For instance, we show that (a) even a configuration-style LP-relaxation has a bad integrality gap and (b) a multi-swap k -median style local-search heuristic has a bad locality gap. Thus, we need to devise various novel techniques to attack ML k FL. Our PTAS for line metrics consists of two main ingredients. First, we prove that there always exists a near-optimal solution possessing some nice structural properties. A novel aspect of this proof is that we first move to a mixed-integer LP (MILP) encoding of the problem and argue that a MILP-solution minimizing a certain potential function possesses the desired structure and then use a rounding algorithm for the generalized-assignment problem to “transfer” this structure to the rounded integer solution. Complementing this, we show that these structural properties enable one to find such a structured solution via dynamic programming.

In the prize-collecting Steiner forest (PCSF) problem, we are given an undirected graph G=(V,E), nonnegative edge costs {c_e} for e in E, terminal pairs {(s_i,t_i)} for i=1,...,k, and penalties {pi_i} for i=1,...,k for each terminal pair; the goal is to find a forest F to minimize c(F) + sum{ pi_i: (s_i,t_i) is not connected in F }. The Steiner forest problem can be viewed as the special case where pi_i are infinite for all i. It was widely believed that the integrality gap of the natural (and well-studied) linear-programming (LP) relaxation for PCSF (PCSF-LP) is at most 2. We dispel this belief by showing that the integrality gap of this LP is at least 9/4 even if the input instance is planar. We also show that using this LP, one cannot devise a Lagrangian-multiplier-preserving (LMP) algorithm with approximation guarantee better than 4. Our results thus show a separation between the integrality gaps of the LP-relaxations for prize-collecting and non-prize-collecting (i.e., standard) Steiner forest, as well as the approximation ratios achievable relative to the optimal LP solution by LMP- and non-LMP-approximation algorithms for PCSF. For the special case of prize-collecting Steiner tree (PCST), we prove that the natural LP relaxation admits basic feasible solutions with all coordinates of value at most 1/3 and all edge variables positive. Thus, we rule out the possibility of approximating PCST with guarantee better than 3 using a direct iterative rounding method.

We consider the MST-interdiction problem: given a multigraph G = (V, E), edge weights {w_e >= 0}_{e in E}, interdiction costs {c_e >= 0}_{e in E}, and an interdiction budget B >= 0, the goal is to remove a subset R of edges of total interdiction cost at most B so as to maximize the w-weight of an MST of G-R:=(V,E-R). Our main result is a 4-approximation algorithm for this problem. This improves upon the previous-best 14-approximation [Zenklusen, FOCS 2015]. Notably, our analysis is also significantly simpler and cleaner than the one in [Zenklusen, FOCS 2015]. Whereas Zenklusen uses a greedy algorithm with an involved analysis to extract a good interdiction set from an over-budget set, we utilize a generalization of knapsack called the tree knapsack problem that nicely captures the key combinatorial aspects of this "extraction problem." We prove a simple, yet strong, LP-relative approximation bound for tree knapsack, which leads to our improved guarantees for MST interdiction. Our algorithm and analysis are nearly tight, as we show that one cannot achieve an approximation ratio better than 3 relative to the upper bound used in our analysis (and the one in [Zenklusen, FOCS 2015]). Our guarantee for MST-interdiction yields an 8-approximation for metric-TSP interdiction (improving over the 28-approximation in [Zenklusen, FOCS 2015]). We also show that maximum-spanning-tree interdiction is at least as hard to approximate as the minimization version of densest-k-subgraph.

We consider clustering problems with non-uniform lower bounds and outliers, and obtain the first approximation guarantees for these problems. We have a set F of facilities with lower bounds {L_i}_{i in F} and a set D of clients located in a common metric space {c(i,j)}_{i,j in F union D}, and bounds k, m. A feasible solution is a pair (S subseteq F, sigma: D -> S union {out}), where sigma specifies the client assignments, such that |S| <=k, |sigma^{-1}(i)| >= L_i for all i in S, and |sigma^{-1}(out)| <= m. In the lower-bounded min-sum-of-radii with outliers P (LBkSRO) problem, the objective is to minimize sum_{i in S} max_{j in sigma^{-1})i)}, and in the lower-bounded k-supplier with outliers (LBkSupO) problem, the objective is to minimize max_{i in S} max_{j in sigma^{-1})i)} c(i,j). We obtain an approximation factor of 12.365 for LBkSRO, which improves to 3.83 for the non-outlier version (i.e., m = 0). These also constitute the first approximation bounds for the min-sum-of-radii objective when we consider lower bounds and outliers separately. We apply the primal-dual method to the relaxation where we Lagrangify the |S| <= k constraint. The chief technical contribution and novelty of our algorithm is that, departing from the standard paradigm used for such constrained problems, we obtain an O(1)-approximation despite the fact that we do not obtain a Lagrangian-multiplier-preserving algorithm for the Lagrangian relaxation. We believe that our ideas have broader applicability to other clustering problems with outliers as well. We obtain approximation factors of 5 and 3 respectively for LBkSupO and its non-outlier version. These are the first approximation results for k-supplier with non-uniform lower bounds.

We study the optimization problem faced by a perfectly informed principal in a Bayesian game, who reveals information to the players about the state of nature to obtain a desirable equilibrium. This signaling problem is the natural design question motivated by uncertainty in games and has attracted much recent attention. We present new hardness results for signaling problems in (a) Bayesian two-player zero-sum games, and (b) Bayesian network routing games.

We consider the matroid median problem [Krishnaswamy et al. 2011], wherein we are given a set of facilities with opening costs and a matroid on the facility-set, and clients with demands and connection costs, and we seek to open an independent set of facilities and assign clients to open facilities so as to minimize the sum of the facility-opening and client-connection costs. We give a simple 8-approximation algorithm for this problem based on LP-rounding, which improves upon the 16-approximation in Krishnaswamy et al. [2011]. We illustrate the power and versatility of our techniques by deriving (a) an 8-approximation for the two-matroid median problem, a generalization of matroid median that we introduce involving two matroids; and (b) a 24-approximation algorithm for matroid median with penalties , which is a vast improvement over the 360-approximation obtained in Krishnaswamy et al. [2011]. We show that a variety of seemingly disparate facility-location problems considered in the literature—data placement problem, mobile facility location, k -median forest, metric uniform minimum-latency Uncapacitated Facility Location (UFL)—in fact reduce to the matroid median or two-matroid median problems, and thus obtain improved approximation guarantees for all these problems. Our techniques also yield an improvement for the knapsack median problem.

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(log2 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 (DkS) 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 DkS on graphs, and proving the existence of a family of one-way functions. Previously, only NP-hardness of k-(s; t)-Cut was known.

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.

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.

We consider a facility-location problem that abstracts settings where the cost of serving the clients assigned to a facility is incurred by the facility. Formally, we consider the minimum-load k-facility location (MLkFL) problem, which is defined as follows. We have a set F of facilities, a set C of clients, and an integer k > 0. Assigning client j to a facility f incurs a connection cost d(f, j). The goal is to open a set F' of k facilities, and assign each client j to a facility f(j) in F' so as to minimize maximum, over all facilities in F', of the sum of distances of clients j assigned to F' to F'. We call this sum the load of facility f. This problem was studied under the name of min-max star cover in [6, 2], who (among other results) gave bicriteria approximation algorithms for MLkFL for when F = C. MLkFL is rather poorly understood, and only an O(k)-approximation is currently known for MLkFL, even for line metrics. Our main result is the first polynomial time approximation scheme (PTAS) for MLkFL on line metrics (note that no non-trivial true approximation of any kind was known for this metric). Complementing this, we prove that MLkFL is strongly NP-hard on line metrics. We also devise a quasi-PTAS for MLkFL on tree metrics. MLkFL turns out to be surprisingly challenging even on line metrics, and resilient to attack by the variety of techniques that have been successfully applied to facility-location problems. For instance, we show that: (a) even a configuration-style LP-relaxation has a bad integrality gap; and (b) a multi-swap k-median style local-search heuristic has a bad locality gap. Thus, we need to devise various novel techniques to attack MLkFL. Our PTAS for line metrics consists of two main ingredients. First, we prove that there always exists a near-optimal solution possessing some nice structural properties. A novel aspect of this proof is that we first move to a mixed-integer LP (MILP) encoding the problem, and argue that a MILP-solution minimizing a certain potential function possesses the desired structure, and then use a rounding algorithm for the generalized-assignment problem to "transfer" this structure to the rounded integer solution. Complementing this, we show that these structural properties enable one to find such a structured solution via dynamic programming.

We consider the matroid median problem, wherein we are given a set of facilities with opening costs and a matroid on the facility-set, and clients with demands and connection costs, and we seek to open an independent set of facilities and assign clients to open facilities so as to minimize the sum of the facility-opening and client-connection costs. We give a simple 8-approximation algorithm for this problem based on LP-rounding, which improves upon the 16-approximation by Krishnaswamy et al. We illustrate the power and versatility of our techniques by deriving: (a) an 8-approximation for the two-matroid median problem, a generalization of matroid median that we introduce involving two matroids; and (b) a 24-approximation algorithm for matroid median with penalties, which is a vast improvement over the 360-approximation obtained by Krishnaswamy et al. We show that a variety of seemingly disparate facility-location problems considered in the literature -- data placement problem, mobile facility location, k-median forest, metric uniform minimum-latency UFL -- in fact reduce to the matroid median or two-matroid median problems, and thus obtain improved approximation guarantees for all these problems. Our techniques also yield an improvement for the knapsack median problem.

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.

In this paper, we study mechanism design problems in the ordinal setting wherein the preferences of agents are described by orderings over outcomes, as opposed to specific numerical values associated with them. This setting is relevant when agents can compare outcomes, but aren't able to evaluate precise utilities for them. Such a situation arises in diverse contexts including voting and matching markets.

We give an algorithm for learning a mixture of unstructured distributions. This problem arises in various unsupervised learning scenarios, for example in learning topic models from a corpus of documents spanning several topics. We show how to learn the constituents of a mixture of k arbitrary distributions over a large discrete domain [n]={1, 2, ...,n} and the mixture weights, using O(n polylog n) samples. (In the topic-model learning setting, the mixture constituents correspond to the topic distributions.)

We consider vehicle-routing problems (VRPs) that incorporate the notion of regret of a client, which is a measure of the waiting time of a client relative to its shortest-path distance from the depot. Formally, we consider both the additive and multiplicative versions of, what we call, the regret-bounded vehicle routing problem (RVRP). In these problems, we are given an undirected complete graph G = ({r} ∪ V,E) on n nodes with a distinguished root (depot) node r, edge costs {cuv} that form a metric, and a regret bound R. Given a path P rooted at r and a node v ∈ P, let cP(v) be the distance from r to v along P. The goal is to find the fewest number of paths rooted at r that cover all the nodes so that for every node v covered by (say) path P: (i) its additive regret cP(v) -- crv, with respect to P is at most R in additive-RVRP; or (ii) its multiplicative regret, cP(v)/crv, with respect to P is at most R in multiplicative-RVRP.

We consider the mobile facility location (MFL) problem. We are given a set of facilities and clients located in a common metric space G = (V, c). The goal is to move each facility from its initial location to a destination (in V) and assign each client to the destination of some facility so as to minimize the sum of the movement-costs of the facilities and the client-assignment costs. This abstracts facility-location settings where one has the flexibility of moving facilities from their current locations to other destinations so as to serve clients more efficiently by reducing their assignment costs. We give the first local-search based approximation algorithm for this problem and achieve the best-known approximation guarantee. Our main result is (3 + ε)-approximation for this problem for any constant ε > 0 using local search. The previous best guarantee for MFL was an 8-approximation algorithm due to Friggstad and Salavatipour [12] based on LP-rounding. Our guarantee matches the best-known approximation guarantee for the k-median problem. Since there is an approximation-preserving reduction from the k-median problem to MFL, any improvement of our result would imply an analogous improvement for the k-median problem. Furthermore, our analysis is tight (up to o(1) factors) since the tight example for the local-search based 3-approximation algorithm for k-median can be easily adapted to show that our local-search algorithm has a tight approximation ratio of 3. Our results extend to the weighted generalization wherein each facility i has a non-negative weight wi and the movement cost for i is wi times the distance traveled by i. In contrast to the k-median problem, the local search procedure that moves, at each step, a constant number of facilities (to chosen destinations) and assigns each client to the nearest destination, is known to have an unbounded locality gap. Our local-search algorithm is a natural and simple variant, where we only select the destinations of the facilities in each step and optimally rematch the facilities to these destinations (which might entail moving all facilities). One of the chief novelties in the analysis is that in order to generate a suitable collection of local-search moves whose resulting inequalities yield the desired bound on the cost of a local-optimum, we define a tree-like structure that (loosely speaking) functions as a “recursion tree”, using which we spawn off local-search moves by exploring this tree to a constant depth.

We consider the design of strategyproof cost-sharing mechanisms. We give two simple, but extremely versatile, black-box reductions, that in combination reduce the cost-sharing mechanism-design problem to the algorithmic problem of finding a minimum-cost solution for a set of players. Our first reduction shows that any truthful, α-approximation mechanism for the social-cost minimization (SCM) problem satisfying a technical no-bossiness condition can be morphed into a truthful mechanism that achieves an O(α log n)-approximation where the prices recover the cost incurred. Thus, we decouple the task of truthfully computing an outcome with near-optimal social cost from the cost-sharing problem. This is fruitful since truthful mechanism-design, especially for single-dimensional problems, is a relatively well-understood and manageable task. Our second reduction nicely complements the first one by showing that any LP-based ρ-approximation for the problem of finding a min-cost solution for a set of players yields a truthful, no-bossy, (ρ + 1)-approximation for the SCM problem (and hence, a truthful (ρ + 1)log n-approximation cost-sharing mechanism). These reductions find a slew of applications, yielding, as corollaries, the first or improved polytime cost-sharing mechanisms for a variety of problems. For example, our first reduction coupled with the celebrated VCG mechanism shows that for any cost-sharing problem (with a monotone cost function) one can obtain a truthful mechanism that achieves an O(log n)-approximation where the prices recover the cost incurred. Other applications include O(log n)-approximation mechanisms for: survivable network design problems, facility location (FL) problems including capacitated and connected FL problems, and minimum-makespan scheduling on unrelated machines. Our results demonstrate that in contrast with our current understanding of group-strategyproof and acyclic mechanisms, strategyproofness allows for ample flexibility in cost-sharing mechanism design enabling one to effectively leverage various algorithmic results.

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 aclusterabilitycriterion 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 beingfaster in practicethan 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.

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 multistage stochastic programming problems. Multistage stochastic programming and, in particular, multistage stochastic linear programs with full recourse, is a domain that has received a great deal of attention within the operations research community, mostly from the perspective of computational results in application settings. Our main result is to give the first fully polynomial approximation scheme for a broad class of multistage stochastic linear programming problems with any constant number of stages. The algorithm analyzed, known as the sample average approximation 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 approximation algorithms for a variety of $k$-stage generalizations of basic combinatorial optimization problems including the set cover, vertex cover, multicut on trees, facility location, and multicommodity flow problems.

It is well known that in a network with arbitrary (convex) latency functions that are a function of edge traffic, the worst-case ratio, over all inputs, of the system delay caused due to selfish behavior versus the system delay of the optimal centralized solution may be unbounded even if the system consists of only two parallel links. This ratio is called the price of anarchy (PoA). In this article, we investigate ways by which one can reduce the performance degradation due to selfish behavior. We investigate two primary methods (a) Stackelberg routing strategies , where a central authority, for example, network manager, controls a fixed fraction of the flow, and can route this flow in any desired way so as to influence the flow of selfish users; and (b) network tolls , where tolls are imposed on the edges to modify the latencies of the edges, and thereby influence the induced Nash equilibrium. We obtain results demonstrating the effectiveness of both Stackelberg strategies and tolls in controlling the price of anarchy. For Stackelberg strategies, we obtain the first results for nonatomic routing in graphs more general than parallel-link graphs, and strengthen existing results for parallel-link graphs. (i) In series-parallel graphs, we show that Stackelberg routing reduces the PoA to a constant (depending on the fraction of flow controlled). (ii) For general graphs, we obtain latency-class specific bounds on the PoA with Stackelberg routing, which give a continuous trade-off between the fraction of flow controlled and the price of anarchy. (iii) In parallel-link graphs, we show that for any given class L of latency functions, Stackelberg routing reduces the PoA to at most α + (1-α)ċρ( L ), where α is the fraction of flow controlled and ρ( L ) is the PoA of class L (when α = 0). For network tolls, motivated by the known strong results for nonatomic games, we consider the more general setting of atomic splittable routing games. We show that tolls inducing an optimal flow always exist, even for general asymmetric games with heterogeneous users, and can be computed efficiently by solving a convex program . This resolves a basic open question about the effectiveness of tolls for atomic splittable games. Furthermore, we give a complete characterization of flows that can be induced via tolls.

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.

We give a general technique to obtain approximation mechanisms that are truthful in expectation. We show that for packing domains, any α -approximation algorithm that also bounds the integrality gap of the LP relaxation of the problem by α can be used to construct an α -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 multiparameter domains. We obtain truthful (in expectation) mechanisms achieving approximation guarantees of O (√ m ) for combinatorial auctions (CAs), (1 + ϵ ) for multiunit CAs with B = Ω (log m ) copies of each item, and 2 for multiparameter knapsack problems (multi-unit auctions). Our construction is based on considering an LP relaxation of the problem and using the classic VCG mechanism to obtain a truthful mechanism in this fractional domain. We argue that the (fractional) optimal solution scaled down by α , where α 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.

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 umax), where OPT is the optimal value of the SWM problem, and umaxis the maximum supply of an item. This immediately yields approximation guarantees of O(radicmlog umax) for the general single-minded envy-free problem; and O(log umax) 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 umax) 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.

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\sqrt{2} \approx 5.828$ for any system.

We develop approximation algorithms for the problem of placing replicated data in arbitrary networks, where the nodes may both issue requests for data objects and have capacity for storing data objects so as to minimize the average data-access cost. We introduce the data placement problem to model this problem. We have a set of caches $\mathcal{F}$, a set of clients $\mathcal{D}$, and a set of data objects $\mathcal{O}$. Each cache i can store at most $u_i$ data objects. Each client $j\in\mathcal{D}$ has demand $d_j$ for a specific data object $o(j)\in\mathcal{O}$ and has to be assigned to a cache that stores that object. Storing an object o in cache i incurs a storage cost of $f_i^o$, and assigning client j to cache i incurs an access cost of $d_jc_{ij}$. The goal is to find a placement of the data objects to caches respecting the capacity constraints, and an assignment of clients to caches so as to minimize the total storage and client access costs. We present a 10-approximation algorithm for this problem. Our algorithm is based on rounding an optimal solution to a natural linear-programming relaxation of the problem. One of the main technical challenges encountered during rounding is to preserve the cache capacities while incurring only a constant-factor increase in the solution cost. We also introduce the connected data placement problem to capture settings where write-requests are also issued for data objects, so that one requires a mechanism to maintain consistency of data. We model this by requiring that all caches containing a given object be connected by a Steiner tree to a root for that object, which issues a multicast message upon a write to (any copy of) that object. The total cost now includes the cost of these Steiner trees. We devise a 14-approximation algorithm for this problem. We show that our algorithms can be adapted to handle two variants of the problem: (a) a k-median variant, where there is a specified bound on the number of caches that may contain a given object, and (b) a generalization where objects have lengths and the total length of the objects stored in any cache must not exceed its capacity.

We consider a fault-tolerant generalization of the classical uncapacitated facility location problem, where each client j has a requirement that r j distinct facilities serve it, instead of just one. We give a 2.076-approximation algorithm for this problem using LP rounding, which is currently the best-known performance guarantee. Our algorithm exploits primal and dual complementary slackness conditions and is based on clustered randomized rounding . A technical difficulty that we overcome is the presence of terms with negative coefficients in the dual objective function, which makes it difficult to bound the cost in terms of dual variables. For the case where all requirements are the same, we give a primal-dual 1.52-approximation algorithm. We also consider a fault-tolerant version of the k -median problem. In the metric k -median problem, we are given n points in a metric space. We must select k of these to be centers, and then assign each input point j to the selected center that is closest to it. In the fault-tolerant version we want j to be assigned to r j distinct centers. The goal is to select the k centers so as to minimize the sum of assignment costs. The primal-dual algorithm for fault-tolerant facility location with uniform requirements also yields a 4-approximation algorithm for the fault-tolerant k -median problem for this case. This the first constant-factor approximation algorithm for the uniform requirements case.

We consider the problem of makespan minimization on m unrelated machines in the context of algorithmic mechanism design, where the machines are the strategic players. This is a multidimensional scheduling domain, and the only known positive results for makespan minimization in such a domain are O(m)-approximation truthful mechanisms [22, 20]. We study a well-motivated special case of this problem, where the processing time of a job on each machine may either be "low" or "high", and the low and high values are public and job-dependent. This preserves the multidimensionality of the domain, and generalizes the restricted-machines (i.e., {pj,∞}) setting in scheduling. We give a general technique to convert any c-approximation algorithm to a 3c-approximation truthful-in-expectation mechanism. This is one of the few known results that shows how to export approximation algorithms for a multidimensional problem into truthful mechanisms in a black-box fashion. When the low and high values are the same for all jobs, we devise a deterministic 2-approximation truthful mechanism. These are the first truthful mechanisms with non-trivial performance guarantees for a multidimensional scheduling domain.

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

Stochastic optimization problems attempt to model uncertainty in the data by assuming that the input is specified by 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 show that for a broad class of 2-stage linear models with recourse, one can, for any ϵ > 0, in time polynomial in 1/ϵ and the size of the input, compute a solution of value within a factor (1+ϵ) of the optimum, in spite of the fact that exponentially many second-stage scenarios may occur. In conjunction with a suitable rounding scheme, this yields the first approximation algorithms for 2-stage stochastic integer optimization problems where the underlying random data is given by a “black box” and no restrictions are placed on the costs in the two stages. Our rounding approach for stochastic integer programs shows that an approximation algorithm for a deterministic analogue yields, with a small constant-factor loss, provably near-optimal solutions for the stochastic generalization. Among the range of applications, we consider are stochastic versions of the multicommodity flow, set cover, vertex cover, and facility location problems.

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.

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.

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.

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.