Moses Charikar

FOCS Conference 2025 Conference Paper

An Improved Greedy Approximation for (Metric) k-Means

• Moses Charikar
• Vincent Cohen-Addad
• Ruiquan Gao 0001
• Fabrizio Grandoni 0001
• Euiwoong Lee
• Ernest van Wijland

Clustering is a basic task in data analysis and machine learning, and the optimization of clustering objectives are well-studied optimization problems; amongst these, the k Means objective is arguably the most well known. Given a collection of points in a metric space, the goal is to partition them into k clusters, each with an associated center, so as to minimize the sum of squared distances of points to their cluster centers. In this paper, we present a polynomial-time $3+2 \sqrt{2}+\varepsilon{\lt}5. 83$-approximation algorithm for k-Means in general metrics. This substantially improves on the current-best $(9+\varepsilon)$-approximation in [Ahmadian, Norouzi-Fard, Svensson, Ward - FOCS’17, SICOMP’20], and even slightly improves on the 5. 92-approximation in [Cohen-Addad, Esfandiari, Mirrokni, Narayanan - STOC’22] for the Euclidean special case. A natural approach for k-Means is to leverage Lagrangian Multiplier Preserving (LMP) approximations for the facility location problem. The previous best results for k-Means build upon an adaptation of an LMP 3-approximation for facility location with metric connection costs in [Jain, Vazirani J. ACM’01] based on a primal-dual method, rather than on the improved LMP greedy 2-approximation for the same problem in [Jain, Mahdian, Markakis, Saberi, Vazirani - J. ACM’03]. The barrier to using the improved LMP algorithm was that no adaptation of this algorithm and its analysis to the case of squared metric connection costs was known (since squared distances violate triangle inequality). Our main contribution is overcoming this barrier by providing such an adaptation. This new LMP approximation algorithm is then combined with the framework recently introduced in [Cohen-Addad, Grandoni, Lee, Schwiegelshohn, Svensson - STOC’25] for the related (metric) k Median problem.

ICML Conference 2025 Conference Paper

Correlation Clustering Beyond the Pivot Algorithm

• Soheil Behnezhad
• Moses Charikar
• Vincent Cohen-Addad
• Alma Ghafari
• Weiyun Ma

We study the classic correlation clustering problem. Given $n$ objects and a complete labeling of the object-pairs as either “similar” or “dissimilar”, the goal is to partition the objects into arbitrarily many clusters while minimizing disagreements with the labels. A classic Pivot algorithm for this problem, due to [Ailon et al STOC’05], obtains a 3-approximation for this problem. Over the years, this algorithm has been successfully implemented in various settings. The downside of the Pivot algorithm is that the approximation analysis of 3 is tight for it. While better approximations have been achieved in some settings, these algorithms are often hard to implement in various settings. For example, [Behnezhad et al FOCS19] showed that the output of Pivot can be maintained in polylog time per update in a dynamic setting, a bound that was improved to constant by [Dalirrooyfard et al ICML’24]. But obtaining a better approximation remains open. In this paper, we present Modified Pivot, an algorithm that locally improves the output of Pivot. Our Modified Pivot algorithm can be implemented just as efficiently as Pivot in various settings. Our experiments show that the output of Modified Pivot on average makes less than 77% of the mistakes made by Pivot. More surprisingly, we prove theoretically that Modified Pivot has approximation ratio $3-\epsilon_0$ for some absolute constant $\epsilon_0 > 0$. This, e. g. , leads to a better than 3 approximation in the dynamic setting in polylog time, improving the 3-approximation obtained by [Behnezhad et al FOCS’19] and [Dalirrooyfard et al ICML’24].

SODA Conference 2025 Conference Paper

Embedding Probability Distributions into Low Dimensional ℓ 1: Tree Ising Models via Truncated Metrics

• Moses Charikar
• Spencer Compton
• Chirag Pabbaraju

STOC Conference 2025 Conference Paper

Six Candidates Suffice to Win a Voter Majority

• Moses Charikar
• Alexandra Lassota
• Prasanna Ramakrishnan
• Adrian Vetta
• Kangning Wang 0001

A cornerstone of social choice theory is Condorcet’s paradox which says that in an election where n voters rank m candidates it is possible that, no matter which candidate is declared the winner, a majority of voters would have preferred an alternative candidate. Instead, can we always choose a small committee of winning candidates that is preferred to any alternative candidate by a majority of voters? Elkind, Lang, and Saffidine raised this question and called such a committee a Condorcet winning set . They showed that winning sets of size 2 may not exist, but sets of size logarithmic in the number of candidates always do. In this work, we show that Condorcet winning sets of size 6 always exist, regardless of the number of candidates or the number of voters. More generally, we show that if α/1 − lnα ≥ 2/ k + 1, then there always exists a committee of size k such that less than an α fraction of the voters prefer an alternate candidate. These are the first nontrivial positive results that apply for all k ≥ 2. Our proof uses the probabilistic method and the minimax theorem, inspired by recent work on approximately stable committee selection . We construct a distribution over committees that performs sufficiently well (when compared against any candidate on any small subset of the voters) so that this distribution must contain a committee with the desired property in its support.

SODA Conference 2025 Conference Paper

The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction

• Moses Charikar
• Erik Waingarten

SODA Conference 2024 Conference Paper

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations

• Moses Charikar
• Michael Kapralov
• Erik Waingarten

In the kernel density estimation (KDE) problem one is given a kernel K(x, y) and a dataset P of points in a high dimensional Euclidean space, and must prepare a small space data structure that can quickly answer density queries: given a point q, output a (1 + ɛ )-approximation to. The classical approach to KDE (and the more general problem of matrix vector multiplication for kernel matrices) is the celebrated fast multipole method of Greengard and Rokhlin [1983]. The fast multipole method combines a basic space partitioning approach with a multidimensional Taylor expansion, which yields a ≈ log d ( n / ɛ ) query time (exponential in the dimension d ). A recent line of work initiated by Charikar and Siminelakis [2017] achieved polynomial dependence on d via a combination of random sampling and randomized space partitioning, with Backurs et al. [2018] giving an efficient data structure with query time ≈ polylog(1/µ)/ ɛ 2 for smooth kernels. Quadratic dependence on ɛ, inherent to the sampling (i. e. , Monte Carlo) methods above, is prohibitively expensive for small ɛ. This is a classical issue addressed by quasi-Monte Carlo methods in numerical analysis. The high level idea in quasi-Monte Carlo methods is to replace random sampling with a discrepancy based approach - an idea recently applied to coresets for KDE by Phillips and Tai [2020]. The work of Phillips and Tai gives a space efficient data structure with query complexity ≈ 1/( ɛ μ). This is polynomially better in 1/ ɛ, but exponentially worse in 1/μ. In this work we show how to get the best of both worlds: we give a data structure with ≈ polylog(1 /μ)/ ɛ query time for smooth kernel KDE. Our main insight is a new way to combine discrepancy theory with randomized space partitioning inspired by, but significantly more efficient than, that of the fast multipole methods. We hope that our techniques will find further applications to linear algebra for kernel matrices.

SODA Conference 2024 Conference Paper

Breaking the Metric Voting Distortion Barrier

• Moses Charikar
• Kangning Wang 0001
• Prasanna Ramakrishnan
• Hongxun Wu

SODA Conference 2024 Conference Paper

Improved Approximations for Ultrametric Violation Distance

• Moses Charikar
• Ruiquan Gao 0001

NeurIPS Conference 2024 Conference Paper

Quantifying the Gain in Weak-to-Strong Generalization

• Moses Charikar
• Chirag Pabbaraju
• Kirankumar Shiragur

Recent advances in large language models have shown capabilities that are extraordinary and near-superhuman. These models operate with such complexity that reliably evaluating and aligning them proves challenging for humans. This leads to the natural question: can guidance from weak models (like humans) adequately direct the capabilities of strong models? In a recent and somewhat surprising work, Burns et al. (2023) empirically demonstrated that when strong models (like GPT-4) are finetuned using labels generated by weak supervisors (like GPT-2), the strong models outperform their weaker counterparts---a phenomenon they term weak-to-strong generalization. In this work, we present a theoretical framework for understanding weak-to-strong generalization. Specifically, we show that the improvement in performance achieved by strong models over their weaker counterparts is quantified by the misfit error incurred by the strong model on labels generated by the weaker model. Our theory reveals several curious algorithmic insights. For instance, we can predict the amount by which the strong model will improve over the weak model, and also choose among different weak models to train the strong model, based on its misfit error. We validate our theoretical findings through various empirical assessments.

STOC Conference 2023 Conference Paper

A Characterization of List Learnability

• Moses Charikar
• Chirag Pabbaraju

A classical result in learning theory shows the equivalence of PAC learnability of binary hypothesis classes and the finiteness of VC dimension. Extending this to the multiclass setting was an open problem, which was settled in a recent breakthrough result characterizing multiclass PAC learnability via the DS dimension introduced earlier by Daniely and Shalev-Shwartz. In this work we consider list PAC learning where the goal is to output a list of k predictions. List learning algorithms have been developed in several settings before and indeed, list learning played an important role in the recent characterization of multiclass learnability. In this work we ask: when is it possible to k -list learn a hypothesis class? We completely characterize k -list learnability in terms of a generalization of DS dimension that we call the k -DS dimension. Generalizing the recent characterization of multiclass learnability, we show that a hypothesis class is k -list learnable if and only if the k -DS dimension is finite.

