Nearest neighbor search is a fundamental data structure problem with many applications. Although the main objective of the data structure is to quickly report data points that are closest to a given query, it has long been noted that without additional constraints the reported answers can be redundant and/or duplicative. This issue is typically addressed in two stages: in the first stage, the algorithm retrieves a (large) number $r$ of points closest to the query, while in the second stage, the $r$ points are post-processed and a small subset is selected to maximize the desired diversity objective. Although popular, this method suffers from a fundamental efficiency bottleneck, as the set of points retrieved in the first stage often needs to be much larger than the final output. In this paper we present provably efficient algorithms for approximate nearest neighbor search with diversity constraints that bypass this two stage process. Our algorithms are based on popular graph-based methods, which allows us to ``piggy-back'' on the existing efficient implementations. These are the first graph-based algorithms for nearest neighbor search with diversity constraints. For data sets with low intrinsic dimension, our data structures report a diverse set of $k$ points approximately closest to the query, in time that only depends on $k$ and $\log \Delta$, where $\Delta$ is the ratio of the diameter to the closest pair distance in the data set. This bound is qualitatively similar to the best known bounds for standard (non-diverse) graph-based algorithms. Our experiments show that the search time of our algorithms is substantially lower than that using the standard two-stage approach.

Graph-based data structures have become powerful and ubiquitous tools for scalable approximate nearest-neighbor (ANN) search over the past decade. In spite of their apparent practical performance, there has only recently been progress on the **worst-case** performance of these data structures. Indeed, the influential work of Indyx and Xu (2023) introduced the key concept of $\alpha$-reachable graphs, showing that graphs constructed by the DiskANN algorithm (Subramanya, et. al. 2023) produce an $\left(\frac{\alpha+1}{\alpha-1}\right)$-approximate solution with a simple best-first search that runs in poly-logarithmic query time. In our work, we improve and generalize this analysis as follows: - We introduce **sorted** $\alpha$-reachable graphs, and use this notion to obtain a stronger approximation factor of $\frac{\alpha}{\alpha-1}$ for the DiskANN algorithm on Euclidean metrics. - We present the **first** worst-case theoretical analysis for the popular **beam-search** algorithm, which is used in practice to search these graphs for $k > 1$ candidate nearest neighbors. We also present empirical results validating the significance of sorted $\alpha$-reachable graphs, which aligns with our theoretical findings.

Vector indexing enables semantic search over diverse corpora and has become an important interface to databases for both users and AI agents. Efficient vector search requires deep optimizations in database systems. This has motivated a new class of specialized vector databases that optimize for vector search quality and cost. Instead, we argue that a scalable, high-performance, and cost-efficient vector search system can be built inside a cloud-native operational database like Azure Cosmos DB while leveraging the benefits of a distributed database such as high availability, durability, and scale. We do this by deeply integrating DiskANN, a state-of-the-art vector indexing library, inside Azure Cosmos DB NoSQL. This system uses a single vector index per partition stored in existing index trees, and kept in sync with underlying data. It supports < 20ms query latency over an index spanning 10 million vectors, has stable recall over updates, and offers approximately 43× and 12× lower query cost compared to Pinecone and Zilliz serverless enterprise products. It also scales out to billions of vectors via automatic partitioning. This convergent design presents a point in favor of integrating vector indices into operational databases in the context of recent debates on specialized vector databases, and offers a template for vector indexing in other databases.

In this paper we study two fully-dynamic multi-dimensional vector load balancing problems with recourse. The adversary presents a stream of n job insertions and deletions, where each job j is a vector in ℝ^d_{≥ 0}. In the vector scheduling problem, the algorithm must maintain an assignment of the active jobs to m identical machines to minimize the makespan (maximum load on any dimension on any machine). In the vector bin packing problem, the algorithm must maintain an assignment of active jobs into a number of bins of unit capacity in all dimensions, to minimize the number of bins currently used. In both problems, the goal is to maintain solutions that are competitive against the optimal solution for the active set of jobs, at every time instant. The algorithm is allowed to change the assignment from time to time, with the secondary objective of minimizing the amortized recourse, which is the average cardinality of the change of the assignment per update to the instance. For the vector scheduling problem, we present two simple algorithms. The first is a randomized algorithm with an O(1) amortized recourse and an O(log d/log log d) competitive ratio against oblivious adversaries. The second algorithm is a deterministic algorithm that is competitive against adaptive adversaries but with a slightly higher competitive ratio of O(log d) and a per-job recourse guarantee bounded by Õ(log n + log d log OPT). We also prove a sharper instance-dependent recourse guarantee for the deterministic algorithm. For the vector bin packing problem, we make the so-called small jobs assumption that the size of all jobs in all the coordinates is O(1/log d) and present a simple O(1)-competitive algorithm with O(log n) recourse against oblivious adversaries. For both problems, the main challenge is to determine when and how to migrate jobs to maintain competitive solutions. Our central idea is that for each job, we make these decisions based only on the active set of jobs that are "earlier" than this job in some ordering ≺ of the jobs.

We consider the recourse version of the classical online load balancing problem on unrelated machines, where the algorithm is allowed to re-assign prior jobs. We give a (2+є)-competitive algorithm for the problem with Oє(logn) amortized recourse per job. This is the first O(1)-competitive algorithm for the problem with non-trivial recourse, and the competitive ratio nearly matches the long-standing best-known offline approximation guarantee. We also show an O(loglogn/logloglogn)-competitive algorithm for the problem with O(1) amortized recourse. The best-known bounds from prior work are O(loglogn)-competitive algorithms with O(1) amortized recourse due to Gupta et al., for the special case of the restricted assignment model.

