The doubling constant of a metric space (X, d) is the smallest value /spl lambda/ such that every ball in X can be covered by balls half radius. dimension then defined as dim (X) = log/sub 2//spl lambda/. A (or sequence metrics) called precisely when its bounded. This robust class spaces which contains many families metrics occur applied settings. We give tight bounds for embedding into (low-dimensional) normed spaces. consider both general metrics, well more restricted those arising from...

We present a simple deterministic data structure for maintaining set S of points in general metric space, while supporting proximity search (nearest neighbor and range queries) updates to (insertions deletions). Our consists sequence progressively finer e-nets S, with pointers that allow us navigate easily from one scale the next.We analyze worst-case complexity this terms abstract dimensionality S. is extremely efficient metrics bounded dimension essentially optimal certain model distance...

We provide the first hardness result of a polylogarithmic approximation ratio for natural NP-hard optimization problem. show that every fixed ε>0, GROUP-STEINER-TREE problem admits no efficient log2-ε k approximation, where denotes number groups (or, alternatively, input size), unless NP has quasi polynomial Las-Vegas algorithms. This holds even graphs which are Hierarchically Well-Separated Trees, introduced by Bartal [FOCS, 1996]. For these trees (and also general trees), our bound is...

We show that the Multicut, Sparsest-Cut, and Min-2CNF ≡ Deletion problems are NP-hard to approximate within every constant factor, assuming Unique Games Conjecture of Khot (2002). A quantitatively stronger version conjecture implies an inapproximability factor $$\Omega(\sqrt{\log \log n}).$$

Alon, Krivelevich, and Sudakov [Random Struct Algorithms 13(3–4) (1998), 457–466.] designed an algorithm based on spectral techniques that almost surely finds a clique of size hidden in otherwise random graph. We show different algorithm, the Lovász theta function, both certifies its optimality. Our has additional advantage being more robust: it also works semirandom model, which adversary can remove edges from portion ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 195–208, 2000

The quest for a polynomial-time approximation scheme (PTAS) Nash equilibrium in two-player game, which emerged as major open question algorithmic game theory, seeks to circumvent the PPAD-completeness of finding an (exact) by approximate equilibrium. closely related problem maximizing certain objective, such social welfare, was shown be NP-hard [Gilboa and Zemel, Games Econom. Behav., 1 (1989), pp. 80–93]. However, this NP-hardness is unlikely extend equilibria, since latter admits...

The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem a randomized polynomial-time algorithm that computes (1+µ)-approximation to optimal tour, any fixed µ>0, in TSP instances form an arbitrary metric space with bounded intrinsic dimension.

In the survivable networkdesign problem (SNDP), goal is to find a minimum-cost spanning subgraph satisfying certain connectivity requirements. We study vertex-connectivity variant of SNDP in which input specifies, for each pair vertices, required number vertex-disjoint paths connecting them. give first strong lower bound on approximability SNDP, showing that admits no efficient $2^{\log^{1-\epsilon} n}$ ratio approximation any fixed $\epsilon\! >\! 0$, unless $\NP\subseteq...

A bisection of a graph with n vertices is partition its into two sets, each size n/2. The cost the number edges connecting sets. It known that finding minimum NP-hard. We present an algorithm finds whose within ratio O(log2n ) from minimum. For graphs excluding any fixed as minor (e.g., planar graphs) we obtain improved approximation O(log n). previously for was roughly $\sqrt{n}$.