NeurIPS Conference 2023 Conference Paper

Simple, Scalable and Effective Clustering via One-Dimensional Projections

• Moses Charikar
• Monika Henzinger
• Lunjia Hu
• Maximilian Vötsch
• Erik Waingarten

Clustering is a fundamental problem in unsupervised machine learning with many applications in data analysis. Popular clustering algorithms such as Lloyd's algorithm and $k$-means++ can take $\Omega(ndk)$ time when clustering $n$ points in a $d$-dimensional space (represented by an $n\times d$ matrix $X$) into $k$ clusters. On massive datasets with moderate to large $k$, the multiplicative $k$ factor can become very expensive. We introduce a simple randomized clustering algorithm that provably runs in expected time $O(\mathsf{nnz}(X) + n\log n)$ for arbitrary $k$. Here $\mathsf{nnz}(X)$ is the total number of non-zero entries in the input dataset $X$, which is upper bounded by $nd$ and can be significantly smaller for sparse datasets. We prove that our algorithm achieves approximation ratio $\widetilde{O}(k^4)$ on any input dataset for the $k$-means objective, and our experiments show that the quality of the clusters found by our algorithm is usually much better than this worst-case bound. We use our algorithm for $k$-means clustering and for coreset construction; our experiments show that it gives a new tradeoff between running time and cluster quality compared to previous state-of-the-art methods for these tasks. Our theoretical analysis is based on novel results of independent interest. We show that the approximation ratio achieved after a random one-dimensional projection can be lifted to the original points and that $k$-means++ seeding can be implemented in expected time $O(n\log n)$ in one dimension.

SODA Conference 2023 Conference Paper

Single-Pass Streaming Algorithms for Correlation Clustering

• Soheil Behnezhad
• Moses Charikar
• Weiyun Ma
• Li-Yang Tan

We study correlation clustering in the streaming setting. This problem has been studied extensively and numerous algorithms have been developed, most requiring multiple passes over the stream. For the important case of single-pass algorithms, recent work of Assadi and Wang [8] obtains a c -approximation using Õ( n ) space where c > 10 5 is a constant and n is the number of vertices to be clustered. We present a single-pass algorithm that obtains a 5-approximation using O(n) space. The algorithm itself is extremely simple and has implications beyond the streaming setting (such as for dynamic and local computation algorithms). The approximation analysis, on the other hand, is delicate and in fact tight.

FOCS Conference 2022 Conference Paper

Almost 3-Approximate Correlation Clustering in Constant Rounds

• Soheil Behnezhad
• Moses Charikar
• Weiyun Ma
• Li-Yang Tan

We study parallel algorithms for correlation clustering. Each pair among n objects is labeled as either “similar” or “dissimilar”. The goal is to partition the objects into arbitrarily many clusters while minimizing the number of disagreements with the labels. Our main result is an algorithm that for any $\varepsilon>0$ obtains a (3 + $\varepsilon$)-approximation in $O(1/\varepsilon$) rounds (of models such as massively parallel computation, local, and semi-streaming). This is a culminating point for the rich literature on parallel correlation clustering. On the one hand, the approximation (almost) matches a natural barrier of 3 for combinatorial algorithms. On the other hand, the algorithm’s round-complexity is essentially constant. To achieve this result, we introduce a simple $O(1/\varepsilon$)-round parallel algorithm. Our main result is to provide an analysis of this algorithm, showing that it achieves a (3 + $\varepsilon$)-approximation. Our analysis draws on new connections to sublinear-time algorithms. Specifically, it builds on the work of Yoshida, Yamamoto, and Ito [1] on bounding the “query complexity” of greedy maximal independent set. To our knowledge, this is the first application of this method in analyzing the approximation ratio of any algorithm. Full version. Due to the page limit, this version of the paper does not include all the proofs. The full version of the paper is available at [2].

SODA Conference 2022 Conference Paper

Metric Distortion Bounds for Randomized Social Choice

• Moses Charikar
• Prasanna Ramakrishnan

Consider the following social choice problem. Suppose we have a set of n voters and m candidates that lie in a metric space. The goal is to design a mechanism to choose a candidate whose average distance to the voters is as small as possible. However, the mechanism does not get direct access to the metric space. Instead, it gets each voter's ordinal ranking of the candidates by distance. Given only this partial information, what is the smallest worst-case approximation ratio (known as the distortion ) that a mechanism can guarantee? A simple example shows that no deterministic mechanism can guarantee distortion better than 3, and no randomized mechanism can guarantee distortion better than 2. It has been conjectured that both of these lower bounds are optimal, and recently, Gkatzelis, Halpern, and Shah proved this conjecture for deterministic mechanisms. We disprove the conjecture for randomized mechanisms for m ≥ 3 by constructing elections for which no randomized mechanism can guarantee distortion better than 2. 0261 for m = 3, 2. 0496 for m = 4, up to 2. 1126 as m → ∞. We obtain our lower bounds by identifying a class of simple metrics that appear to capture much of the hardness of the problem, and we show that any randomized mechanism must have high distortion on one of these metrics. We provide a nearly matching upper bound for this restricted class of metrics as well. Finally, we conjecture that these bounds give the optimal distortion for every m, and provide a proof for m = 3, thereby resolving that case.

SODA Conference 2022 Conference Paper

Near-Optimal Explainable k-Means for All Dimensions

• Moses Charikar
• Lunjia Hu

Many clustering algorithms are guided by certain cost functions such as the widely-used k -means cost. These algorithms divide data points into clusters with often complicated boundaries, creating difficulties in explaining the clustering decision. In a recent work, Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020) introduced explainable clustering, where the cluster boundaries are axis-parallel hyperplanes and the clustering is obtained by applying a decision tree to the data. The central question here is: how much does the explainability constraint increase the value of the cost function? Given d -dimensional data points, we show an efficient algorithm that finds an explainable clustering whose k -means cost is at most k 1–2/ d poly( d log k ) times the minimum cost achievable by a clustering without the explainability constraint, assuming k, d ≥ 2. Taking the minimum of this bound and the k polylog( k ) bound in independent work by Makarychev-Shan (ICML 2021), Gamlath-Jia-Polak-Svensson (2021), or Esfandiari-Mirrokni-Narayanan (2021), we get an improved bound of k 1–2/ d polylog( k ), which we show is optimal for every choice of k, d ≥ 2 up to a poly-logarithmic factor in k. For d = 2 in particular, we show an O (log k log log k ) bound, improving near-exponentially over the previous best bound of O ( k log k ) by Laber and Murtinho (ICML 2021).

NeurIPS Conference 2022 Conference Paper

On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood

• Moses Charikar
• Zhihao Jiang
• Kirankumar Shiragur
• Aaron Sidford

We provide an efficient unified plug-in approach for estimating symmetric properties of distributions given $n$ independent samples. Our estimator is based on profile-maximum-likelihood (PML) and is sample optimal for estimating various symmetric properties when the estimation error $\epsilon \gg n^{-1/3}$. This result improves upon the previous best accuracy threshold of $\epsilon \gg n^{-1/4}$ achievable by polynomial time computable PML-based universal estimators \cite{ACSS20, ACSS20b}. Our estimator reaches a theoretical limit for universal symmetric property estimation as \cite{Han20} shows that a broad class of universal estimators (containing many well known approaches including ours) cannot be sample optimal for every $1$-Lipschitz property when $\epsilon \ll n^{-1/3}$.

FOCS Conference 2021 Conference Paper

Multiway Online Correlated Selection

• Guy Blanc
• Moses Charikar

We give a 0. 5368-competitive algorithm for edge-weighted online bipartite matching. Prior to our work, the best competitive ratio was 0. 5086 due to Fahrbach, Huang, Tao, and Zadimoghaddam (FOCS 2020). They achieved their breakthrough result by developing a subroutine called online correlated selection (OCS) which takes as input a sequence of pairs and selects one item from each pair. Importantly, the selections the OCS makes are negatively correlated. We achieve our result by defining multiway OCSes which receive arbitrarily many elements at each step, rather than just two. In addition to better competitive ratios, our formulation allows for a simpler reduction from edge-weighted online bipartite matching to OCSes. While Fahrbach et al. used a factor-revealing linear program to optimize the competitive ratio, our analysis directly connects the competitive ratio to the parameters of the multiway OCS. Finally, we show that the formulation of Farhbach et al. can achieve a competitive ratio of at most 0. 5239, confirming that multiway OCSes are strictly more powerful.

NeurIPS Conference 2020 Conference Paper

Instance Based Approximations to Profile Maximum Likelihood

• Nima Anari
• Moses Charikar
• Kirankumar Shiragur
• Aaron Sidford

In this paper we provide a new efficient algorithm for approximately computing the profile maximum likelihood (PML) distribution, a prominent quantity in symmetric property estimation. We provide an algorithm which matches the previous best known efficient algorithms for computing approximate PML distributions and improves when the number of distinct observed frequencies in the given instance is small. We achieve this result by exploiting new sparsity structure in approximate PML distributions and providing a new matrix rounding algorithm, of independent interest. Leveraging this result, we obtain the first provable computationally efficient implementation of PseudoPML, a general framework for estimating a broad class of symmetric properties. Additionally, we obtain efficient PML-based estimators for distributions with small profile entropy, a natural instance-based complexity measure. Further, we provide a simpler and more practical PseudoPML implementation that matches the best-known theoretical guarantees of such an estimator and evaluate this method empirically.