As Approximate Nearest Neighbor Search (ANNS)-based dense retrieval becomes ubiquitous for search and recommendation scenarios, efficiently answering filtered ANNS queries has become a critical requirement. Filtered ANNS queries ask for the nearest neighbors of a query’s embedding from the points in the index that match the query’s labels such as date, price range, language. There has been little prior work on algorithms that use label metadata associated with vector data to build efficient indices for filtered ANNS queries. Consequently, current indices have high search latency or low recall which is not practical in interactive web-scenarios. We present two algorithms with native support for faster and more accurate filtered ANNS queries: one with streaming support, and another based on batch construction. Central to our algorithms is the construction of a graph-structured index which forms connections not only based on the geometry of the vector data, but also the associated label set. On real-world data with natural labels, both algorithms are an order of magnitude or more efficient for filtered queries than the current state of the art algorithms. The generated indices also be queried from an SSD and support thousands of queries per second at over recall@10.

The vector-balancing problem is a fundamental problem in discrepancy theory: given T vectors in [–1, 1]n, find a signing σ(a) ∊ {±1} of each vector a to minimize the discrepancy ‖ Σa σ(a) · a‖∞. This problem has been extensively studied in the static/offline setting. In this paper we initiate its study in the fully-dynamic setting with recourse: the algorithm sees a stream of T insertions and deletions of vectors, and at each time must maintain a low-discrepancy signing, while also minimizing the amortized recourse (the number of times any vector changes its sign) per update. For general vectors, we show algorithms which almost match Spencer's offline discrepancy bound, with O(n polylog T) amortized recourse per update. The crucial idea behind our algorithm is to compute a basic feasible solution to the linear relaxation in a distributed and recursive manner, which helps find a low-discrepancy signing. We bound the recourse using the distributed computation of the basic solution, and argue that only a small part of the instance needs to be re-computed at each update. Since vector balancing has also been greatly studied for sparse vectors, we then give algorithms for low-discrepancy edge orientation, where we dynamically maintain signings for 2-sparse vectors in an n-dimensional space. Alternatively, this can be seen as orienting a dynamic set of edges of an n-vertex graph to minimize the discrepancy, i.e., the absolute difference between in- and out-degrees at any vertex. We present a deterministic algorithm with O(polylog n) discrepancy and O(polylog n) amortized recourse. The core ideas are to dynamically maintain an expander-decomposition with low recourse (using a very simple approach), and then to show that, as the expanders change over time, a natural local-search algorithm converges quickly (i.e., with low recourse) to a low-discrepancy solution. We also give strong lower bounds (with some matching upper bounds) for local-search discrepancy minimization algorithms for vector balancing and edge orientation.

In the classical Online Metric Matching problem, we are given a metric space with $k$ servers. A collection of clients arrive in an online fashion, and upon arrival, a client should irrevocably be matched to an as-yet-unmatched server. The goal is to find an online matching which minimizes the total cost, i.e., the sum of distances between each client and the server it is matched to. We know deterministic algorithms~\cite{KP93,khuller1994line} that achieve a competitive ratio of $2k-1$, and this bound is tight for deterministic algorithms. The problem has also long been considered in specialized metrics such as the line metric or metrics of bounded doubling dimension, with the current best result on a line metric being a deterministic $O(\log k)$ competitive algorithm~\cite{raghvendra2018optimal}. Obtaining (or refuting) $O(\log k)$-competitive algorithms in general metrics and constant-competitive algorithms on the line metric have been long-standing open questions in this area. In this paper, we investigate the robustness of these lower bounds by considering the Online Metric Matching with Recourse problem where we are allowed to change a small number of previous assignments upon arrival of a new client. Indeed, we show that a small logarithmic amount of recourse can significantly improve the quality of matchings we can maintain. For general metrics, we show a simple \emph{deterministic} $O(\log k)$-competitive algorithm with $O(\log k)$-amortized recourse, an exponential improvement over the $2k-1$ lower bound when no recourse is allowed. We next consider the line metric, and present a deterministic algorithm which is $3$-competitive and has $O(\log k)$-recourse, again a substantial improvement over the best known $O(\log k)$-competitive algorithm when no recourse is allowed.

We consider the online carpooling problem: given $n$ vertices, a sequence of edges arrive over time. When an edge $e_t = (u_t, v_t)$ arrives at time step $t$, the algorithm must orient the edge either as $v_t \rightarrow u_t$ or $u_t \rightarrow v_t$, with the objective of minimizing the maximum discrepancy of any vertex, i.e., the absolute difference between its in-degree and out-degree. Edges correspond to pairs of persons wanting to ride together, and orienting denotes designating the driver. The discrepancy objective then corresponds to every person driving close to their fair share of rides they participate in. In this paper, we design efficient algorithms which can maintain polylog$(n,T)$ maximum discrepancy (w.h.p) over any sequence of $T$ arrivals, when the arriving edges are sampled independently and uniformly from any given graph $G$. This provides the first polylogarithmic bounds for the online (stochastic) carpooling problem. Prior to this work, the best known bounds were $O(\sqrt{n \log n})$-discrepancy for any adversarial sequence of arrivals, or $O(\log\!\log n)$-discrepancy bounds for the stochastic arrivals when $G$ is the complete graph. The technical crux of our paper is in showing that the simple greedy algorithm, which has provably good discrepancy bounds when the arriving edges are drawn uniformly at random from the complete graph, also has polylog discrepancy when $G$ is an expander graph. We then combine this with known expander-decomposition results to design our overall algorithm.