A technique introduced by Indyk and Woodruff (STOC 2005) has inspired several recent advances in data-stream algorithms. We show that a number of these results follow eas- ily from the application single probabilistic method called Precision Sampling. Using this method, we obtain simple data- stream algorithms maintain randomized sketch an input vector x = (x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> ,x...

We present a near-linear time algorithm that approximates the edit distance between two strings within polylogarithmic factor. For of length n and every fixed ε >; 0, computes (log n) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(1/ε)</sup> approximation in xmlns:xlink="http://www.w3.org/1999/xlink">1+ε</sup> time. This is an exponential improvement over previously known factor, 2 xmlns:xlink="http://www.w3.org/1999/xlink">Õ</sup>...

Sketching and streaming algorithms are in the forefront of current research directions for cut problems graphs. In model, we show that (1--ε)-approximation Max-Cut must use n{1-O(ε)} space; moreover, beating 4/5-approximation requires polynomial space. For sketching every r-uniform hypergraph admits a (1+ ε)-cut-sparsifier (i.e., weighted subhypergraph approximately preserves all cuts) with O(ε-2n(r+log n)) edges. We also make first steps towards general CSPs (Constraint Satisfaction Problems).

Edit distance has been extensively studied for the past several years. Nevertheless, no linear-time algorithm is known to compute edit between two strings, or even approximate it within a modest factor. Furthermore, various natural algorithmic problems such as low-distortion embeddings into normed spaces, nearest-neighbor schemes, and sketching algorithms, results are rather weak. We develop algorithms that solve gap versions of problem: given strings length n with promise their either at...

We initiate the study of approximate algorithms on negatively curved spaces. These spaces have recently become interest in various domains computer science including networking and vision. The classical example such a space is real-hyperbolic \mathbb{H}^d for d \geqslant 2, but our approach applies to more general family characterized by Gromov's (combinatorial) hyperbolic condition. give efficient data structures problems like nearest-neighbor search compact, low-stretch routing subsets...

We consider the k-balanced partitioning problem, where goal is to partition vertices of an input graph G into k equally sized components, while minimizing total weight edges connecting different components. allow be part and denote cardinality vertex set by n. This problem a natural important generalization well-known problems, including minimum bisection balanced cut.We present (bi-criteria) approximation algorithm achieving O(√log n log k), which matches or improves over previous...

A natural requirement for many distributed structures is fault-tolerance: after some failures in the underlying network, whatever remains from structure should still be effective network. In this paper we examine spanners of general graphs that are tolerant to vertex failures, and significantly improve their dependence on number faults r all stretch bounds.

Estimating the leading principal components of data, assuming they are sparse, is a central task in modern high-dimensional statistics. Many algorithms were developed for this sparse PCA problem, from simple diagonal thresholding to sophisticated semidefinite programming (SDP) methods. A key theoretical question under what conditions can such recover components? We study single-spike model with an $\ell_{0}$-sparse eigenvector, asymptotic regime as dimension $p$ and sample size $n$ both tend...

We undertake a systematic study of sketching quadratic form: given an n x matrix A, create succinct sketch sk(A) which can produce (without further access to A) multiplicative (1+ε)-approximation xT A for any desired query ∈ Rn. While general does not admit non-trivial sketches, positive semi-definite (PSD) matrices sketches size θ(ε{-2 n), via the Johnson-Lindenstrauss lemma, achieving "for each" guarantee, namely, each x, with constant probability succeeds. (For stronger all" where...

Recent advances in large-margin classification of data residing general metric spaces (rather than Hilbert spaces) enable under various natural metrics, such as string edit and earthmover distance. A framework developed for this purpose left open the questions computational efficiency providing direct bounds on generalization error. We design a new algorithm spaces, whose runtime accuracy depend doubling dimension points, can thus achieve superior performance many common scenarios. The...

Lov{ász and Schrijver [SIAM J. Optim., 1 (1991), pp. 166--190] devised a lift-and-project method that produces sequence of convex relaxations for the problem finding in graph an independent set (or clique) maximum size. Each relaxation is tighter than one before it, while first already at least as strong theta function [IEEE Trans. Inform. Theory, 25 (1979), 1--7]. We show on random Gn,1/2 , value rth roughly \rule{0pt}{7pt}$\smash{\sqrt{\rule{0pt}{7pt}\smash{n/2^r}}}$, almost surely. It...

We simplify and improve upon recent lower bounds on the minimum distortion of embedding certain finite metric spaces into l1. In particular, we show that for infinitely many values n there are n-point negative type require a Ω(log log n) such an embedding, implying same bound integrality gap well-known SDP relaxation SPARSEST-CUT. This result builds improves (log n)1/6---o(1) due to Khot Vishnoi [STOC 2005]. also edit distance {O, 1}n L1 requires n). simplifies very Naor [FOCS

The distance to monotonicity of a sequence is the minimum number edit operations required transform into an increasing order; this measure complementary length longest subsequence (LIS). We address question estimating these quantities in one-pass data stream model and present first sub-linear space algorithms for both problems.We O(√n)-space deterministic that approximate LIS within factor arbitrarily close 1. also show lower bound Ω(n) on by any randomized algorithm compute (or...

We show that the MULTICUT, SPARSEST-CUT, and MIN-2CNF/spl equiv/DELETION problems are NP-hard to approximate within every constant factor, assuming unique games conjecture of Khot [STOC, 2002]. A quantitatively stronger version implies inapproximability factor /spl Omega/(log log n).