We present a technique for transforming classical approximation algorithms into constant-time that approximate the size of optimal solution. Our is applicable to certain subclass compute solution in constant number phases. The based on greedily considering local improvements random order.The problems amenable our include Vertex Cover, Maximum Matching, Weight Set and Minimum Dominating Set. For example, we give first algorithm class graphs degree bounded by $d$, computes maximum matching...

We give algorithms for geometric graph problems in the modern parallel models such as MapReduce. For example, Minimum Spanning Tree (MST) problem over a set of points two-dimensional space, our algorithm computes (1 + ε)-approximate MST. Our work constant number rounds communication, while using total space and communication proportional to size data (linear near linear time algorithms). In contrast, general graphs, achieving same result MST (or even connectivity) remains challenging open...

We introduce a new tool for approximation and testing algorithms called partitioning oracles. develop methods constructing them any class of bounded-degree graphs with an excluded minor, in general, hyperfinite graphs. These oracles utilize only local computation to consistently answer queries about global partition that breaks the graph into small connected components by removing fraction edges. illustrate power this technique using it extend simplify number previous results sparse graphs,...

We describe a general method for testing whether function on n input variables has concise representation. The approach combines ideas from the junta test of Fischer et al. 16 with learning theory, and yields property testers that make po!y(s/epsiv) queries (independent n) Boolean classes such as s-term DNF formulas (answering question posed by Parnas [12]), sizes. decision trees, sizes formulas, circuits. can be applied to non-Boolean valued well. This is achieved via generalization notion...

We consider the problem of maintaining a large matching and small vertex cover in dynamically changing graph. Each update to graph is either an edge deletion or insertion. give first randomized data structure that simultaneously achieves constant approximation factor handles sequence K updates K*polylog(n) time, where n number vertices Previous structures require polynomial amount computation per update.

We give near-optimal sketching and streaming algorithms for estimating Shannon entropy in the most general model, with arbitrary insertions deletions. This improves on prior results that obtain suboptimal space bounds insertion-only model without sketching. Our high-level approach is simple: we to estimate Tsallis entropy, use them extrapolate an of entropy. The accuracy our estimates proven using approximation theory arguments extremal properties Chebyshev polynomials. work also yields...

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>...

For over a decade now we have been witnessing the success of massive parallel computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One reasons for their is fact that these frameworks are able to accurately capture nature large-scale computation. In particular, compared classic distributed algorithms PRAM models, allow much more local The fundamental question arises in this context though: can leverage additional power obtain even faster algorithms?

We give a nearly optimal sublinear-time algorithm for approximating the size of minimum vertex cover in graph G. The may query degree deg(v) any v its choice, and each 1 ≤ i deg(v), it ask ith neighbor v. Letting VCopt(G) denote G, outputs, with high constant success probability, an estimate [EQUATION] such that [EQUATION], where e is given additive approximation parameter. refer to as (2, e)-estimate. complexity running time are O([EQUATION] · poly(1/e)), d denotes average graph. best...

A maximal independent set (MIS) can be maintained in an evolving m-edge graph by simply recomputing it from scratch O(m) time after each update. But sublinear m fully dynamic graphs?

We study the fair variant of classic $k$-median problem introduced by Chierichetti et al. [2017]. In standard problem, given an input pointset $P$, goal is to find $k$ centers $C$ and assign each point one in such that average distance points their cluster center minimized. $k$-median, are colored, minimize same objective while ensuring all clusters have "approximately equal" number color. proposed a two-phase algorithm for $k$-clustering. first step, partitioned into subsets called fairlets...

We show how to compute the edit distance between two strings of length $n$ up a factor $2^{\tilde{O}(\sqrt{\log n})}$ in $n^{1+o(1)}$ time. This is first subpolynomial approximation algorithm for this problem that runs near-linear time, improving on state-of-the-art $n^{1/3+o(1)}$ approximation. Previously, was known only embedding into $\ell_1$, and it not if can be computed less than quadratic

We prove n^(1+Omega(1/p))/p^O(1) lower bounds for the space complexity of p-pass streaming algorithms solving following problems on n-vertex graphs: * testing if an undirected graph has a perfect matching (this implies computing maximum or even just size), two specific vertices are at distance most 2(p+1) in graph, there is directed path from s to t and graph. Prior our result, it was known that these require Omega(n^2) one pass, but no n^(1+Omega(1)) bound any p>=2. These results follow...

We show how to compute the edit distance between two strings of length n up a factor 2(O-tilde(sqrt(log n))) in n(1+o(1)) time. This is first sub-polynomial approximation algorithm for this problem that runs near-linear time, improving on state-of-the-art n(1/3+o(1)) approximation. Previously, 2O √log n) was known only embedding into l1, and it not if can be computed less than quadratic

We consider the problem of estimating size a maximum matching when edges are revealed in streaming fashion. When input graph is planar, we present simple and elegant algorithm that with high probability estimates within constant factor using [EQUATION](n2/3) space, where n number vertices. The approach generalizes to family graphs have bounded arboricity, which include an excluded constant-size minor. To best our knowledge, this first result for adversarial-order model (as opposed...

We extend the binary search technique to searching in trees. consider two models of queries: questions about vertices and edges. present a general approach this sort problem, apply it both cases, achieving algorithms constructing optimal decision In edge query model problem is identical special class tree-like posets stated by Ben-Asher et al. (1999). Our upper bound on computation time, O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3...

The first fully dynamic algorithm for maintaining a maximal independent set (MIS) with update time that is sublinear in the number of edges was presented recently by authors this paper [Assadi et al., STOC'18]. deterministic and its O(m3/4), where m (dynamically changing) edges. Subsequently, Gupta Khan independently Du Zhang [arXiv, April 2018] algorithms MIS times O(m2/3) [MATH HERE], respectively. also gave randomized HERE]. Moreover, they provided some partial (conditional) hardness...

We give a nearly optimal sublinear-time algorithm for approximating the size of minimum vertex cover in graph G. The may query degree deg(v) any v its choice, and each 1 < i deg(v), it ask ith neighbor v. Letting VCopt (G) denote G, outputs, with high constant success probability, an estimate such that , where ∊ is given additive approximation parameter. refer to as (2, ∊)-estimate. complexity running time are Õ( · poly(1/ε)), denotes average graph. best previously known sublinear algorithm,...

We introduce a hierarchical partitioning scheme of the Euclidean plane, called circular partitions. Such partition consists hierarchy convex polygons, each having small aspect ratio, and satisfying specified volume constraints. apply these partitions to obtain natural extension popular Treemap visualization method. Our proposed algorithm is not constrained in using only rectangles, can achieve provably better guarantees on ratio constructed polygons.

Previous chapter Next Full AccessProceedings Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Streaming for Estimating Matching Size in Planar Graphs and BeyondHossein Esfandiari, Mohammad T Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, Krzysztof OnakHossein Onakpp.1217 - 1233Chapter DOI:https://doi.org/10.1137/1.9781611973730.81PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We consider problem estimating size...