We consider virtual circuit routing protocols with an objective of minimizing energy in a network of components that are speed scalable, and that may be shut down when idle. We assume the standard model for component power: the power consumed by a component with load (speed) $s$ is $\sigma+ s^\alpha$, where $\sigma$ is the static power and the exponent $\alpha>1$. We obtain a very simple $O(\log^\alpha k)$-approximation algorithm for multicommodity routing, where $k$ is the number of demand pairs. This improves upon previous results by several logarithmic factors. The key step in our algorithm is a random sampling technique that we call hallucination, which is reminiscent of the sample-augment framework for buy-at-bulk problems, and sampling in cut-sparsification algorithms. We also consider the online setting of the problem, where demand pairs arrive over time. We show that our offline algorithm naturally extends to the online setting, and obtain a randomized competitive ratio of $\tilde{O}( \log^{3\alpha + 1} k)$, which is the first nontrivial bound. The analysis of this algorithm involves the study of priority multicommodity flows, where edges and demand-pairs have priorities and each demand-pair must route its flow only on edges of lower priority. We establish a polylogarithmic flow-cut gap for these priority flows, which we believe is of independent interest. Finally, we show how our technique can be used to achieve a randomized $( O(\log m), O(\log^2 m))$ bicriteria competitive algorithm for the uniform capacitated network design problem, where $m$ is the number of edges. Here, every edge has a cost $c_e$ and uniform capacity $q$, and the goal is to choose the minimum cost subgraph that can support the given multicommodity demand. This is the first online algorithm for this problem. In fact, our approach also improves prior results in the offline setting by several logarithmic factors.

In this article, we introduce and study the Non-Uniform k -Center (NUkC) problem. Given a finite metric space ( X , d ) and a collection of balls of radii { r 1 ≥ … ≥ r k }, the NUkC problem is to find a placement of their centers in the metric space and find the minimum dilation α, such that the union of balls of radius α ⋅ r i around the i th center covers all the points in X . This problem naturally arises as a min-max vehicle routing problem with fleets of different speeds. The NUkC problem generalizes the classic k -center problem, wherein all the k radii are the same (which can be assumed to be 1 after scaling). It also generalizes the k -center with outliers (kCwO for short) problem, in which there are k balls of radius 1 and ℓ (number of outliers) balls of radius 0. Before this work, there was a 2-approximation and 3-approximation algorithm known for these problems, respectively; the former is best possible unless P=NP. We first observe that no O (1)-approximation to the optimal dilation is possible unless P=NP, implying that the NUkC problem is harder than the above two problems. Our main algorithmic result is an ( O (1), O (1))- bi-criteria approximation result: We give an O (1)-approximation to the optimal dilation; however, we may open Θ(1) centers of each radii. Our techniques also allow us to prove a simple (uni-criterion), optimal 2-approximation to the kCwO problem improving upon the long-standing 3-factor approximation for this problem. Our main technical contribution is a connection between the NUkC problem and the so-called firefighter problems on trees that have been studied recently in the TCS community. We show NUkC is at least as hard as the firefighter problem. While we do nt know whether the converse is true, we are able to adapt ideas from recent works [1, 3] in non-trivial ways to obtain our constant factor bi-criteria approximation.

In this paper, we introduce and study the Robust-Correlation-Clustering problem: given a graph G = (V,E) where every edge is either labeled + or - (denoting similar or dissimilar pairs of vertices), and a parameter m, the goal is to delete a set D of m vertices, and partition the remaining vertices V \ D into clusters to minimize the cost of the clustering, which is the sum of the number of + edges with end-points in different clusters and the number of - edges with end-points in the same cluster. This generalizes the classical Correlation-Clustering problem which is the special case when m = 0. Correlation clustering is useful when we have (only) qualitative information about the similarity or dissimilarity of pairs of points, and Robust-Correlation-Clustering equips this model with the capability to handle noise in datasets. In this work, we present a constant-factor bi-criteria algorithm for Robust-Correlation-Clustering on complete graphs (where our solution is O(1)-approximate w.r.t the cost while however discarding O(1) m points as outliers), and also complement this by showing that no finite approximation is possible if we do not violate the outlier budget. Our algorithm is very simple in that it first does a simple LP-based pre-processing to delete O(m) vertices, and subsequently runs a particular Correlation-Clustering algorithm ACNAlg [Ailon et al., 2005] on the residual instance. We then consider general graphs, and show (O(log n), O(log^2 n)) bi-criteria algorithms while also showing a hardness of alpha_MC on both the cost and the outlier violation, where alpha_MC is the lower bound for the Minimum-Multicut problem.

Motivated by applications in cloud computing, we study the classical online caching problem for a cache of variable size, where the algorithm pays a maintenance cost that monotonically increases with cache size. This captures not only the classical setting of a fixed cache size, which corresponds to a maintenance cost of 0 for a cache of size at most k and ∞ otherwise, but also other natural settings in the context of cloud computing such as a concave rental cost on cache size. We call this the elastic caching problem. Our results are: (a) a randomized algorithm with a competitive ratio of O(log n) for maintenance cost that is an arbitrary function of cache size, (b) a deterministic algorithm with a competitive ratio of 2 for concave, or more generally submodular maintenance costs, (c) a deterministic n-competitive algorithm when the cost function is any monotone non-negative set function, and (d) a randomized constant-factor approximation algorithm for the offline version of the problem. Our algorithms are based on a configuration LP formulation of the problem, for which our main technical contribution is to maintain online a feasible fractional solution that can be converted to an integer solution using existing rounding techniques.

In this paper, we present a new iterative rounding framework for many clustering problems. Using this, we obtain an (α1 + є ≤ 7.081 + є)-approximation algorithm for k-median with outliers, greatly improving upon the large implicit constant approximation ratio of Chen. For k-means with outliers, we give an (α2+є ≤ 53.002 + є)-approximation, which is the first O(1)-approximation for this problem. The iterative algorithm framework is very versatile; we show how it can be used to give α1- and (α1 + є)-approximation algorithms for matroid and knapsack median problems respectively, improving upon the previous best approximations ratios of 8 due to Swamy and 17.46 due to Byrka et al. The natural LP relaxation for the k-median/k-means with outliers problem has an unbounded integrality gap. In spite of this negative result, our iterative rounding framework shows that we can round an LP solution to an almost-integral solution of small cost, in which we have at most two fractionally open facilities. Thus, the LP integrality gap arises due to the gap between almost-integral and fully-integral solutions. Then, using a pre-processing procedure, we show how to convert an almost-integral solution to a fully-integral solution losing only a constant-factor in the approximation ratio. By further using a sparsification technique, the additive factor loss incurred by the conversion can be reduced to any є > 0.