FOCS Conference 2020 Conference Paper

Kernel Density Estimation through Density Constrained Near Neighbor Search

• Moses Charikar
• Michael Kapralov
• Navid Nouri
• Paris Siminelakis

In this paper we revisit the kernel density estimation problem: given a kernel K(x, y) and a dataset of n points in high dimensional Euclidean space, prepare a data structure that can quickly output, given a query q, a (1+ ε)-approximation to μ: =[1/(|P|)]Σ p∈P K(p, q). First, we give a single data structure based on classical near neighbor search techniques that improves upon or essentially matches the query time and space complexity for all radial kernels considered in the literature so far. We then show how to improve both the query complexity and runtime by using recent advances in data-dependent near neighbor search. We achieve our results by giving an new implementation of the natural importance sampling scheme. Unlike previous approaches, our algorithm first samples the dataset uniformly (considering a geometric sequence of sampling rates), and then uses existing approximate near neighbor search techniques on the resulting smaller dataset to retrieve the sampled points that lie at an appropriate distance from the query. We show that the resulting sampled dataset has strong geometric structure, making approximate near neighbor search return the required samples much more efficiently than for worst case datasets of the same size. As an example application, we show that this approach yields a data structure that achieves query time μ -(1+0(1))/4 and space complexity μ -(1+0(1)) for the Gaussian kernel. Our data dependent approach achieves query time μ -0. 173-0(1) and space μ -(1+0(1)) for the Gaussian kernel. The data dependent analysis relies on new techniques for tracking the geometric structure of the input datasets in a recursive hashing process that we hope will be of interest in other applications in near neighbor search.

NeurIPS Conference 2019 Conference Paper

A General Framework for Symmetric Property Estimation

• Moses Charikar
• Kirankumar Shiragur
• Aaron Sidford

In this paper we provide a general framework for estimating symmetric properties of distributions from i. i. d. samples. For a broad class of symmetric properties we identify the {\em easy} region where empirical estimation works and the {\em difficult} region where more complex estimators are required. We show that by approximately computing the profile maximum likelihood (PML) distribution \cite{ADOS16} in this difficult region we obtain a symmetric property estimation framework that is sample complexity optimal for many properties in a broader parameter regime than previous universal estimation approaches based on PML. The resulting algorithms based on these \emph{pseudo PML distributions} are also more practical.

STOC Conference 2019 Conference Paper

Efficient profile maximum likelihood for universal symmetric property estimation

• Moses Charikar
• Kirankumar Shiragur
• Aaron Sidford

Estimating symmetric properties of a distribution, e.g. support size, coverage, entropy, distance to uniformity, are among the most fundamental problems in algorithmic statistics. While these properties have been studied extensively and separate optimal estimators have been produced, in striking recent work Acharya et al. provided a single estimator that is competitive for each. They showed that the value of the property on the distribution that approximately maximizes profile likelihood (PML) , i.e. the probability of observed frequency of frequencies, is sample competitive with respect to a broad class of estimators. Unfortunately, prior to this work, there was no known polynomial time algorithm to compute such an approximation or use PML to obtain a universal plug-in estimator. In this paper we provide an algorithm that, given n samples from a distribution, computes an approximate PML distribution up to a multiplicative error of exp( n 2/3 poly log( n )) in nearly linear time. Generalizing work of Acharya et al. we show that our algorithm yields a universal plug-in estimator that is competitive with a broad range of estimators up to accuracy є = Ω( n −0.166 ). Further, we provide efficient polynomial-time algorithms for computing a d -dimensional generalization of PML (for constant d ) that allows for universal plug-in estimation of symmetric relationships between distributions.

SODA Conference 2019 Conference Paper

Hierarchical Clustering better than Average-Linkage

• Moses Charikar
• Vaggos Chatziafratis
• Rad Niazadeh

Hierarchical Clustering (HC) is a widely studied problem in exploratory data analysis, usually tackled by simple agglomerative procedures like average-linkage, single-linkage or complete-linkage. In this paper we focus on two objectives, introduced recently to give insight into the performance of average-linkage clustering: a similarity based HC objective proposed by [21] and a dissimilarity based HC objective proposed by [9]. In both cases, we present tight counterexamples showing that average-linkage cannot obtain better than ⅓ and ⅔ approximations respectively (in the worst-case), settling an open question raised in [21]. This matches the approximation ratio of a random solution, raising a natural question: can we beat average-linkage for these objectives? We answer this in the affirmative, giving two new algorithms based on semidefinite programming with provably better guarantees.

FOCS Conference 2019 Conference Paper

Multi-resolution Hashing for Fast Pairwise Summations

• Moses Charikar
• Paris Siminelakis

A basic computational primitive in the analysis of massive datasets is summing simple functions over a large number of objects. Modern applications pose an additional challenge in that such functions often depend on a parameter vector y (query) that is unknown a priori. Given a set of points X and a pairwise function w(x, y), we study the problem of designing a data-structure that enables sub-linear time approximation of the summation of w(x, y) for all x in X for any query point y. By combining ideas from Harmonic Analysis (partitions of unity and approximation theory) with Hashing-Based-Estimators [Charikar, Siminelakis FOCS'17], we provide a general framework for designing such data structures through hashing that reaches far beyond what previous techniques allowed. A key design principle is constructing a collection of hash families, each inducing a different collision probability between points in the dataset, such that the pointwise supremum of the collision probabilities scales as the square root of the function w(x, y). This leads to a data-structure that approximates pairwise summations using a sub-linear number of samples from each hash family. Using this new framework along with Distance Sensitive Hashing [Aumuller, Christiani, Pagh, Silvestri PODS'18], we show that such a collection can be constructed and evaluated efficiently for log-convex functions of the inner product between two vectors. Our method leads to data structures with sub-linear query time that significantly improve upon random sampling and can be used for Kernel Density, Partition Function Estimation and sampling.

ICML Conference 2019 Conference Paper

Rehashing Kernel Evaluation in High Dimensions

• Paris Siminelakis
• Kexin Rong 0001
• Peter Bailis
• Moses Charikar
• Philip Alexander Levis

Kernel methods are effective but do not scale well to large scale data, especially in high dimensions where the geometric data structures used to accelerate kernel evaluation suffer from the curse of dimensionality. Recent theoretical advances have proposed fast kernel evaluation algorithms leveraging hashing techniques with worst-case asymptotic improvements. However, these advances are largely confined to the theoretical realm due to concerns such as super-linear preprocessing time and diminishing gains in non-worst case datasets. In this paper, we close the gap between theory and practice by addressing these challenges via provable and practical procedures for adaptive sample size selection, preprocessing time reduction, and refined variance bounds that quantify the data-dependent performance of random sampling and hashing-based kernel evaluation methods. Our experiments show that these new tools offer up to $10\times$ improvement in evaluation time on a range of synthetic and real-world datasets.

FOCS Conference 2018 Conference Paper

Efficient Density Evaluation for Smooth Kernels

• Arturs Backurs
• Moses Charikar
• Piotr Indyk
• Paris Siminelakis

Given a kernel function k(. ,.) and a dataset P⊂ R^d, the kernel density function of P at a point x∈ R d is equal to KDF P (x): = 1/|P| Σy∈P k(x, y). Kernel density evaluation has numerous applications, in scientific computing, statistics, computer vision, machine learning and other fields. In all of them it is necessary to evaluate KDF P(x) quickly, often for many inputs x and large point-sets P. In this paper we present a collection of algorithms for efficient KDF evaluation under the assumptions that the kernel k is "smooth", i. e. the value changes at most polynomially with the distance. This assumption is satisfied by several well-studied kernels, including the (generalized) t-student kernel and rational quadratic kernel. For smooth kernels, we give a data structure that, after O(dn log (Φ n)/ε^2) preprocessing, estimates KDF P(x) up to a factor of 1 ± ε in O(dlog (Φ n)/ε 2 ) time, where Phi; is the aspect ratio. The log(Φn) term can be further replaced by log n under an additional decay condition on k, which is satisfied by the aforementioned examples. We further extend the results in two ways. First, we use low-distortion embeddings to extend the results to kernels defined for spaces other than ℓ_2. The key feature of this reduction is that the distortion of the embedding affects only the running time of the algorithm, not the accuracy of the estimation. As a result, we obtain (1+ε)-approximate estimation algorithms for kernels over other ℓ p norms, Earth-Mover Distance, and other metric spaces. Second, for smooth kernels that are decreasing with distance, we present a general reduction from density estimation to approximate near neighbor in the underlying space. This allows us to construct algorithms for general doubling metrics, as well as alternative algorithms for l p norms and other spaces.

ICML Conference 2018 Conference Paper

Hierarchical Clustering with Structural Constraints

• Vaggos Chatziafratis
• Rad Niazadeh
• Moses Charikar

Hierarchical clustering is a popular unsupervised data analysis method. For many real-world applications, we would like to exploit prior information about the data that imposes constraints on the clustering hierarchy, and is not captured by the set of features available to the algorithm. This gives rise to the problem of hierarchical clustering with structural constraints. Structural constraints pose major challenges for bottom-up approaches like average/single linkage and even though they can be naturally incorporated into top-down divisive algorithms, no formal guarantees exist on the quality of their output. In this paper, we provide provable approximation guarantees for two simple top-down algorithms, using a recently introduced optimization viewpoint of hierarchical clustering with pairwise similarity information (Dasgupta, 2016). We show how to find good solutions even in the presence of conflicting prior information, by formulating a constraint-based regularization of the objective. Furthemore, we explore a variation of this objective for dissimilarity information (Cohen-Addad et al. , 2018) and improve upon current techniques. Finally, we demonstrate our approach on a real dataset for the taxonomy application.