We present the first online algorithms for the nonuniform, multicommodity buy-at-bulk (MC-BB) network design problem. Our competitive ratios qualitatively match the best known approximation factors for the corresponding offline problems. In particular, we show (a) a polynomial time online algorithm with a polylogarithmic competitive ratio for the MC-BB problem in undirected edge-weighted graphs, (b) a quasi-polynomial time online algorithm with a polylogarithmic competitive ratio for the MC-BB problem in undirected node-weighted graphs, (c) for any fixed $\epsilon > 0$, a polynomial time online algorithm with a competitive ratio of $\tilde{O}\big(k^{\frac{1}{2}+\epsilon})$ (where $k$ is the number of demands, and the tilde hides polylog factors) for MC-BB in directed graphs, and (d) algorithms with matching competitive ratios for the prize-collecting variant of all the preceding problems. Prior to our work, a logarithmic competitive ratio was known for undirected, edge-weighted graphs only for the special case of uniform costs [B. Awerbuch and Y. Azar, FOCS, 1997, pp. 542--547], and a polylogarithmic-competitive algorithm was known for the edge-weighted single-sink problem [A. Meyerson, Procedings of SPAA, 2004, pp. 275--280]. We believe no online algorithm was known in the node-weighted and directed settings, even for uniform costs. Our main technical contribution is an online reduction theorem of MC-BB problems to their single-sink counterparts. We use the concept of junction-tree solutions from [C. Chekuri, M. T. Hajiaghayi, G. Kortsarz, and M. R. Salavatipour, Proceedings of FOCS, 2006, pp. 677--686], which play an important role in solving the offline versions of the problem via a greedy subroutine---an inherently offline procedure. We use just the existence of good junction-trees for our reduction.

In this paper, we study the problem of learning a mixture of Gaussians with streaming data: given a stream of $N$ points in $d$ dimensions generated by an unknown mixture of $k$ spherical Gaussians, the goal is to estimate the model parameters using a single pass over the data stream. We analyze a streaming version of the popular Lloyd's heuristic and show that the algorithm estimates all the unknown centers of the component Gaussians accurately if they are sufficiently separated. Assuming each pair of centers are $C\sigma$ distant with $C=\Omega((k\log k)^{1/4}\sigma)$ and where $\sigma^2$ is the maximum variance of any Gaussian component, we show that asymptotically the algorithm estimates the centers optimally (up to certain constants); our center separation requirement matches the best known result for spherical Gaussians \citep{vempalawang}. For finite samples, we show that a bias term based on the initial estimate decreases at $O(1/{\rm poly}(N))$ rate while variance decreases at nearly optimal rate of $\sigma^2 d/N$. Our analysis requires seeding the algorithm with a good initial estimate of the true cluster centers for which we provide an online PCA based clustering algorithm. Indeed, the asymptotic per-step time complexity of our algorithm is the optimal $d\cdot k$ while space complexity of our algorithm is $O(dk\log k)$. In addition to the bias and variance terms which tend to $0$, the hard-thresholding based updates of streaming Lloyd's algorithm is agnostic to the data distribution and hence incurs an \emph{approximation error} that cannot be avoided. However, by using a streaming version of the classical \emph{(soft-thresholding-based)} EM method that exploits the Gaussian distribution explicitly, we show that for a mixture of two Gaussians the true means can be estimated consistently, with estimation error decreasing at nearly optimal rate, and tending to $0$ for $N\rightarrow \infty$.

In this paper, we give new results for the set cover problem in the fully dynamic model. In this model, the set of "active" elements to be covered changes over time. The goal is to maintain a near-optimal solution for the currently active elements, while making few changes in each timestep. This model is popular in both dynamic and online algorithms: in the former, the goal is to minimize the update time of the solution, while in the latter, the recourse (number of changes) is bounded. We present generic techniques for the dynamic set cover problem inspired by the classic greedy and primal-dual offline algorithms for set cover. The former leads to a competitive ratio of O(lognt), where nt is the number of currently active elements at timestep t, while the latter yields competitive ratios dependent on ft, the maximum number of sets that a currently active element belongs to. We demonstrate that these techniques are useful for obtaining tight results in both settings: update time bounds and limited recourse, exhibiting algorithmic techniques common to these two parallel threads of research.

In this paper, we introduce and study the Non-Uniform k-Center problem (NUkC). Given a finite metric space $(X,d)$ and a collection of balls of radii $\{r_1\geq \cdots \ge r_k\}$, the NUkC problem is to find a placement of their centers on the metric space and find the minimum dilation $α$, such that the union of balls of radius $α\cdot r_i$ around the $i$th center covers all the points in $X$. This problem naturally arises as a min-max vehicle routing problem with fleets of different speeds. The NUkC problem generalizes the classic $k$-center problem when all the $k$ radii are the same (which can be assumed to be $1$ after scaling). It also generalizes the $k$-center with outliers (kCwO) problem when there are $k$ balls of radius $1$ and $\ell$ balls of radius $0$. There are $2$-approximation and $3$-approximation algorithms known for these problems respectively; the former is best possible unless P=NP and the latter remains unimproved for 15 years. We first observe that no $O(1)$-approximation is to the optimal dilation is possible unless P=NP, implying that the NUkC problem is more non-trivial than the above two problems. Our main algorithmic result is an $(O(1),O(1))$-bi-criteria approximation result: we give an $O(1)$-approximation to the optimal dilation, however, we may open $Θ(1)$ centers of each radii. Our techniques also allow us to prove a simple (uni-criteria), optimal $2$-approximation to the kCwO problem improving upon the long-standing $3$-factor. Our main technical contribution is a connection between the NUkC problem and the so-called firefighter problems on trees which have been studied recently in the TCS community.

We introduce and study a new notion of graph partitioning, intimately connected to spectral clustering and k-means clustering. Formally, given a graph G on n vertices, we ask to find a graph H that is the union of k cliques on n vertices, such that LG > λ LH where λ is maximized. Here LG and LH are the (normalized) Laplacians of the graphs G and H respectively. Informally, our graph partitioning objective asks for the optimal spectral simplification of a given graph as a disjoint union of k cliques.

In this article, we present improved inapproximability results for the k -level uncapacitated facility location problem. In particular, we show that there is no polynomial time approximation algorithm with performance guarantee better than 1.539 unless P = NP for the case when k = 2. For the case of general k (tending to infinity), we obtain a better hardness factor of 1.61. Interestingly, our results show that the two-level problem is computationally harder than the well-known uncapacitated facility location problem ( k = 1) since the best-known approximation guarantee for the latter problem is 1.488 due to Li [2013], and our inapproximability is a factor of 1.539 for the two-level problem. The only inapproximability result known before for this class of metric facility location problems is the bound of 1.463 due to Guha and Khuller [1999], which holds even for the case of k = 1.

We consider a natural online optimization problem set on the real line. The state of the online algorithm at each integer time is a location on the real line. At each integer time, a convex function arrives online. In response, the online algorithm picks a new location. The cost paid by the online algorithm for this response is the distance moved plus the value of the function at the final destination. The objective is then to minimize the aggregate cost over all time. The motivating application is rightsizing power-proportional data centers. We give a 2-competitive algorithm for this problem. We also give a 3-competitive memoryless algorithm, and show that this is the best competitive ratio achievable by a deterministic memoryless algorithm. Finally we show that this online problem is strictly harder than the standard ski rental problem.

The Euclidean $k$-means problem is a classical problem that has been extensively studied in the theoretical computer science, machine learning and the computational geometry communities. In this problem, we are given a set of $n$ points in Euclidean space $R^d$, and the goal is to choose $k$ centers in $R^d$ so that the sum of squared distances of each point to its nearest center is minimized. The best approximation algorithms for this problem include a polynomial time constant factor approximation for general $k$ and a $(1+ε)$-approximation which runs in time $poly(n) 2^{O(k/ε)}$. At the other extreme, the only known computational complexity result for this problem is NP-hardness [ADHP'09]. The main difficulty in obtaining hardness results stems from the Euclidean nature of the problem, and the fact that any point in $R^d$ can be a potential center. This gap in understanding left open the intriguing possibility that the problem might admit a PTAS for all $k,d$. In this paper we provide the first hardness of approximation for the Euclidean $k$-means problem. Concretely, we show that there exists a constant $ε> 0$ such that it is NP-hard to approximate the $k$-means objective to within a factor of $(1+ε)$. We show this via an efficient reduction from the vertex cover problem on triangle-free graphs: given a triangle-free graph, the goal is to choose the fewest number of vertices which are incident on all the edges. Additionally, we give a proof that the current best hardness results for vertex cover can be carried over to triangle-free graphs. To show this we transform $G$, a known hard vertex cover instance, by taking a graph product with a suitably chosen graph $H$, and showing that the size of the (normalized) maximum independent set is almost exactly preserved in the product graph using a spectral analysis, which might be of independent interest.

We present the first non-trivial online algorithms for the non-uniform, multicommodity buy-at-bulk (MC-BB) network design problem. Our competitive ratios qualitatively match the best known approximation factors for the corresponding offline problems. In particular, we show:1. A polynomial time online algorithm with a poly-logarithmic competitive ratio for the MC-BB problem in undirected edge-weighted graphs.2. A quasi-polynomial time online algorithm with a poly-logarithmic competitive ratio for the MC-BB problem in undirected node-weighted graphs.3. For any fixed ε > 0, a polynomial time online algorithm with a competitive ratio of O̅(k{1/2+ε}polylog(n)) (where k is the number of demands) for MC-BB in directed graphs.4. Algorithms with matching competitive ratios for the prize-collecting variants of all the above problems. Prior to our work, a logarithmic competitive ratio was known for undirected, edge-weighted graphs only for the special case of uniform costs (Awerbuch and Azar, FOCS 1997), and a polylogarithmic competitive ratio was known for the edge-weighted single-sink problem (Meyerson, SPAA 2004). To the best of our knowledge, no previous online algorithm was known, even for uniform costs, in the node-weighted and directed settings. Our main engine for the results above is an online reduction theorem of MC-BB problems to their single-sink (SS-BB) counterparts. We use the concept of junction-tree solutions (Chekuri et al., FOCS 2006) that play an important role in solving the offline versions of the problem via a greedy subroutine -- an inherently offline procedure. Our main technical contribution is in designing an online algorithm using only the existence of good junction-trees to reduce an MC-BB instance to multiple SS-BB sub-instances. Along the way, we also give the first non-trivial online node-weighted/directed single-sink buy-at-bulk algorithms. In addition to the new results, our generic reduction also yields new proofs of recent results for the online node-weighted Steiner forest and online group Steiner forest problems.

We study exact recovery conditions for convex relaxations of point cloud clustering problems, focusing on two of the most common optimization problems for unsupervised clustering: k-means and k-median clustering. Motivations for focusing on convex relaxations are: (a) they come with a certificate of optimality, and (b) they are generic tools which are relatively parameter-free, not tailored to specific assumptions over the input. More precisely, we consider the distributional setting where there are k clusters in Rm and data from each cluster consists of n points sampled from a symmetric distribution within a ball of unit radius. We ask: what is the minimal separation distance between cluster centers needed for convex relaxations to exactly recover these k clusters as the optimal integral solution? For the k-median linear programming relaxation we show a tight bound: exact recovery is obtained given arbitrarily small pairwise separation ε > O between the balls. In other words, the pairwise center separation is δ > 2+ε. Under the same distributional model, the k-means LP relaxation fails to recover such clusters at separation as large as δ = 4. Yet, if we enforce PSD constraints on the k-means LP, we get exact cluster recovery at separation as low as δ > min{2 + √2k/m}, 2+√2 + 2/m} + ε. In contrast, common heuristics such as Lloyd's algorithm (a.k.a. the k means algorithm) can fail to recover clusters in this setting; even with arbitrarily large cluster separation, k-means++ with overseeding by any constant factor fails with high probability at exact cluster recovery. To complement the theoretical analysis, we provide an experimental study of the recovery guarantees for these various methods, and discuss several open problems which these experiments suggest.