ICML Conference 2018 Conference Paper

Local Density Estimation in High Dimensions

• Xian Wu 0009
• Moses Charikar
• Vishnu Natchu

An important question that arises in the study of high dimensional vector representations learned from data is: given a set D of vectors and a query q, estimate the number of points within a specified distance threshold of q. Our algorithm uses locality sensitive hashing to preprocess the data to accurately and efficiently estimate the answers to such questions via an unbiased estimator that uses importance sampling. A key innovation is the ability to maintain a small number of hash tables via preprocessing data structures and algorithms that sample from multiple buckets in each hash table. We give bounds on the space requirements and query complexity of our scheme, and demonstrate the effectiveness of our algorithm by experiments on a standard word embedding dataset.

SODA Conference 2017 Conference Paper

Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics

• Moses Charikar
• Vaggos Chatziafratis

Dasgupta recently introduced a cost function for the hierarchical clustering of a set of points given pairwise similarities between them. He showed that this function is NP-hard to optimize, but a top-down recursive partitioning heuristic based on an a n -approximation algorithm for uniform sparsest cut gives an approximation of O (a n log n ) (the current best algorithm has We show that the aforementioned sparsest cut heuristic in fact obtains an O (α n )-approximation. The algorithm also applies to a generalized cost function studied by Dasgupta. Moreover, we obtain a strong inapproximability result, showing that the Hierarchical Clustering objective is hard to approximate to within any constant factor assuming the Small-Set Expansion (SSE) Hypothesis. Finally, we discuss approximation algorithms based on convex relaxations. We present a spreading metric SDP relaxation for the problem and show that it has integrality gap at most The advantage of the SDP relative to the sparsest cut heuristic is that it provides an explicit lower bound on the optimal solution and could potentially yield an even better approximation for hierarchical clustering. In fact our analysis of this SDP served as the inspiration for our improved analysis of the sparsest cut heuristic. We also show that a spreading metric LP relaxation gives an O (log n )-approximation.

FOCS Conference 2017 Conference Paper

Hashing-Based-Estimators for Kernel Density in High Dimensions

• Moses Charikar
• Paris Siminelakis

Given a set of points P ⊂ ℝ d and a kernel k, the Kernel Density Estimate at a point x ∈ ℝ d is defined as KDE P (x) = 1/|P| Σy ∈P k(x, y). We study the problem of designing a data structure that given a data set P and a kernel function, returns approximations to the kernel density of a query point in sublinear time. We introduce a class of unbiased estimators for kernel density implemented through locality-sensitive hashing, and give general theorems bounding the variance of such estimators. These estimators give rise to efficient data structures for estimating the kernel density in high dimensions for a variety of commonly used kernels. Our work is the first to provide data-structures with theoretical guarantees that improve upon simple random sampling in high dimensions.

STOC Conference 2017 Conference Paper

Learning from untrusted data

• Moses Charikar
• Jacob Steinhardt
• Gregory Valiant

The vast majority of theoretical results in machine learning and statistics assume that the training data is a reliable reflection of the phenomena to be learned. Similarly, most learning techniques used in practice are brittle to the presence of large amounts of biased or malicious data. Motivated by this, we consider two frameworks for studying estimation, learning, and optimization in the presence of significant fractions of arbitrary data.

NeurIPS Conference 2016 Conference Paper

Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction

• Jacob Steinhardt
• Gregory Valiant
• Moses Charikar

We consider a crowdsourcing model in which n workers are asked to rate the quality of n items previously generated by other workers. An unknown set of $\alpha n$ workers generate reliable ratings, while the remaining workers may behave arbitrarily and possibly adversarially. The manager of the experiment can also manually evaluate the quality of a small number of items, and wishes to curate together almost all of the high-quality items with at most an fraction of low-quality items. Perhaps surprisingly, we show that this is possible with an amount of work required of the manager, and each worker, that does not scale with n: the dataset can be curated with $\tilde{O}(1/\beta\alpha\epsilon^4)$ ratings per worker, and $\tilde{O}(1/\beta\epsilon^2)$ ratings by the manager, where $\beta$ is the fraction of high-quality items. Our results extend to the more general setting of peer prediction, including peer grading in online classrooms.

SODA Conference 2014 Conference Paper

Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach

• Nikhil Bansal 0001
• Moses Charikar
• Ravishankar Krishnaswamy
• Shi Li 0001

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 Õ (log 1, 5 n ) approximation algorithm for the problem improving upon the previous Õ (log 2 n ) approximation. We also show an Ω(log 1/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.

STOC Conference 2014 Conference Paper

Smoothed analysis of tensor decompositions

• Aditya Bhaskara
• Moses Charikar
• Ankur Moitra
• Aravindan Vijayaraghavan

SODA Conference 2012 Conference Paper

Polynomial integrality gaps for strong SDP relaxations of Densest k -subgraph

• Aditya Bhaskara
• Moses Charikar
• Aravindan Vijayaraghavan
• Venkatesan Guruswami
• Yuan Zhou 0007

The Densest k -subgraph problem (i. e. find a size k subgraph with maximum number of edges), is one of the notorious problems in approximation algorithms. There is a significant gap between known upper and lower bounds for Densest k -subgraph: the current best algorithm gives an ≈ O ( n 1/4 ) approximation, while even showing a small constant factor hardness requires significantly stronger assumptions than P ≠ NP. In addition to interest in designing better algorithms, a number of recent results have exploited the conjectured hardness of Densest k -subgraph and its variants. Thus, understanding the approximability of Densest k -subgraph is an important challenge. In this work, we give evidence for the hardness of approximating Densest k -subgraph within polynomial factors. Specifically we expose the limitations of strong semidefinite programs from SDP hierarchies in solving Densest k -subgraph. Our results include: • A lower bound of Ω( n 1/4 /log 3 n ) on the integrality gap for Ω(log n / log log n ) rounds of the Sherali-Adams relaxation for Densest k -subgraph. This also holds for the relaxation obtained from Sherali-Adams with an added SDP constraint. Our gap instances are in fact Erdös-Renyi random graphs. • For every ∊ > 0, a lower bound of n 2/53 − ∊ on the integrality gap of n Ω(∊) rounds of the Lasserre SDP relaxation for Densest k -subgraph, and an n Ω ∊ (1) gap for n 1−∊ rounds. Our construction proceeds via a reduction from random instances of a certain Max-CSP over large domains. In the absence of inapproximability results for Densest k -subgraph, our results show that beating a factor of n Ω(1) is a barrier for even the most powerful SDPs, and in fact even beating the best known n 1/4 factor is a barrier for current techniques. Our results indicate that approximating Densest k -subgraph within a polynomial factor might be a harder problem than Unique Games or Small Set Expansion, since these problems were recently shown to be solvable using n ∊ ω(1) rounds of the Lasserre hierarchy where ∊ is the completeness parameter in Unique Games and Small Set Expansion.

FOCS Conference 2011 Conference Paper

Near Linear Lower Bound for Dimension Reduction in L1

• Alexandr Andoni
• Moses Charikar
• Ofer Neiman
• Huy L. Nguyên

Given a set of n points in ℓ 1, how many dimensions are needed to represent all pair wise distances within a specific distortion? This dimension-distortion tradeoff question is well understood for the ℓ 2 norm, where O((log n)/ϵ 2 ) dimensions suffice to achieve 1+ϵ distortion. In sharp contrast, there is a significant gap between upper and lower bounds for dimension reduction in ℓ 1. A recent result shows that distortion 1+ϵ can be achieved with n/ϵ 2 dimensions. On the other hand, the only lower bounds known are that distortion δ requires n Ω(1/δ 2 ) dimensions and that distortion 1+ϵ requires n 1/2-O(ϵ log(1/ϵ)) dimensions. In this work, we show the first near linear lower bounds for dimension reduction in ℓ 1. In particular, we show that 1+ϵ distortion requires at least n 1-O(1 / log(1/ϵ)) dimensions. Our proofs are combinatorial, but inspired by linear programming. In fact, our techniques lead to a simple combinatorial argument that is equivalent to the LP based proof of Brinkman-Charikar for lower bounds on dimension reduction in ℓ 1.

SODA Conference 2011 Conference Paper

Tight Hardness Results for Minimizing Discrepancy

• Moses Charikar
• Alantha Newman
• Aleksandar Nikolov

In the Discrepancy problem, we are given M sets { S 1, …, S M } on N elements. Our goal is to find an assignment χ of {– 1, +1} values to elements, so as to minimize the maximum discrepancy. Recently, Bansal gave an efficient algorithm for achieving O (√ N ) discrepancy for any set system where M = O ( N ) [Ban10], giving a constructive version of Spencer's proof that the discrepancy of any set system is at most O (√ N ) for this range of M [Spe85]. We show that from the perspective of computational efficiency, these results are tight for general set systems where M = O ( N ). Specifically, we show that it is NP-hard to distinguish between such set systems with discrepancy zero and those with discrepancy Ω(√ N ). This means that even if the optimal solution has discrepancy zero, we cannot hope to efficiently find a coloring with discrepancy o (√ N ). We also consider the hardness of the Discrepancy problem on sets with bounded shatter function, and show that the upper bounds due to Matoušek [Mat95] are tight for these sets systems as well. The hardness results in both settings are obtained from a common framework: we compose a family of high discrepancy set systems with set systems for which it is NP-hard to distinguish instances with discrepancy zero from instances in which a large number of the sets (i. e. constant fraction of the sets) have non-zero discrepancy. Our composition amplifies this zero versus non-zero gap.

STOC Conference 2010 Conference Paper

Detecting high log-densities: an O ( n 1/4 ) approximation for densest k -subgraph

• Aditya Bhaskara
• Moses Charikar
• Eden Chlamtac
• Uriel Feige
• Aravindan Vijayaraghavan

In the Densest k-Subgraph problem, given a graph G and a parameter k, one needs to find a subgraph of G induced on k vertices that contains the largest number of edges. There is a significant gap between the best known upper and lower bounds for this problem. It is NP-hard, and does not have a PTAS unless NP has subexponential time algorithms. On the other hand, the current best known algorithm of Feige, Kortsarz and Peleg, gives an approximation ratio of n 1/3 - c for some fixed c>0 (later estimated at around c= 1/90). We present an algorithm that for every ε> 0 approximates the Densest k-Subgraph problem within a ratio of n ¼ + ε in time n O(1/ε) . If allowed to run for time n O(log n) , the algorithm achieves an approximation ratio of O(n ¼ ). Our algorithm is inspired by studying an average-case version of the problem where the goal is to distinguish random graphs from random graphs with planted dense subgraphs -- the approximation ratio we achieve for the general case matches the "distinguishing ratio" we obtain for this planted problem. At a high level, our algorithms involve cleverly counting appropriately defined trees of constant size in G, and using these counts to identify the vertices of the dense subgraph. We say that a graph G(V,E) has log-density α if its average degree is Θ(|V| α ). The algorithmic core of our result is a procedure to output a k-subgraph of 'nontrivial' density whenever the log-density of the densest k-subgraph is larger than the log-density of the host graph. We outline an extension to our approximation algorithm which achieves an O(n ¼ -ε )-approximation in O(2 n O(ε) ) time. We also show that, for certain parameter ranges, eigenvalue and SDP based techniques can outperform our basic distinguishing algorithm for random instances (in polynomial time), though without improving upon the O(n ¼ ) guarantee overall.

FOCS Conference 2010 Conference Paper

Vertex Sparsifiers and Abstract Rounding Algorithms

• Moses Charikar
• Frank Thomson Leighton
• Shi Li 0001
• Ankur Moitra

The notion of vertex sparsification (in particular cut-sparsification) is introduced in, where it was shown that for any graph G = (V, E) and any subset of k terminals K ⊂ V, there is a polynomial time algorithm to construct a graph H = (K, E H ) on just the terminal set so that simultaneously for all cuts (A, K-A), the value of the minimum cut in G separating A from K-A is approximately the same as the value of the corresponding cut in H. Then approximation algorithms can be run directly on H as a proxy for running on G. We give the first super-constant lower bounds for how well a cut-sparsifier H can simultaneously approximate all minimum cuts in G. We prove a lower bound of Ω(log 1/4 k) this is polynomially-related to the known upper bound of O(log k/log log k). Independently, a similar lower bound is given in. This is an exponential improvement on the Ω(log log k) bound given in which in fact was for a stronger vertex sparsification guarantee, and did not apply to cut sparsifiers. Despite this negative result, we show that for many natural optimization problems, we do not need to incur a multiplicative penalty for our reduction. Roughly, we show that any rounding algorithm which also works for the O-extension relaxation can be used to construct good vertex-sparsifiers for which the optimization problem is easy. Using this, we obtain optimal O(log k)-competitive Steiner oblivious routing schemes, which generalize the results in. We also demonstrate that for a wide range of graph packing problems (which includes maximum concurrent flow, maximum multiflow and multicast routing, among others, as a special case), the integrality gap of the linear program is always at most O(log k) times the integrality gap restricted to trees. Lastly, we use our ideas to give an efficient construction for vertex-sparsifiers that match the current best existential results - this was previously open. Our algorithm makes novel use of Earth-mover constraints.

STOC Conference 2009 Conference Paper

Integrality gaps for Sherali-Adams relaxations

• Moses Charikar
• Konstantin Makarychev
• Yury Makarychev

We prove strong lower bounds on integrality gaps of Sherali-Adams relaxations for MAX CUT, Vertex Cover, Sparsest Cut and other problems. Our constructions show gaps for Sherali-Adams relaxations that survive n δ rounds of lift and project. For MAX CUT and Vertex Cover, these show that even n δ rounds of Sherali-Adams do not yield a better than 2-ε approximation. The main combinatorial challenge in constructing these gap examples is the construction of a fractional solution that is far from an integer solution, but yet admits consistent distributions of local solutions for all small subsets of variables. Satisfying this consistency requirement is one of the major hurdles to constructing Sherali-Adams gap examples. We present a modular recipe for achieving this, building on previous work on metrics with a local-global structure. We develop a conceptually simple geometric approach to constructing Sherali-Adams gap examples via constructions of consistent local SDP solutions. This geometric approach is surprisingly versatile. We construct Sherali-Adams gap examples for Unique Games based on our construction for MAX CUT together with a parallel repetition like procedure. This in turn allows us to obtain Sherali-Adams gap examples for any problem that has a Unique Games based hardness result (with some additional conditions on the reduction from Unique Games). Using this, we construct 2-ε gap examples for Maximum Acyclic Subgraph that rules out any family of linear constraints with support at most n δ .

STOC Conference 2009 Conference Paper

MaxMin allocation via degree lower-bounded arborescences

• MohammadHossein Bateni
• Moses Charikar
• Venkatesan Guruswami

We consider the problem of MaxMin allocation of indivisible goods. There are m items to be distributed among n players. Each player $i$ has a nonnegative valuation p ij for an item j, and the goal is to allocate items to players so as to maximize the minimum total valuation received by each player. There is a large gap in our understanding of this problem. The best known positive result is an ~O(√ n)-approximation algorithm, while there is only a factor 2 hardness known. Better algorithms are known for the restricted assignment case where each item has exactly one nonzero value for the players. We study the effect of bounded degree for items: each item has a nonzero value for at most D players. We show that essentially the case D = 3 is equivalent to the general case, and give a 4-approximation algorithm for D = 2.

SODA Conference 2007 Conference Paper

A divide and conquer algorithm for d -dimensional arrangement

• Moses Charikar
• Konstantin Makarychev
• Yury Makarychev

STOC Conference 2007 Conference Paper

Improved approximation for directed cut problems

• Amit Agarwal
• Noga Alon
• Moses Charikar

We present improved approximation algorithms for directed multicutand directed sparsest cut. The current best known approximationratio for these problems is O(n 1/2 ). We obtain an Õ(n 11/23 )-approximation. Our algorithm works with thenatural LP relaxation used in prior work. We use a randomized roundingalgorithm with a more sophisticated charging scheme and analysis toobtain our improvement. This also implies a Õ(n 11/23 ) upper bound on the ratio between the maximum multicommodity flowand minimum multicut in directed graphs.

FOCS Conference 2007 Conference Paper

Local Global Tradeoffs in Metric Embeddings

• Moses Charikar
• Konstantin Makarychev
• Yury Makarychev

Suppose that every k points in a metric space X are D-distortion embeddable into lscr 1. We give upper and lower bounds on the distortion required to embed the entire space X into lscr 1. This is a natural mathematical question and is also motivated by the study of relaxations obtained by lift-and-project methods for graph partitioning problems. In this setting, we show that X can be embedded into lscr 1 with distortion O(D times log(|X|/k)). Moreover, we give a lower bound showing that this result is tight if D is bounded away from I. For D = 1 + delta we give a lower bound of Omega(log(|X|/k/ log( 1/delta)); and for D = 1, we give a lower bound of Omega( log |X|/(log k +log log | X|)). Our bounds significantly improve on the results of Arora, Jjovdsz, Newman, Rabani, Rabinovich and Vempala, who initiated a study of these questions.

SODA Conference 2007 Conference Paper

Near-optimal algorithms for maximum constraint satisfaction problems

• Moses Charikar
• Konstantin Makarychev
• Yury Makarychev

FOCS Conference 2007 Conference Paper

On the Advantage over Random for Maximum Acyclic Subgraph

• Moses Charikar
• Konstantin Makarychev
• Yury Makarychev

In this paper we present a new approximation algorithm for the Max Acyclic Subgraph problem. Given an instance where the maximum acyclic subgraph contains 1/2 + delta fraction of all edges, our algorithm finds an acyclic subgraph with 1/2 + Omega(delta/ log n) fraction of all edges.

SODA Conference 2006 Conference Paper

A robust maximum completion time measure for scheduling

• Moses Charikar
• Samir Khuller

SODA Conference 2006 Conference Paper

Directed metrics and directed graph partitioning problems

• Moses Charikar
• Konstantin Makarychev
• Yury Makarychev

SODA Conference 2006 Conference Paper

l 2 2 spreading metrics for vertex ordering problems

• Moses Charikar
• MohammadTaghi Hajiaghayi
• Howard J. Karloff
• Satish Rao

STOC Conference 2006 Conference Paper

Near-optimal algorithms for unique games

• Moses Charikar
• Konstantin Makarychev
• Yury Makarychev

Unique games are constraint satisfaction problems that can be viewed as a generalization of Max-Cut to a larger domain size. The Unique Games Conjecture states that it is hard to distinguish between instances of unique games where almost all constraints are satisfiable and those where almost none are satisfiable. It has been shown to imply a number of inapproximability results for fundamental problems that seem difficult to obtain by more standard complexity assumptions. Thus, proving or refuting this conjecture is an important goal. We present significantly improved approximation algorithms for unique games. For instances with domain size k where the optimal solution satisfies 1-ε fraction of all constraints, our algorithms satisfy roughly k -ε/(2-ε) and 1- O(√εlog k) fraction of all constraints. Our algorithms are based on rounding a natural semidefinite programming relaxation for the problem and their performance almost matches the integrality gap of this relaxation. Our results are near optimal if the Unique Games Conjecture is true, i.e. any improvement (beyond low order terms) would refute the conjecture.

SODA Conference 2005 Conference Paper

A tight threshold for metric Ramsey phenomena

• Moses Charikar
• Adriana Karagiozova

STOC Conference 2005 Conference Paper

Aggregating inconsistent information: ranking and clustering

• Nir Ailon
• Moses Charikar
• Alantha Newman

We address optimization problems in which we are given contradictory pieces of input information and the goal is to find a globally consistent solution that minimizes the number of disagreements with the respective inputs. Specifically, the problems we address are rank aggregation, the feedback arc set problem on tournaments, and correlation and consensus clustering. We show that for all these problems (and various weighted versions of them), we can obtain improved approximation factors using essentially the same remarkably simple algorithm. Additionally, we almost settle a long-standing conjecture of Bang-Jensen and Thomassen and show that unless NP⊆BPP, there is no polynomial time algorithm for the problem of minimum feedback arc set in tournaments.

SODA Conference 2005 Conference Paper

Approximating the average response time in broadcast scheduling

• Nikhil Bansal 0001
• Moses Charikar
• Sanjeev Khanna
• Joseph Naor

FOCS Conference 2005 Conference Paper

Fitting tree metrics: Hierarchical clustering and Phylogeny

• Nir Ailon
• Moses Charikar

Given dissimilarity data on pairs of objects in a set, we study the problem of fitting a tree metric to this data so as to minimize additive error (i. e. some measure of the difference between the tree metric and the given data). This problem arises in constructing an M-level hierarchical clustering of objects (or an ultrametric on objects) so as to match the given dissimilarity data - a basic problem in statistics. Viewed in this way, the problem is a generalization of the correlation clustering problem (which corresponds to M = 1). We give a very simple randomized combinatorial algorithm for the M-level hierarchical clustering problem that achieves an approximation ratio of M+2. This is a generalization of a previous factor 3 algorithm for correlation clustering on complete graphs. The problem of fitting tree metrics also arises in phylogeny where the objective is to learn the evolution tree by fitting a tree to dissimilarity data on taxa. The quality of the fit is measured by taking the l/sub p/ norm of the difference between the tree metric constructed and the given data. Previous results obtained a factor 3 approximation for finding the closest tree tree metric under the l/spl infin/ norm. No nontrivial approximation for general l/sub p/ norms was known before. We present a novel LP formulation for this problem and obtain an O((log n log log n)/sup 1/p/) approximation using this. Enroute, we obtain an O((log n log log n)/sup 1/p/) approximation for the closest ultrametric under the l/sub p/ norm. Our techniques are based on representing and viewing an ultrametric as a hierarchy of clusterings, and may be useful in other contexts.

STOC Conference 2005 Conference Paper

O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems

• Amit Agarwal
• Moses Charikar
• Konstantin Makarychev
• Yury Makarychev

We give O(√log n)-approximation algorithms for the MIN UNCUT, MIN 2CNF DELETION, DIRECTED BALANCED SEPERATOR, and DIRECTED SPARSEST CUT problems. The previously best known algorithms give an O(log n)-approximation for MIN UNCUT [9], DIRECTED BALANCED SEPERATOR [17], DIRECTED SPARSEST CUT [17], and an O(log n log log n)-approximation for MIN 2CNF DELETION [14].We also show that the integrality gap of an SDP relaxation of the MINIMUM MULTICUT problem is Ω(log n).

STOC Conference 2005 Conference Paper

On non-uniform multicommodity buy-at-bulk network design

• Moses Charikar
• Adriana Karagiozova

We study the multicommodity buy-at-bulk network design problem in which we seek to design a network that satisfies the demands between terminals from a given set of source-sink pairs. The key characteristic of this problem is the fact that the cost functions associated with the edges of the graph are sub-additive monotone and hence experience economies of scale . In the non-uniform case, each edge has its own cost function -- possibly different from other edges. Special cases of this problem have been studied extensively: there are approximation algorithms when the edge cost functions are identical or when all source-sink pairs share the same source. We present the first non-trivial approximation algorithm for the general case. Our algorithm is an extremely simple randomized greedy algorithm and has an approximation guarantee of exp( O √ln n ln ln n )) when the instance has at most n source-sink pairs with unit demands. In the case of general demands, this yields an approximation factor of exp( O √ln N ln ln N )), where N is the sum of all demands.

TCS Journal 2004 Journal Article

Finding frequent items in data streams

• Moses Charikar
• Kevin Chen
• Martin Farach-Colton

We present a 1-pass algorithm for estimating the most frequent items in a data stream using limited storage space. Our method relies on a data structure called a COUNT SKETCH, which allows us to reliably estimate the frequencies of frequent items in the stream. Our algorithm achieves better space bounds than the previously known best algorithms for this problem for several natural distributions on the item frequencies. In addition, our algorithm leads directly to a 2-pass algorithm for the problem of estimating the items with the largest (absolute) change in frequency between two data streams. To our knowledge, this latter problem has not been previously studied in the literature.

FOCS Conference 2004 Conference Paper

Maximizing Quadratic Programs: Extending Grothendieck's Inequality

• Moses Charikar
• Anthony Wirth

This paper considers the following type of quadratic programming problem. Given an arbitrary matrix A, whose diagonal elements are zero, find x /spl isin/ {-1, 1}/sup n/ such that x/sup T/Ax is maximized. Our approximation algorithm for this problem uses the canonical semidefinite relaxation and returns a solution whose ratio to the optimum is in /spl Omega/(1/ logn). This quadratic programming problem can be seen as an extension to that of maximizing x/sup T/Ay (where y's components are also /spl plusmn/1). Grothendieck's inequality states that the ratio of the optimum value of the latter problem to the optimum of its canonical semidefinite relaxation is bounded below by a constant. The study of this type of quadratic program arose from a desire to approximate the maximum correlation in correlation clustering. Nothing substantive was known about this problem; we present an /spl Omega/ (1/logn) approximation, based on our quadratic programming algorithm. We can also guarantee that our quadratic programming algorithm returns a solution to the MAXCUT problem that has a significant advantage over a random assignment.

FOCS Conference 2004 Conference Paper

On the Integrality Ratio for Asymmetric TSP

• Moses Charikar
• Michel X. Goemans
• Howard J. Karloff

The traveling salesman problem comes in two variants. The symmetric version (STSP) assumes that the cost c/sub ij/ of going to city i to city j is equal to c/sub ji/, while the more general asymmetric version (ATSP) does not make this assumption. In both cases, it is usually assumed that we are in the metric case, i. e. , the costs satisfy the triangle inequality: c/sub ij/ + c/sub jk/ /spl ges/ c/sub ik/ for all i, j, k. In this assumption, we improve the lower bound on the integrality ratio of the Held-Karp bound for asymmetric TSP (with triangle inequality) from 4/3 to 2.

STOC Conference 2003 Conference Paper

Better streaming algorithms for clustering problems

• Moses Charikar
• Liadan O'Callaghan
• Rina Panigrahy

We study clustering problems in the streaming model, where the goal is to cluster a set of points by making one pass (or a few passes) over the data using a small amount of storage space. Our main result is a randomized algorithm for the k --Median problem which produces a constant factor approximation in one pass using storage space O(k poly log n ). This is a significant improvement of the previous best algorithm which yielded a 2 O (1/ε) approximation using O(n ε ) space. Next we give a streaming algorithm for the k --Median problem with an arbitrary distance function. We also study algorithms for clustering problems with outliers in the streaming model. Here, we give bicriterion guarantees, producing constant factor approximations by increasing the allowed fraction of outliers slightly.

FOCS Conference 2003 Conference Paper

Clustering with Qualitative Information

• Moses Charikar
• Venkatesan Guruswami
• Anthony Wirth

We consider the problem of clustering a collection of elements based on pairwise judgments of similarity and dissimilarity. N. Bansal et al. (2002) cast the problem thus: given a graph G whose edges are labeled "+" (similar) or "-" (dissimilar), partition the vertices into clusters so that the number of pairs correctly (resp. incorrectly) classified with respect to the input labeling is maximized (resp. minimized). Complete graphs, where the classifier labels every edge, and general graphs, where some edges are not labeled, are both worth studying. We answer several questions left open by N. Bansal et al. (2002) and provide a sound overview of clustering with qualitative information. We give a factor 4 approximation for minimization on complete graphs, and a factor O(log n) approximation for general graphs. For the maximization version, a PTAS for complete graphs is shown by N. Bansal et al. (2002); we give a factor 0. 7664 approximation for general graphs, noting that a PTAS is unlikely by proving APX-hardness. We also prove the APX-hardness of minimization on complete graphs.

FOCS Conference 2003 Conference Paper

On the Impossibility of Dimension Reduction in l 1

• Bo Brinkman
• Moses Charikar

The Johnson-Lindenstrauss Lemma shows that any n points in Euclidean space (with distances measured by the /spl lscr//sub 2/ norm) may be mapped down to O((log n)//spl epsiv//sup 2/) dimensions such that no pairwise distance is distorted by more than a (1+ /spl epsiv/) factor. Determining whether such dimension reduction is possible in /spl lscr//sub 1/ has been an intriguing open question. We show strong lower bounds for general dimension reduction in /spl lscr//sub 1/. We give an explicit family of n points in /spl lscr//sub 1/ such that any embedding with distortion /spl delta/ requires n/sup /spl Omega/(1//spl delta/2)/ dimensions. This proves that there is no analog of the Johnson-Lindenstrauss Lemma for /spl lscr//sub 1/; in fact embedding with any constant distortion requires n/sup /spl Omega/(1)/ dimensions. Further, embedding the points into /spl lscr//sub 1/ with 1 + /spl epsiv/ distortion requires n/sup 1/2 -O(/spl epsiv/log(1//spl epsiv/))/ dimensions. Our proof establishes this lower bound for shortest path metrics of series-parallel graphs. We make extensive use of linear programming and duality in devising our bounds. We expect that the tools and techniques we develop will be useful for future investigations of embeddings into /spl lscr//sub 1/.

STOC Conference 2002 Conference Paper

Approximating the smallest grammar: Kolmogorov complexity in natural models

• Moses Charikar
• Eric Lehman
• Ding Liu
• Rina Panigrahy
• Manoj Prabhakaran 0001
• April Rasala
• Amit Sahai
• Abhi Shelat

We consider the problem of finding the smallest context-free grammar that generates exactly one given string of length n . The size of this grammar is of theoretical interest as an efficiently computable variant of Kolmogorov complexity. The problem is of practical importance in areas such as data compression and pattern extraction.The smallest grammar is known to be hard to approximate to within a constant factor, and an o (log n /log log n ) approximation would require progress on a long-standing algebraic problem [10]. Previously, the best proved approximation ratio was O ( n 1/2 ) for the Bisection algorithm [8]. Our main result is an exponential improvement of this ratio; we give an O (log ( n/g * )) approximation algorithm, where g * is the size of the smallest grammar.We then consider other computable variants of Kolomogorov complexity. In particular we give an O (log 2 n ) approximation for the smallest non-deterministic finite automaton with advice that produces a given string. We also apply our techniques to "advice-grammars" and "edit-grammars", two other natural models of string complexity.

FOCS Conference 2002 Conference Paper

Dimension Reduction in the \ell _1 Norm

• Moses Charikar
• Amit Sahai

The Johnson-Lindenstrauss lemma shows that any set of n points in Euclidean space can be mapped linearly down to O((log n)//spl epsi//sup 2/) dimensions such that all pairwise distances are distorted by at most 1+/spl epsi/. We study the basic question of whether there exists an analogue of the Johnson-Lindenstrauss lemma for the /spl lscr//sub 1/ norm? Note that Johnson-Lindenstrauss lemma gives a linear embedding which is independent of the point set. For the /spl lscr//sub 1/ norm, we show that one cannot hope to use linear embeddings as a dimensionality reduction tool for general point sets, even if the linear embedding is chosen as a function of the given point set. In particular, we construct a set of O(n) points in /spl lscr//sub 1//sup n/ such that any linear embedding into /spl lscr//sub 1//sup d/ must incur a distortion of /spl Omega//spl radic/(n/d). This bound is tight up to a log n factor. We then initiate a systematic study of general classes of /spl lscr//sub 1/ embeddable metrics that admit low dimensional, small distortion embeddings. In particular, we show dimensionality reduction theorems for tree metrics, circular-decomposable metrics, and metrics supported on K/sub 2, 3/-free graphs, giving embeddings into /spl lscr//sub 1//sup O(log(2) n)/ with constant distortion. Finally, we also present lower bounds on dimension reduction techniques for other /spl lscr//sub p/ norms. Our work suggests that the notion of a stretch-limited embedding, where no distance is stretched by more than a factor d in any dimension, is important to the study of dimension reduction for /spl lscr//sub 1/. We use such stretch limited embeddings as a tool for proving lower bounds for dimension reduction and also as an algorithmic tool for proving positive results.

SODA Conference 2002 Conference Paper

On semidefinite programming relaxations for graph coloring and vertex cover

• Moses Charikar

STOC Conference 2002 Conference Paper

Similarity estimation techniques from rounding algorithms

• Moses Charikar

(MATH) A locality sensitive hashing scheme is a distribution on a family $\F$ of hash functions operating on a collection of objects, such that for two objects x,y , Pr h εF[ h ( x ) = h ( y )] = sim( x,y ), where sim ( x,y ) ε [0,1] is some similarity function defined on the collection of objects. Such a scheme leads to a compact representation of objects so that similarity of objects can be estimated from their compact sketches, and also leads to efficient algorithms for approximate nearest neighbor search and clustering. Min-wise independent permutations provide an elegant construction of such a locality sensitive hashing scheme for a collection of subsets with the set similarity measure sim ( A,B ) = \frac{|A ∩ B|}{|A ∪ B|}.(MATH) We show that rounding algorithms for LPs and SDPs used in the context of approximation algorithms can be viewed as locality sensitive hashing schemes for several interesting collections of objects. Based on this insight, we construct new locality sensitive hashing schemes for: A collection of vectors with the distance between → \over u and → \over v measured by Ø(→ \over u , → \over v )/π, where Ø(→ \over u , → \over v ) is the angle between → \over u ) and → \over v ). This yields a sketching scheme for estimating the cosine similarity measure between two vectors, as well as a simple alternative to minwise independent permutations for estimating set similarity. A collection of distributions on n points in a metric space, with distance between distributions measured by the Earth Mover Distance ( EMD ), (a popular distance measure in graphics and vision). Our hash functions map distributions to points in the metric space such that, for distributions P and Q , EMD ( P,Q ) ≤ E hε\F [ d ( h ( P ), h ( Q ))] ≤ O (log n log log n ). EMD ( P, Q ).

SODA Conference 2001 Conference Paper

Algorithms for facility location problems with outliers

• Moses Charikar
• Samir Khuller
• David M. Mount
• Giri Narasimhan

STOC Conference 2001 Conference Paper

Approximating min-sum k -clustering in metric spaces

• Yair Bartal
• Moses Charikar
• Danny Raz

The min-sum k-clustering problem in a metric space is to find a partition of the space into k clusters as to minimize the total sum of distances between pairs of points assigned to the same cluster. We give the first polynomial time non-trivial approximation algorithm for this problem. The algorithm provides an $\ratio$ approximation to the min-sum k -clustering problem in general metric spaces, with running time $\runtime$. The result is based on embedding of metric spaces into hierarchically separated trees. We also provide a bicriteria approximation result that provides a constant approximation factor solution with only a constant factor increase in the number of clusters. This result is obtained by modifying and drawing ideas from recently developed primal dual approximation algorithms for facility location.

STOC Conference 2001 Conference Paper

Clustering to minimize the sum of cluster diameters

• Moses Charikar
• Rina Panigrahy

We study the problem of clustering points in a metric space so as to minimize the sum of cluster diameters. Significantly improving on previous results, we present a primal-dual based constant factor approximation algorithm for this problem. We present a simple greedy algorithm that achieves a logarithmic approximation which also applies when the distance function is asymmetric. The previous best known result obtained a logarithmic approximation with a constant factor blowup in the number of clusters. We also obtain an incremental clustering algorithm that maintains a solution whose cost is at most a constant factor times that of optimal with a constant factor blowup in the number of clusters.

I&C Journal 2001 Journal Article

Delayed Information and Action in On-Line Algorithms

• Susanne Albers
• Moses Charikar
• Michael Mitzenmacher

Most on-line analysis assumes that, at each time step, all relevant information up to that time step is available and a decision has an immediate effect. In many on-line problems, however, the time when relevant information is available and the time a decision has an effect may be decoupled. For example, when making an investment, one might not have completely up-to-date information on market prices. Similarly, a buy or sell order might only be executed some time in the future. We introduce and explore natural delayed models for several well-known on-line problems. Our analyses demonstrate the importance of considering timeliness in determining the competitive ratio of an on-line algorithm. For many problems, we demonstrate that there exist algorithms with small competitive ratios even when large delays affect the timeliness of information and the effect of decisions.

TCS Journal 2001 Journal Article

On page migration and other relaxed task systems

• Yair Bartal
• Moses Charikar
• Piotr Indyk

This paper is concerned with the page migration (or file migration) problem (Black and Sleator, Technical Report CMU-CS-89-201, Department of Computer Science, Carnegie-Mellon University, 1989) as part of a large class of on-line problems. The page migration problem deals with the management of pages residing in a network of processors. In the classical problem there is only one copy of each page which is accessed by different processors over time. The page is allowed to be migrated between processors. However a migration incurs higher communication cost than an access (proportionally to the page size). The problem is that of deciding when and where to migrate the page in order to lower access costs. A more general setting is the k-page migration problem where we wish to maintain k copies of the page. The page migration problems are concerned with a dilemma common to many on-line problems: determining when it is beneficial to make configuration changes. We deal with the relaxed task systems model which captures a large class of problems of this type, that can be described as the generalization of some original task system problem (Borodin et al. , J. ACM 39(4) (1992) 745–763). Given a c-competitive algorithm for a task system we show how to obtain a deterministic O(c2) and randomized O(c) competitive algorithms for the corresponding relaxed task system. The result implies deterministic algorithms for k-page migration by using k-server (Manasse et al. , J. Algorithms 11(2) (1990) 208–230) algorithms, and for network leasing by using generalized Steiner tree algorithms (Awerbuch et al. , Proc 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, January 1996, pp. 68–74), as well as providing solutions for natural generalizations of other problems (e. g. storage rearrangement (Fiat et al. , Proc. 36th Ann. IEEE Symp. on Foundations of Computer Science, October 1995, pp. 392–403). We further study some special cases of the k-page migration problem and get optimal deterministic algorithms. For the classical page migration problem we present a deterministic algorithm that achieves a competitive ratio of ∼4. 086, improving upon the previously best competitive ratio of 7 (Awerbuch et al. , Proc. 25th ACM Symp. on Theory of Computing, May 1993, pp. 164–173). (The current lower bound on the problem is ∼3. 148 (Chrobak et al. , J. Algorithms 24(1) (1997) 124–157).)

FOCS Conference 2000 Conference Paper

Combinatorial feature selection problems

• Moses Charikar
• Venkatesan Guruswami
• Ravi Kumar 0001
• Sridhar Rajagopalan
• Amit Sahai

Motivated by frequently recurring themes in information retrieval and related disciplines, we define a genre of problems called combinatorial feature selection problems. Given a set S of multidimensional objects, the goal is to select a subset K of relevant dimensions (or features) such that some desired property /spl Pi/ holds for the set S restricted to K. Depending on /spl Pi/, the goal could be to either maximize or minimize the size of the subset K. Several well-studied feature selection problems can be cast in this form. We study the problems in this class derived from several natural and interesting properties /spl Pi/, including variants of the classical p-center problem as well as problems akin to determining the VC-dimension of a set system. Our main contribution is a theoretical framework for studying combinatorial feature selection, providing (in most cases essentially tight) approximation algorithms and hardness results for several instances of these problems.

STOC Conference 2000 Conference Paper

Query strategies for priced information (extended abstract)

• Moses Charikar
• Ronald Fagin
• Venkatesan Guruswami
• Jon M. Kleinberg
• Prabhakar Raghavan
• Amit Sahai

STOC Conference 1999 Conference Paper

A Constant-Factor Approximation Algorithm for the k -Median Problem (Extended Abstract)

• Moses Charikar
• Sudipto Guha
• Éva Tardos
• David B. Shmoys

FOCS Conference 1999 Conference Paper

Improved Combinatorial Algorithms for the Facility Location and k-Median Problems

• Moses Charikar
• Sudipto Guha

We present improved combinatorial approximation algorithms for the uncapacitated facility location and k-median problems. Two central ideas in most of our results are cost scaling and greedy improvement. We present a simple greedy local search algorithm which achieves an approximation ratio of 2. 414+/spl epsiv/ in O/spl tilde/(n/sup 2///spl epsiv/) time. This also yields a bicriteria approximation tradeoff of (1+/spl gamma/, 1+2//spl gamma/) for facility cost versus service cost which is better than previously known tradeoffs and close to the best possible. Combining greedy improvement and cost scaling with a recent primal dual algorithm for facility location due to K. Jain and V. Vazirani (1999), we get an approximation ratio of 1. 853 in O/spl tilde/(n/sup 3/) time. This is already very close to the approximation guarantee of the best known algorithm which is LP-based. Further combined with the best known LP-based algorithm for facility location, we get a very slight improvement in the approximation factor for facility location, achieving 1. 728. We present improved approximation algorithms for capacitated facility location and a variant. We also present a 4-approximation for the k-median problem, using similar ideas, building on the 6-approximation of Jain and Vazirani. The algorithm runs in O/spl tilde/(n/sup 3/) time.

SODA Conference 1999 Conference Paper

Minimizing Wirelength in Zero and Bounded Skew Clock Trees

• Moses Charikar
• Jon M. Kleinberg
• Ravi Kumar 0001
• Sridhar Rajagopalan
• Amit Sahai
• Andrew Tomkins

STOC Conference 1999 Conference Paper

On targeting Markov segments

• Moses Charikar
• Ravi Kumar 0001
• Prabhakar Raghavan
• Sridhar Rajagopalan
• Andrew Tomkins

STOC Conference 1998 Conference Paper

Algorithms for Capacitated Vehicle Routing

• Moses Charikar
• Samir Khuller
• Balaji Raghavachari

FOCS Conference 1998 Conference Paper

Approximating a Finite Metric by a Small Number of Tree Metrics

• Moses Charikar
• Chandra Chekuri
• Ashish Goel
• Sudipto Guha
• Serge A. Plotkin

Y. Bartal (1996, 1998) gave a randomized polynomial time algorithm that given any n point metric G, constructs a tree T such that the expected stretch (distortion) of any edge is at most O (log n log log n). His result has found several applications and in particular has resulted in approximation algorithms for many graph optimization problems. However approximation algorithms based on his result are inherently randomized. In this paper we derandomize the use of Bartal's algorithm in the design of approximation algorithms. We give an efficient polynomial time algorithm that given a finite n point metric G, constructs O(n log n) trees and a probability distribution /spl mu/ on them such that the expected stretch of any edge of G in a tree chosen according to /spl mu/ is at most O(log n log log n). Our result establishes that finite metrics can be probabilistically approximated by a small number of tree metrics. We obtain the first deterministic approximation algorithms for buy-at-bulk network design and vehicle routing; in addition we subsume results from our earlier work on derandomization. Our main result is obtained by a novel view of probabilistic approximation of metric spaces as a deterministic optimization problem via linear programming.

SODA Conference 1998 Conference Paper

Approximation Algorithms for Directed Steiner Problems

• Moses Charikar
• Chandra Chekuri
• To-Yat Cheung
• Zuo Dai
• Ashish Goel
• Sudipto Guha
• Ming Li 0001

FOCS Conference 1998 Conference Paper

Delayed Information and Action in On-line Algorithms

• Susanne Albers
• Moses Charikar
• Michael Mitzenmacher

Most on-line analysis assumes that, at each time-step, all relevant information up to that time step is available and a decision has an immediate effect. In many on-line problems, however, the time relevant information is available and the time a decision has an effect may be decoupled. For example, when making an investment, one might not have completely up-to-date information on market prices. Similarly, a buy or sell order might only be executed some time later in the future. We introduce and explore natural delayed models for several well-known on-line problems. Our analyses demonstrate the importance of considering timeliness in determining the competitive ratio of an on-line algorithm. For many problems, we demonstrate that there exist algorithms with small competitive ratios even when large delays affect the timeliness of information and the effect of decisions.

STOC Conference 1998 Conference Paper

Min-Wise Independent Permutations (Extended Abstract)

• Andrei Z. Broder
• Moses Charikar
• Alan M. Frieze
• Michael Mitzenmacher

STOC Conference 1998 Conference Paper

Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and k -Median

• Moses Charikar
• Chandra Chekuri
• Ashish Goel
• Sudipto Guha

SODA Conference 1998 Conference Paper

The Dynamic Servers Problem

• Moses Charikar
• Dan Halperin
• Rajeev Motwani 0001

FOCS Conference 1998 Conference Paper

The Finite Capacity Dial-A-Ride Problem

• Moses Charikar
• Balaji Raghavachari

We give the first non-trivial approximation algorithm for the Capacitated Dial-a-Ride problem: given a collection of objects located at points in a metric space, a specified destination point for each object, and a vehicle with a capacity of at most k objects, the goal is to compute a shortest tour for the vehicle in which all objects can be delivered to their destinations while ensuring that the vehicle carries at most k objects at any point in time. The problem is known under several names, including the Stacker Crane problem and the Dial-a-Ride problem. No theoretical approximation guarantees were known for this problem other than for the cases k=1, /spl infin/ and the trivial O(k) approximation for general capacity k. We give an algorithm with approximation ratio O(/spl radic/k) for special instances on a class of tree metrics called height-balanced trees. Using Bartal's recent results on the probabilistic approximation of metric spaces by tree metrics, we obtain an approximation ratio of O(/spl radic/k log n log log n) for arbitrary n point metric spaces. When the points lie on a line (line metric), we provide a 2-approximation algorithm. We also consider the Dial-a-Ride problem in another framework: when the vehicle is allowed to leave objects at intermediate locations and pick them up at a later time and deliver them. For this model, we design an approximation algorithm whose performance ratio is O(1) for tree metrics and O(log n log log n) for arbitrary metrics. We also study the ratio between the values of the optimal solutions for the two versions of the problem. We show that unlike in k-delivery TSP in which all the objects are identical, this ratio is not bounded by a constant for the Dial-a-Ride problem, and it could be as large as R(k/sup 2/3/).

STOC Conference 1997 Conference Paper

Incremental Clustering and Dynamic Information Retrieval

• Moses Charikar
• Chandra Chekuri
• Tomás Feder
• Rajeev Motwani 0001

SODA Conference 1997 Conference Paper

On Page Migration and Other Relaxed Task Systems

• Yair Bartal
• Moses Charikar
• Piotr Indyk