We consider virtual circuit routing protocols, with an objective of minimizing energy, in a network of components that are speed scalable, and that may be shutdown when idle. We assume that the speed s of a link is proportional to its load, and assume the standard model for component power, namely that the power is some constant static power σ plus sα, where typically α ∊ [1.1,3]. We give a polynomial-time offline algorithm for multicommodity routing, that has approximation ratio O(loga k), where k is the number of demand pairs. This is obtained as a combination of three natural combinatorial algorithms. The key step of the algorithm design is a random sampling technique that we call hallucination, which is reminiscent of the Sample-Augment framework for solving Buy-at-Bulk type problems, and sampling in cut-sparsification algorithms. The analysis of the approximation ratio is then a direct consequence of the flow-cut gap for multicommodity flow. The algorithm extends rather naturally to an online algorithm, which we show has competitive ratio Õ(log3a+1 k). The analysis of the online algorithm introduces a natural “priority” multicommodity flow problem, and bounds the priority multicommodity flow-cut gap-this might also be of independent interest. We also explain how our hallucination technique can be used to achieve an (O(log km), O(logkm)) bicriteria approximation result for the problem of buying a minimum cost collection of unit-capacitated edges to support a concurrent multicommodity flow, where m is the number of links in the network.

We study the broadcast scheduling problem with the objective of minimizing the average response time. There is a single server that can hold n pages of unit size, and multiple requests for these pages arrive over time. At each time slot the server can broadcast one page which satisfies all the outstanding requests for this page at that time. The goal is to find a schedule to minimize the average response time of the requests, i.e. the duration since a request arrives until it is satisfied. We give an Õ(log1,5 n) approximation algorithm for the problem improving upon the previous Õ(log 2 n) approximation. We also show an Ω(log1/2–∊n) hardness result, and an integrality gap of Ω(log n) for the natural LP relaxation for the problem. Prior to our work, only NP-Hardness and a (tiny) constant integrality gap was known. These results are based on establishing a close connection to the discrepancy minimization problem for permutation set-systems. Specifically, our improved approximation is based on using recent algorithmic ideas developed for discrepancy minimization. Our integrality gap is obtained from the Ω(log n)-lower bound on the discrepancy of 3-permutations, while our hardness result is based on establishing the first hardness result for the discrepancy of ℓ-permutations.

We consider circuit routing with an objective of minimizing energy, in a network of routers that are speed scalable and that may be shutdown when idle. It is known that this energy minimization problem can be reduced to a capacitated flow network design problem, where vertices have a common capacity but arbitrary costs, and the goal is to choose a minimum cost collection of vertices whose induced subgraph will support the specified flow requirements. For the multicast (single-sink) capacitated design problem we give a polynomial-time algorithm that is O(log3 n)- approximate with O(log4 n) congestion. This translates back to a O(log4α+3 n)-approximation for the multicast energy-minimization routing problem, where α is the polynomial exponent in the dynamic power used by a router. For the unicast (multicommodity) capacitated design problem we give a polynomial-time algorithm that is O(log5 n)-approximate with O(log12 n) congestion, which translates back to a O(log12α+5 n)-approximation for the unicast energy-minimization routing problem.

In the classical broadcast scheduling problem , there are n pages stored at a server, and requests for these pages arrive over time. Whenever a page is broadcast, it satisfies all outstanding requests for that page. The objective is to minimize average flow time of the requests. For any ϵ > 0, we give a (1+ϵ)-speed O (1/ϵ 3 )-competitive online algorithm for broadcast scheduling. This improves over the recent breakthrough result of Im and Moseley [2010], where they obtained a (1+ϵ)-speed O (1/ϵ 11 )-competitive algorithm. Our algorithm and analysis are considerably simpler than Im and Moseley [2010]. More importantly, our techniques also extend to the general setting of nonuniform page sizes and dependent requests . This is the first scalable algorithm for broadcast scheduling with varying size pages and resolves the main open question from Im and Moseley [2010].

We investigate approximation algorithms for the classical minimum makespan scheduling problem, focusing on instances where the rank of the matrix describing the processing times of the jobs is bounded. A bounded rank matrix arises naturally when the processing time of a job on machine depends upon a bounded set of resources. A bounded rank matrix also shows up when jobs have varying degrees of parallelizability and the machines have multiple cores. We are interested in studying the tractability of the problem as a function of the (positive) rank of the processing-time matrix. At one extreme is the case of unit rank, also known as related machines, which admits a PTAS [7], and at the other extreme is the full rank case (unrelated machines), which is NP-hard to approximate within a factor better than 3/2 [8]. Our main technical contribution is in showing that the approximability of the problem is not smooth with the rank of the matrix. From the inapproximability side, we show that the problem becomes APX-hard, even for rank four matrices. For rank seven matrices, we prove that it is hard to approximate to a factor 3/2, matching the inapproximability result for general unrelated machines. From the algorithmic side, we obtain a quasi-polynomial approximation scheme (i.e., a (1 + ε) approximation in time npoly(1/ε, log n)) for the rank two case. This implies that the problem is not APX-hard in this case, unless NP has quasi-polynomial algorithms. Our algorithm is a subtle dynamic program which runs in polynomial time in some interesting special cases. The classification of the three dimensional problem remains open.

We consider preemptive online scheduling algorithms to minimize the total weighted/unweighted flow time plus energy for speed-scalable heterogeneous multiprocessors. We show that the well-known priority scheduling algorithms Highest Density First, Weighted Shortest Elapsed Time First, and Weighted Late Arrival Processor Sharing, are not O(1)-speed O(1)-competitive for the objective of weighted flow even in the special case of fixed variable speed processors (aka the related machines setting). This illustrates that scheduling heterogeneous multiprocessors is a different, and algorithmically more challenging problem, than scheduling homogeneous multiprocessors. We then show that a variation of the non-clairvoyant algorithm Late Arrival Processor Sharing coupled with a non-obvious speed scaling algorithm is scalable for the objective of unweighted flow plus energy on speed-scalable multiprocessors. This is the first provably scalable non-clairvoyant algorithm on heterogeneous multiprocessors, even in the related machines setting, for the objective of total (unweighted) flow time.

In the Stochastic Orienteering problem, we are given a metric, where each node also has a job located there with some deterministic reward and a random size. (Think of the jobs as being chores one needs to run, and the sizes as the amount of time it takes to do the chore.) The goal is to adaptively decide which nodes to visit to maximize total expected reward, subject to the constraint that the total distance traveled plus the total size of jobs processed is at most a given budget of B. (I.e., we get reward for all those chores we finish by the end of the day). The (random) size of a job is not known until it is completely processed. Hence the problem combines aspects of both the stochastic knapsack problem with uncertain item sizes and the deterministic orienteering problem of using a limited travel time to maximize gathered rewards located at nodes. In this paper, we present a constant-factor approximation algorithm for the best non-adaptive policy for the Stochastic Orienteering problem. We also show a small adaptivity gap—i.e., the existence of a non-adaptive policy whose reward is at least an Ω(1/ log log B) fraction of the optimal expected reward—and hence we also get an O(log log B)-approximation algorithm for the adaptive problem. Finally we address the case when the node rewards are also random and could be correlated with the waiting time, and give a non-adaptive policy which is an O(log n log B)-approximation to the best adaptive policy on n-node metrics with budget B.

In this paper, we present improved inapproximability results for the k-level uncapacitated facility location problem. In particular, we show that there is no polynomial time approximation algorithm with performance guarantee better than 1.539 unless NP is contained in DTIME(nO(log log n)) for the case when k = 2. For the case of general k (tendining to infinity) we obtain a better hardness factor of 1.61. Interestingly, our results show that the two-level problem is computationally harder than the well known uncapacitated facility location problem (k = 1) since the best known approximation guarantee for the latter problem is 1.488 due to Li [22], and our inapproximability is a factor of 1.539 for the two-level problem. The only inapproximability result known before for this class of metric facility location problems is the bound of 1.463 due to Guha and Khuller [17], which holds even for the case of k = 1.

We investigate the problem of designing differentially private mechanisms for a set of d linear queries over a database, while adding as little error as possible. Hardt and Talwar [HT10] related this problem to geometric properties of a convex body defined by the set of queries and gave a O(log3 d)-approximation to the minimum l22 error, assuming a conjecture from convex geometry called the Slicing or Hyperplane conjecture. In this work we give a mechanism that works unconditionally, and also gives an improved O(log2 d) approximation to the expected l22 error. We remove the dependence on the Slicing conjecture by using a result of Klartag [Kla06] that shows that any convex body is close to one for which the conjecture holds; our main contribution is in making this result constructive by using recent techniques of Dadush, Peikert and Vempala [DPV10]. The improvement in approximation ratio relies on a stronger lower bound we derive on the optimum. This new lower bound goes beyond the packing argument that has traditionally been used in Differential Privacy and allows us to add the packing lower bounds obtained from orthogonal subspaces. We are able to achieve this via a symmetrization argument which argues that there always exists a near optimal differentially private mechanism which adds noise that is independent of the input database! We believe this result should be of independent interest, and also discuss some interesting consequences.

Consider the edge-connectivity survivable network design problem (SNDP): given a graph $G = (V,E)$ with edge-costs, and edge-connectivity requirements $r_{ij} \in \mathbb{Z}_{\geq 0}$ for every pair of vertices $i, j \in V$, find an (approximately) minimum-cost network that provides the required connectivity. While this problem is known to admit good approximation algorithms in the offline case, no algorithms were known for this problem in the online setting. In this paper, we give a randomized $\tilde{O}(r_{\max} \log^3 n)$-competitive online algorithm for this edge-connectivity network design problem that runs in time $O(m^{r_{\max}})$, where $r_{\max} = \max_{ij} r_{ij}$. Our algorithms use the standard embeddings of graphs into random subtrees (i.e., into singly connected subgraphs) as an intermediate step to get algorithms for higher connectivity. As a consequence of using these random embeddings, our algorithms are competitive only against oblivious adversaries. Our results for the online problem give us approximation algorithms that admit strict cost-shares with the same strictness value. This, in turn, implies approximation algorithms for (a) the rent-or-buy version and (b) the (two-stage) stochastic version of the edge-connected network design problem with independent arrivals. If we are in the case when the underlying graph is complete and the edge-costs are metric (i.e., the triangle inequality is satisfied), we improve on our results to give an $O(\log n)$-competitive deterministic online algorithm for the rooted version of the problem, and constant-factor approximation algorithms for the rent-or-buy and stochastic variants of SNDP.

In the stochastic knapsack problem, we are given a knapsack of size B, and a set of items whose sizes and rewards are drawn from a known probability distribution. To know the actual size and reward we have to schedule the item-when it completes, we get to know these values. The goal is to schedule the items (possibly making adaptive decisions based on the sizes seen so far) to maximize the expected total reward of items which successfully pack into the knapsack. We know constant-factor approximations when (i) the rewards and sizes are independent, and (ii) we cannot prematurely cancel items after we schedule them. What if either or both assumptions are relaxed? Related stochastic packing problems are the multi-armed bandit (and budgeted learning) problems, here one is given several arms which evolve in a specified stochastic fashion with each pull, and the goal is to (adaptively) decide which arms to pull, in order to maximize the expected reward obtained after B pulls in total. Much recent work on this problem focuses on the case when the evolution of each arm follows a martingale, i.e., when the expected reward from one pull of an arm is the same as the reward at the current state. What if the rewards do not form a martingale? In this paper, we give O(1)-approximation algorithms for the stochastic knapsack problem with correlations and/or cancellations. Extending the ideas developed here, we give O(1)-approximations for MAB problems without the martingale assumption. Indeed, we can show that previously proposed linear programming relaxations for these problems have large integrality gaps. So we propose new time-indexed LP relaxations, using a decomposition and "gap-filling" approach, we convert these fractional solutions to distributions over strategies, and then use the LP values and the time ordering information from these strategies to devise randomized adaptive scheduling algorithms.

In the classical k-median problem, we are given a metric space and would like to open k centers so as to minimize the sum (over all the vertices) of the distance of each vertex to its nearest open center. In this paper, we consider the following generalization of the problem: instead of opening at most k centers, what if each center belongs to one of T different types, and we are allowed to open at most ki centers of type i (for each i = 1, 2, …, T). The case T = 1 is the classical k-median, and the case of T = 2 is the red-blue median problem for which Hajiaghayi et al. [ESA 2010] recently gave a constant-factor approximation algorithm. Even more generally, what if the set of open centers had to form an independent set from a matroid? In this paper, we give a constant factor approximation algorithm for such matroid median problems. Our algorithm is based on rounding a natural LP relaxation in two stages: in the first step, we sparsify the structure of the fractional solution while increasing the objective function value by only a constant factor. This enables us to write another LP in the second phase, for which the sparsified LP solution is feasible. We then show that this second phase LP is in fact integral; the integrality proof is based on a connection to matroid intersection. We also consider the penalty version (alternately, the so-called prize collecting version) of the matroid median problem and obtain a constant factor approximation algorithm for it. Finally, we look at the Knapsack Median problem (in which the facilities have costs and the set of open facilities need to fit into a Knapsack) and get a bicriteria approximation algorithm which violates the Knapsack bound by a small additive amount.

Traditional efforts for scaling network intrusion detection (NIDS) and intrusion prevention systems (NIPS) have largely focused on a single-vantage-point view. In this paper, we explore an alternative design that exploits spatial, network-wide opportunities for distributing NIDS and NIPS functions. For the NIDS case, we design a linear programming formulation to assign detection responsibilities to nodes while ensuring that no node is overloaded. We describe a prototype NIDS implementation adapted from the Bro system to analyze traffic per these assignments, and demonstrate the advantages that this approach achieves. For NIPS, we show how to maximally leverage specialized hardware (e.g., TCAMs) to reduce the footprint of unwanted traffic on the network. Such hardware constraints make the optimization problem NP-hard, and we provide practical approximation algorithms based on randomized rounding.

Consider the following generalized min-sum set cover or multiple intents re-ranking problem proposed by Azar et al. (STOC 2009). We are given a universe of elements and a collection of subsets, with each set S having a covering requirement of K(S). The objective is to pick one element at a time such that the average covering time of the sets is minimized, where the covering time of a set S is the first time at which K(S) elements from it have been selected. There are two well-studied extreme cases of this problem: (i) when K(S) = 1 for all sets, we get the min-sum set cover problem, and (ii) when K(S) = |S| for all sets, we get the minimum-latency set cover problem. Constant factor approximations are known for both these problems. In their paper, Azar et al. considered the general problem and gave a logarithmic approximation algorithm for it. In this paper, we improve their result and give a simple randomized constant factor approximation algorithm for the generalized min-sum set cover problem.

The group Steiner problem is a classical network design problem where we are given a graph and a collection of groups of vertices, and want to build a min-cost subgraph that connects the root vertex to at least one vertex from each group. What if we wanted to build a subgraph that two-edge-connects the root to each group—that is, for every group g ⊆ V, the subgraph should contain two edge-disjoint paths from the root to some vertex in g? What if we wanted the two edge-disjoint paths to end up at distinct vertices in the group, so that the loss of a single member of the group would not destroy connectivity? In this paper, we investigate tree-embedding techniques that can be used to solve these and other 2-edge-connected network design problems. We illustrate the potential of these techniques by giving poly-logarithmic approximation algorithms for two-edge-connected versions of the group Steiner, connected facility location, buy-at-bulk, and the k-MST problems.

We give a (2+ε)-speed O(1)-competitive algorithm for scheduling jobs with arbitrary speed-up curves for the l2 norm of flow. We give a similar result for the broadcast setting with varying page sizes.

Consider the edge-connectivity survivable network design problem: given a graph G = (V,E) with edge-costs, and edge-connectivity requirements rij for every pair of vertices i,j, find an (approximately) minimum-cost network that provides the required connectivity. While this problem is known to admit good approximation algorithms in the offline case, no algorithms were known for this problem in the online setting.