Strategy improvement is a natural and well-studied family of algorithms for solving various classes of stochastic and deterministic graph games. We present an improved upper bound of O(n 2ⁿ) on the number of iterations performed by the most natural, and most greedy, variant of the algorithm when applied to n-vertex Energy Games. We also obtain a similar upper bound of O(poly(n)⋅ 2ⁿ) on the expected number of iterations performed by Random-Edge, one of the most natural randomized variants of the algorithm. To the best of our knowledge, these are the first bounds for natural strategy-improvement algorithms on non-binary energy games that beat the trivial nⁿ = 2^{n log n} bound obtained by enumerating all strategies. The proof is based on a new adaptation of the layering technique of [Dorfman, Kaplan, Zwick, ICALP 2019].

We introduce a streaming model that uses both catalytic and regular memory. In this model, we show how to exactly compute the frequency moments using a logarithmic number of bits of regular memory and a polynomial number of bits of catalytic memory. More generally, we show how to compute arbitrary polynomials of the item frequencies exactly within the same space bounds. As an application, we obtain catalytic streaming algorithms that exactly compute the number of distinct elements in a stream, count the number of triangles (or any other small subgraph) in a graph whose edges arrive in a stream, and identify heavy hitters. Our algorithms for frequency moments perform a constant number of passes over the stream, and for polynomial evaluation, we require one more pass than the degree of the polynomial. In particular, for the second moment, we perform three passes over the stream. By relating our catalytic streaming model to the catalytic communication model introduced in [Pyne et al., 2025], we show that catalytic memory is not useful for any one pass streaming algorithms. For lower bounds on multi pass streaming algorithms, the impossibility results of [Pyne et al., 2025] are not strong enough. However, using a different technique, we show that computing the second frequency moment cannot be achieved by a two pass catalytic streaming algorithm that satisfies certain natural assumptions.

A tree cut-sparsifier T of quality α of a graph G is a single tree that preserves the capacities of all cuts in the graph up to a factor of α. A tree flow-sparsifier T of quality α guarantees that every demand that can be routed in T can also be routed in G with congestion at most α. We present a near-linear time algorithm that, for any undirected capacitated graph G = (V,E,c), constructs a tree cut-sparsifier T of quality O(log² n log log n), where n = |V|. This nearly matches the quality of the best known polynomial construction of a tree cut-sparsifier, of quality O(log^{1.5} n log log n) [Räcke and Shah, ESA 2014]. By the flow-cut gap, our result yields a tree flow-sparsifier (and congestion-approximator) of quality O(log³ n log log n). This improves on the celebrated result of [Räcke, Shah, and Täubig, SODA 2014] (RST) that gave a near-linear time construction of a tree flow-sparsifier of quality O(log⁴ n). Our algorithm builds on a recent expander decomposition algorithm by [Agassy, Dorfman, and Kaplan, ICALP 2023], which we use as a black box to obtain a clean and modular foundation for tree cut-sparsifiers. This yields an improved and simplified version of the RST construction for cut-sparsifiers with quality O(log³ n). We then introduce a near-linear time refinement phase that controls the load accumulated on boundary edges of the sub-clusters across the levels of the tree. Combining the improved framework with this refinement phase leads to our final O(log² n log log n) tree cut-sparsifier.

We introduce a new Bayesian perspective on the concept of data reconstruction, and leverage this viewpoint to propose a new security definition that, in certain settings, provably prevents reconstruction attacks. We use our paradigm to shed new light on one of the most notorious attacks in the privacy and memorization literature - fingerprinting code attacks (FPC). We argue that these attacks are really a form of membership inference attacks, rather than reconstruction attacks. Furthermore, we show that if the goal is solely to prevent reconstruction (but not membership inference), then in some cases the impossibility results derived from FPC no longer apply.

We revisit the classical problem of minimizing the total flow time of jobs on a single machine in the online setting where jobs arrive over time. It has long been known that the Shortest Remaining Processing Time (SRPT) algorithm is optimal (i.e., 1-competitive) when the job sizes are known upfront [Schrage, 1968]. But in the non-clairvoyant setting where job sizes are revealed only when the job finishes, no algorithm can be constant-competitive [Motwani, Phillips, and Torng, 1994]. We consider the $\varepsilon$-clairvoyant setting, where $\varepsilon \in[0,1]$, and each job’s processing time becomes known once its remaining processing time equals an $\varepsilon$ fraction of its processing time. This captures settings where the system user uses the initial $(1-\varepsilon)$ fraction of a job’s processing time to learn its true length, which it can then reveal to the algorithm. The model was proposed by Yingchareonthawornchai and Torng (2017), and it smoothly interpolates between the clairvoyant setting (when $\varepsilon=1$) and the non-clairvoyant setting (when $\varepsilon=0$). In a concrete sense, we are asking: how much knowledge is required to circumvent the hardness of this problem? We show that a little knowledge is enough, and that a constant competitive algorithm exists for every constant $\varepsilon\gt 0$. More precisely, for all $\varepsilon \in(0,1)$, we present a deterministic $\left\lceil\frac{1}{\varepsilon}\right\rceil$-competitive algorithm, which is optimal for deterministic algorithms. We also present a matching lower bound (up to a constant factor) for randomized algorithms. Our algorithm to achieve this bound is remarkably simple and applies the “optimism in the face of uncertainty” principle. For each job, we form an optimistic estimate of its length, based on the information revealed thus far and run SRPT on these optimistic estimates. The proof relies on maintaining a matching between the jobs in OPT’s queue and the algorithm’s queue, with small prefix expansion. We achieve this by carefully choosing a set of jobs to arrive earlier than their release times without changing the algorithm, and possibly helping the adversary. These early arrivals allow us to maintain structural properties inductively, giving us the tight guarantee.

We present a randomized Õ(n^{3.5})-time algorithm for computing optimal energetic paths for an electric car between all pairs of vertices in an n-vertex directed graph with positive and negative costs, or gains, which are defined to be the negatives of the costs. The optimal energetic paths are finite and well-defined even if the graph contains negative-cost, or equivalently, positive-gain, cycles. This makes the problem much more challenging than standard shortest paths problems. More specifically, for every two vertices s and t in the graph, the algorithm computes α_B(s,t), the maximum amount of charge the car can reach t with, if it starts at s with full battery, i.e., with charge B, where B is the capacity of the battery. The algorithm also outputs a concise description of the optimal energetic paths that achieve these values. In the presence of positive-gain cycles, optimal paths are not necessarily simple. For dense graphs, our new Õ(n^{3.5}) time algorithm improves on a previous Õ(mn²)-time algorithm of Dorfman et al. [ESA 2023] for the problem. The gain of an arc is the amount of charge added to the battery of the car when traversing the arc. The charge in the battery can never exceed the capacity B of the battery and can never be negative. An arc of positive gain may correspond, for example, to a downhill road segment, while an arc with a negative gain may correspond to an uphill segment. A positive-gain cycle, if one exists, can be used in certain cases to charge the battery to its capacity. This makes the problem more interesting and more challenging. As mentioned, optimal energetic paths are well-defined even in the presence of positive-gain cycles. Positive-gain cycles may arise when certain road segments have magnetic charging strips, or when the electric car has solar panels. Combined with a result of Dorfman et al. [SOSA 2024], this also provides a randomized Õ(n^{3.5})-time algorithm for computing minimum-cost paths between all pairs of vertices in an n-vertex graph when the battery can be externally recharged, at varying costs, at intermediate vertices.

We investigate Learning from Label Proportions (LLP), a partial information setting where examples in a training set are grouped into bags, and only aggregate label values in each bag are available. Despite the partial observability, the goal is still to achieve small regret at the level of individual examples. We give results on the sample complexity of LLP under square loss, showing that our sample complexity is essentially optimal. From an algorithmic viewpoint, we rely on carefully designed variants of Empirical Risk Minimization, and Stochastic Gradient Descent algorithms, combined with ad hoc variance reduction techniques. On one hand, our theoretical results improve in important ways on the existing literature on LLP, specifically in the way the sample complexity depends on the bag size. On the other hand, we validate our algorithmic solutions on several datasets, demonstrating improved empirical performance (better accuracy for less samples) against recent baselines.

We revisit the fundamental question of formally defining what constitutes a reconstruction attack. While often clear from the context, our exploration reveals that a precise definition is much more nuanced than it appears, to the extent that a single all-encompassing definition may not exist. Thus, we employ a different strategy and aim to "sandwich" the concept of reconstruction attacks by addressing two complementing questions: (i) What conditions guarantee that a given system is protected against such attacks? (ii) Under what circumstances does a given attack clearly indicate that a system is not protected? More specifically, * We introduce a new definitional paradigm -- Narcissus Resiliency -- to formulate a security definition for protection against reconstruction attacks. This paradigm has a self-referential nature that enables it to circumvent shortcomings of previously studied notions of security. Furthermore, as a side-effect, we demonstrate that Narcissus resiliency captures as special cases multiple well-studied concepts including differential privacy and other security notions of one-way functions and encryption schemes. * We formulate a link between reconstruction attacks and Kolmogorov complexity. This allows us to put forward a criterion for evaluating when such attacks are convincingly successful.

In the private set union problem each user owns a bag of at most $k$ items (from some large universe of items), and we are interested in computing the union of the items in the bags of all of the users. This is trivial without privacy, but a differentially private algorithm must be careful about reporting items contained in only a small number of bags. We consider differentially private algorithms that always report a subset of the union, and define the utility of an algorithm to be the expected size of the subset that it reports. Because the achievable utility varies significantly with the dataset, we introduce the *utility ratio*, which normalizes utility by a dataset-specific upper bound and characterizes a mechanism by its lowest normalized utility across all datasets. We then develop algorithms with guaranteed utility ratios and complement them with bounds on the best possible utility ratio. Prior work has shown that a single algorithm can be simultaneously optimal for all datasets when $k=1$, but we show that instance-optimal algorithms do not exist when $k>1$, and characterize how performance degrades as $k$ grows. At the same time, we design a private algorithm that achieves the maximum possible utility, regardless of $k$, when the item histogram matches a prior prediction (for instance, from a previous data release) and degrades gracefully with the $L_\infty$ distance between the prediction and the actual histogram when the prediction is imperfect.

Motivated by the desire to utilize a limited number of configurable optical switches by recent advances in Software Defined Networks (SDNs), we define an online problem which we call the Caching in Matchings problem. This problem has a natural combinatorial structure and therefore may find additional applications in theory and practice. In the Caching in Matchings problem our cache consists of $k$ matchings of connections between servers that form a bipartite graph. To cache a connection we insert it into one of the $k$ matchings possibly evicting at most two other connections from this matching. This problem resembles the problem known as Connection Caching, where we also cache connections but our only restriction is that they form a graph with bounded degree $k$. Our results show a somewhat surprising qualitative separation between the problems: The competitive ratio of any online algorithm for caching in matchings must depend on the size of the graph. Specifically, we give a deterministic $O(nk)$ competitive and randomized $O(n \log k)$ competitive algorithms for caching in matchings, where $n$ is the number of servers and $k$ is the number of matchings. We also show that the competitive ratio of any deterministic algorithm is $Ω(\max(\frac{n}{k},k))$ and of any randomized algorithm is $Ω(\log \frac{n}{k^2 \log k} \cdot \log k)$. In particular, the lower bound for randomized algorithms is $Ω(\log n)$ regardless of $k$, and can be as high as $Ω(\log^2 n)$ if $k=n^{1/3}$, for example. We also show that if we allow the algorithm to use at least $2k-1$ matchings compared to $k$ used by the optimum then we match the competitive ratios of connection catching which are independent of $n$. Interestingly, we also show that even a single extra matching for the algorithm allows to get substantially better bounds.

Recent advances in algorithmic design show how to utilize predictions obtained by machine learning models from past and present data. These approaches have demonstrated an enhancement in performance when the predictions are accurate, while also ensuring robustness by providing worst-case guarantees when predictions fail. In this paper we focus on online problems; prior research in this context was focused on a paradigm where the algorithms are oblivious of the predictors' design, treating them as a black box. In contrast, in this work, we unpack the predictor and integrate the learning problem it gives rise for within the algorithmic challenge. In particular we allow the predictor to learn as it receives larger parts of the input, with the ultimate goal of designing online learning algorithms specifically tailored for the algorithmic task at hand. Adopting this perspective, we focus on a number of fundamental problems, including caching and scheduling, which have been well-studied in the black-box setting. For each of the problems, we introduce new algorithms that take advantage of explicit and carefully designed learning rules. These pairings of online algorithms with corresponding learning rules yields improvements in the overall performance in comparison with previous work.

Abstract Let $$S \subseteq \mathbb {R}^2$$ S ⊆ R 2 be a set of nsites in the plane, so that every site $$s \in S$$ s ∈ S has an associated radius $$r_s > 0$$ r s > 0 . Let $$\mathcal {D}(S)$$ D ( S ) be the disk intersection graph defined by S, i.e., the graph with vertex set S and an edge between two distinct sites $$s, t \in S$$ s , t ∈ S if and only if the disks with centers s, t and radii $$r_s$$ r s , $$r_t$$ r t intersect. Our goal is to design data structures that maintain the connectivity structure of $$\mathcal {D}(S)$$ D ( S ) as sites are inserted and/or deleted in S. First, we consider unit disk graphs, i.e., we fix $$r_s = 1$$ r s = 1 , for all sites $$s \in S$$ s ∈ S . For this case, we describe a data structure that has $$O(\log ^2 n)$$ O ( log 2 n ) amortized update time and $$O(\log n/\log \log n)$$ O ( log n / log log n ) query time. Second, we look at disk graphs with bounded radius ratio $$\Psi $$ Ψ , i.e., for all $$s \in S$$ s ∈ S , we have $$1 \le r_s \le \Psi $$ 1 ≤ r s ≤ Ψ , for a parameter $$\Psi $$ Ψ that is known in advance. Here, we not only investigate the fully dynamic case, but also the incremental and the decremental scenario, where only insertions or only deletions of sites are allowed. In the fully dynamic case, we achieve amortized expected update time $$O(\Psi \log ^{4} n)$$ O ( Ψ log 4 n ) and query time $$O(\log n/\log \log n)$$ O ( log n / log log n ) . This improves the currently best update time by a factor of $$\Psi $$ Ψ . In the incremental case, we achieve logarithmic dependency on $$\Psi $$

We present a general technique, based on parametric search with some twist, for solving a variety of optimization problems on a set of semi-algebraic geometric objects of constant complexity. The common feature of these problems is that they involve a `growth parameter' $r$ and a semi-algebraic predicate $Π(o,o';r)$ of constant complexity on pairs of input objects, which depends on $r$ and is monotone in $r$. One then defines a graph $G(r)$ whose edges are all the pairs $(o,o')$ for which $Π(o,o';r)$ is true, and seeks the smallest value of $r$ for which some monotone property holds for $G(r)$. Problems that fit into this context include (i) the reverse shortest path problem in unit-disk graphs, recently studied by Wang and Zhao, (ii) the same problem for weighted unit-disk graphs, with a decision procedure recently provided by Wang and Xue, (iii) extensions of these problems to three and higher dimensions, (iv) the discrete Fréchet distance with one-sided shortcuts in higher dimensions, extending the study by Ben Avraham et al., (v) perfect matchings in intersection graphs: given, e.g., a set of fat ellipses of roughly the same size, find the smallest value $r$ such that if we expand each of the ellipses by $r$, the resulting intersection graph contains a perfect matching, (vi) generalized distance selection problems: given, e.g., a set of disjoint segments, find the $k$'th smallest distance among the pairwise distances determined by the segments, for a given (sufficiently small but superlinear) parameter $k$, and (vii) the maximum-height independent towers problem, in which we want to erect vertical towers of maximum height over a 1.5-dimensional terrain so that no pair of tower tips are mutually visible. We obtain significantly improved solutions for problems (i), (ii) and (vi), and new efficient solutions to the other problems.

A $(ϕ,ε)$-expander-decomposition of a graph $G$ (with $n$ vertices and $m$ edges) is a partition of $V$ into clusters $V_1,\ldots,V_k$ with conductance $Φ(G[V_i]) \ge ϕ$, such that there are at most $εm$ inter-cluster edges. Such a decomposition plays a crucial role in many graph algorithms. We give a randomized $\tilde{O}(m/ϕ)$ time algorithm for computing a $(ϕ, ϕ\log^2 {n})$-expander decomposition. This improves upon the $(ϕ, ϕ\log^3 {n})$-expander decomposition also obtained in $\tilde{O}(m/ϕ)$ time by [Saranurak and Wang, SODA 2019] (SW) and brings the number of inter-cluster edges within logarithmic factor of optimal. One crucial component of SW's algorithm is non-stop version of the cut-matching game of [Khandekar, Rao, Vazirani, JACM 2009] (KRV): The cut player does not stop when it gets from the matching player an unbalanced sparse cut, but continues to play on a trimmed part of the large side. The crux of our improvement is the design of a non-stop version of the cleverer cut player of [Orecchia, Schulman, Vazirani, Vishnoi, STOC 2008] (OSVV). The cut player of OSSV uses a more sophisticated random walk, a subtle potential function, and spectral arguments. Designing and analysing a non-stop version of this game was an explicit open question asked by SW.

Search trees on trees (STTs) generalize the fundamental binary search tree (BST) data structure: in STTs the underlying search space is an arbitrary tree, whereas in BSTs it is a path. An optimal BST of size $n$ can be computed for a given distribution of queries in $O(n^2)$ time [Knuth 1971] and centroid BSTs provide a nearly-optimal alternative, computable in $O(n)$ time [Mehlhorn 1977]. By contrast, optimal STTs are not known to be computable in polynomial time, and the fastest constant-approximation algorithm runs in $O(n^3)$ time [Berendsohn, Kozma 2022]. Centroid trees can be defined for STTs analogously to BSTs, and they have been used in a wide range of algorithmic applications. In the unweighted case (i.e., for a uniform distribution of queries), a centroid tree can be computed in $O(n)$ time [Brodal et al. 2001; Della Giustina et al. 2019]. These algorithms, however, do not readily extend to the weighted case. Moreover, no approximation guarantees were previously known for centroid trees in either the unweighted or weighted cases. In this paper we revisit centroid trees in a general, weighted setting, and we settle both the algorithmic complexity of constructing them, and the quality of their approximation. For constructing a weighted centroid tree, we give an output-sensitive $O(n\log h)\subseteq O(n\log n)$ time algorithm, where $h$ is the height of the resulting centroid tree. If the weights are of polynomial complexity, the running time is $O(n\log\log n)$. We show these bounds to be optimal, in a general decision tree model of computation. For approximation, we prove that the cost of a centroid tree is at most twice the optimum, and this guarantee is best possible, both in the weighted and unweighted cases. We also give tight, fine-grained bounds on the approximation-ratio for bounded-degree trees and on the approximation-ratio of more general $α$-centroid trees.

We introduce the concurrent shuffle model of differential privacy. In this model we have multiple concurrent shufflers permuting messages from different, possibly overlapping, batches of users. Similarly to the standard (single) shuffler model, the privacy requirement is that the concatenation of all shuffled messages should be differentially private. We study the private continual summation problem (a.k.a. the counter problem) and show that the concurrent shuffle model allows for significantly improved error compared to a standard (single) shuffler model. Specifically, we give a summation algorithm with error $\tilde{O}(n^{1/(2k+1)})$ with $k$ concurrent shufflers on a sequence of length $n$. Furthermore, we prove that this bound is tight for any $k$, even if the algorithm can choose the sizes of the batches adaptively. For $k=\log n$ shufflers, the resulting error is polylogarithmic, much better than $\tilde{\Theta}(n^{1/3})$ which we show is the smallest possible with a single shuffler. We use our online summation algorithm to get algorithms with improved regret bounds for the contextual linear bandit problem. In particular we get optimal $\tilde{O}(\sqrt{n})$ regret with $k= \tilde{\Omega}(\log n)$ concurrent shufflers.

In this work we revisit an interactive variant of joint differential privacy, recently introduced by Naor et al. [2023], and generalize it towards handling online processes in which existing privacy definitions seem too restrictive. We study basic properties of this definition and demonstrate that it satisfies (suitable variants) of group privacy, composition, and post processing. In order to demonstrate the advantages of this privacy definition compared to traditional forms of differential privacy, we consider the basic setting of online classification. We show that any (possibly non-private) learning rule can be effectively transformed to a private learning rule with only a polynomial overhead in the mistake bound. This demonstrates a stark difference with traditional forms of differential privacy, such as the one studied by Golowich and Livni [2021], where only a double exponential overhead in the mistake bound is known (via an information theoretic upper bound).

We study the online facility location problem with uniform facility costs in the random-order model. Meyerson's algorithm [FOCS'01] is arguably the most natural and simple online algorithm for the problem with several advantages and appealing properties. Its analysis in the random-order model is one of the cornerstones of random-order analysis beyond the secretary problem. Meyerson's algorithm was shown to be (asymptotically) optimal in the standard worst-case adversarial-order model and 8-competitive in the random order model. While this bound in the random-order model is the long-standing state-of-the-art, it is not known to be tight, and the true competitive-ratio of Meyerson's algorithm remained an open question for more than two decades. We resolve this question and prove tight bounds on the competitive-ratio of Meyerson's algorithm in the random-order model, showing that it is exactly 4-competitive. Following our tight analysis, we introduce a generic parameterized version of Meyerson's algorithm that retains all the advantages of the original version. We show that the best algorithm in this family is exactly 3-competitive. On the other hand, we show that no online algorithm for this problem can achieve a competitive-ratio better than 2. Finally, we prove that the algorithms in this family are robust to partial adversarial arrival orders.

Binary search trees (BSTs) are one of the most basic and widely used data structures. The best static tree for serving a sequence of queries (searches) can be computed by dynamic programming. In contrast, when the BSTs are allowed to be dynamic (i.e. change by rotations between searches), we still do not know how to compute the optimal algorithm (OPT) for a given sequence. One of the candidate algorithms whose serving cost is suspected to be optimal up-to a (multiplicative) constant factor is known by the name Greedy Future (GF). In an equivalent geometric way of representing queries on BSTs, GF is in fact equivalent to another algorithm called Geometric Greedy (GG). Most of the results on GF are obtained using the geometric model and the study of GG. Despite this intensive recent fruitful research, the best lower bound we have on the competitive ratio of GF is 4/3. Furthermore, it has been conjectured that the additive gap between the cost of GF and OPT is only linear in the number of queries. In this paper we prove a lower bound of 2 on the competitive ratio of GF, and we prove that the additive gap between the cost of GF and OPT can be Ω(m ⋅ log log n) where n is the number of items in the tree and m is the number of queries.

Traffic splitting is a required functionality in networks, for example for load balancing over multiple paths or among different servers. The capacities of the servers determine the partition by which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power consuming and are also required for other tasks such as classification and routing. Previous work showed how to compute the smallest prefix-matching TCAM necessary to implement a given partition exactly. In this paper we solve the more practical case, where at most${n}$prefix-matching TCAM rules are available, restricting the ability to implement exactly the desired partition. We consider the$L_{1}$distance between partitions, which is of interest when overloaded requests are simply dropped, and we want to minimize the total loss. We prove that the Niagara algorithm (Kang et al., 2015) can be used to find the closest partition in$L_{1}$to the desired partition, that can be realized with${n}$TCAM rules. Moreover, we prove it for arbitrary partitions, with (possibly) non-integer parts. We also include a short discussion on similarities and differences to previous work which studies the same problem but for$L_{\infty }$distances.

The amount of training-data is one of the key factors which determines the generalization capacity of learning algorithms. Intuitively, one expects the error rate to decrease as the amount of training-data increases. Perhaps surprisingly, natural attempts to formalize this intuition give rise to interesting and challenging mathematical questions. For example, in their classical book on pattern recognition, Devroye, Gyorfi and Lugosi (1996) ask whether there exists a {monotone} Bayes-consistent algorithm.This question remained open for over 25 years, until recently Pestov (2021) resolved it for binary classification, using an intricate construction of a monotone Bayes-consistent algorithm. We derive a general result in multiclass classification, showing that every learning algorithm $A$ can be transformed to a monotone one with similar performance. Further, the transformation is efficient and only uses a black-box oracle access to $A$. This demonstrates that one can provably avoid non-monotonic behaviour without compromising performance, thus answering questions asked by Devroye, Gyorfi, and Lugosi (1996), Viering, Mey, and Loog (2019), Viering and Loog (2021), and by Mhammedi (2021). Our general transformation readily implies monotone learners in a variety of contexts: for example, Pestov’s result follows by applying it on \emph{any} Bayes-consistent algorithm (e.g., $k$-Nearest-Neighbours). In fact, our transformation extends Pestov’s result to classification tasks with an arbitrary number of labels. This is contrast with Pestov’s work which is tailored to binary classification. In addition, we provide uniform bounds on the error of the monotone algorithm. This makes our transformation applicable in distribution-free settings. For example, in PAC learning it implies that every learnable class admits a monotone PAC learner. This resolves questions asked by Viering, Mey, and Loog (2019); Viering and Loog (2021); Mhammedi (2021)

In this work we study the problem of differentially private (DP) quantiles, in which given dataset $X$ and quantiles $q_1, ..., q_m \in [0,1]$, we want to output $m$ quantile estimations which are as close as possible to the true quantiles and preserve DP. We describe a simple recursive DP algorithm, which we call Approximate Quantiles (AQ), for this task. We give a worst case upper bound on its error, and show that its error is much lower than of previous implementations on several different datasets. Furthermore, it gets this low error while running time two orders of magnitude faster that the best previous implementation.

Differentially private algorithms for common metric aggregation tasks, such as clustering or averaging, often have limited practicality due to their complexity or to the large number of data points that is required for accurate results. We propose a simple and practical tool $\mathsf{FriendlyCore}$ that takes a set of points ${\cal D}$ from an unrestricted (pseudo) metric space as input. When ${\cal D}$ has effective diameter $r$, $\mathsf{FriendlyCore}$ returns a “stable” subset ${\cal C} \subseteq {\cal D}$ that includes all points, except possibly few outliers, and is guaranteed to have diameter $r$. $\mathsf{FriendlyCore}$ can be used to preprocess the input before privately aggregating it, potentially simplifying the aggregation or boosting its accuracy. Surprisingly, $\mathsf{FriendlyCore}$ is light-weight with no dependence on the dimension. We empirically demonstrate its advantages in boosting the accuracy of mean estimation and clustering tasks such as $k$-means and $k$-GMM, outperforming tailored methods.

Traffic splitting is a required functionality in networks, for example for load balancing over multiple paths or among different servers. The capacities of the servers determine the partition by which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power consuming and are also required for other tasks such as classification and routing. Previous work showed how to compute the smallest prefix-matching TCAM necessary to implement a given partition exactly. In this paper we solve the more practical case, where at most n prefix-matching TCAM rules are available, restricting the ability to implement exactly the desired partition. We consider the L1distance between partitions, which is of interest when overloaded requests are simply dropped, and we want to minimize the total loss. We prove that the Niagara algorithm [1] can be used to find the closest partition in L1to the desired partition, that can be realized with n TCAM rules. Moreover, we prove it for arbitrary partitions, with (possibly) non-integer parts.

Traffic splitting is a required functionality in networks, for example for load balancing over paths or servers, or by the source’s access restrictions. The capacities of the servers (or the number of users with particular access restrictions) determine the sizes of the parts into which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power consuming. We analyze the expected size of a representation, for uniformly random ordered partitions. We show that the expected representation size of a random partition is at least half the size for the worst-case partition, and is linear in the number of parts and in the logarithm of the size of the address space.

We study the greedy-based online algorithm for edge-weighted matching with (one-sided) vertex arrivals in bipartite graphs, and edge arrivals in general graphs. This algorithm was first studied more than a decade ago by Korula and Pál for the bipartite case in the random-order model. While the weighted bipartite matching problem is solved in the random-order model, this is not the case in recent and exciting online models in which the online player is provided with a sample, and the arrival order is adversarial. The greedy-based algorithm is arguably the most natural and practical algorithm to be applied in these models. Despite its simplicity and appeal, and despite being studied in multiple works, the greedy-based algorithm was not fully understood in any of the studied online models, and its actual performance remained an open question for more than a decade. We provide a thorough analysis of the greedy-based algorithm in several online models. For vertex arrivals in bipartite graphs, we characterize the exact competitive-ratio of this algorithm in the random-order model, for any arrival order of the vertices subsequent to the sampling phase (adversarial and random orders in particular). We use it to derive tight analysis in the recent adversarial-order model with a sample (AOS model) for any sample size, providing the first result in this model beyond the simple secretary problem. Then, we generalize and strengthen the black box method of converting results in the random-order model to single-sample prophet inequalities, and use it to derive the state-of-the-art single-sample prophet inequality for the problem. Finally, we use our new techniques to analyze the greedy-based algorithm for edge arrivals in general graphs and derive results in all the mentioned online models. In this case as well, we improve upon the state-of-the-art single-sample prophet inequality.

It is well known that a queue can be simulated by two stacks using a constant number of stack operations per queue operation. In this paper we consider the forgotten converse problem of simulating a stack using several queues. We consider several variants of this problem. For the offline variant, we obtain a tight upper and lower bounds for the worst-case number of queue operations needed to simulate a sequence of n stack operations using k queues. For the online variant, when the number of queues k is constant, and n is the maximum number of items in the stack at any given time, we obtain tight Θ(n1/k) upper and lower bounds on the worst-case and amortized number of queue operations needed to simulate one stack operation. When k is allowed to grow with n, we prove an upper bound of O(n1/k + logk n) and a lower bound of on the amortized number of queue operations per stack operation. We also prove an upper bound of O(kn1/k) and a lower bound of Ω(n1/k + logk n) on the worst-case number of queue operations per stack operation. We also show that the specific but interesting sequence of n pushes followed by n pops can be implemented much faster using a total number of only Θ(n logk n) queue operations, for every k ≥ 2, an amortized number of Θ(logk n) queue operations per stack operation, and this bound is tight. On the other hand, we show that the same sequence requires at least Ω(n1/k) queue operations per stack operation in the worst case.

Given an input that undergoes a sequence of updates, a dynamic algorithm maintains a valid solution to some predefined problem at any point in time; the goal is to design an algorithm in which computing a solution to the updated input is done more efficiently than computing the solution from scratch. A dynamic algorithm against an adaptive adversary is required to be correct when the adversary chooses the next update after seeing the previous outputs of the algorithm. We obtain faster dynamic algorithms against an adaptive adversary and separation results between what is achievable in the oblivious vs. adaptive settings. To get these results we exploit techniques from differential privacy, cryptography, and adaptive data analysis. Our results are as follows.

A streaming algorithm is said to be adversarially robust if its accuracy guarantees are maintained even when the data stream is chosen maliciously, by an adaptive adversary . We establish a connection between adversarial robustness of streaming algorithms and the notion of differential privacy . This connection allows us to design new adversarially robust streaming algorithms that outperform the current state-of-the-art constructions for many interesting regimes of parameters.

We present efficient differentially private algorithms for learning unions of polygons in the plane (which are not necessarily convex). Our algorithms are $(\alpha,\beta)$--probably approximately correct and $(\varepsilon,\delta)$--differentially private using a sample of size $\tilde{O}\left(\frac{1}{\alpha\varepsilon}k\log d\right)$, where the domain is $[d]\times[d]$ and $k$ is the number of edges in the union of polygons. Our algorithms are obtained by designing a private variant of the classical (nonprivate) learner for conjunctions using the greedy algorithm for set cover.

Traffic splitting is a required functionality in networks, for example for load balancing over multiple paths or among different servers. The capacities of the servers determine the partition by which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power consuming and are often also required for other tasks such as classification and routing. Previous work showed how to compute the smallest prefix-matching TCAM necessary to implement a given partition exactly. In this paper we solve the more practical case, where at most$n$prefix-matching TCAM rules are available, restricting the ability to implement exactly the desired partition. We give simple and efficient algorithms to find$n$rules that generate a partition closest in$L_\infty $to the desired one. We do the same for a one-sided version of$L_\infty $which equals to the maximum overload on a server and for a relative version of it. We use our algorithms to evaluate how the expected error changes as a function of the number of rules, the number of servers, and the width of the TCAM.

We study a novel variant of online finite-horizon Markov Decision Processes with adversarially changing loss functions and initially unknown dynamics. In each episode, the learner suffers the loss accumulated along the trajectory realized by the policy chosen for the episode, and observes aggregate bandit feedback: the trajectory is revealed along with the cumulative loss suffered, rather than the individual losses encountered along the trajectory. Our main result is a computationally efficient algorithm with $O(\sqrt{K})$ regret for this setting, where K is the number of episodes. We establish this result via an efficient reduction to a novel bandit learning setting we call Distorted Linear Bandits (DLB), which is a variant of bandit linear optimization where actions chosen by the learner are adversarially distorted before they are committed. We then develop a computationally-efficient online algorithm for DLB for which we prove an $O(\sqrt{T})$ regret bound, where T is the number of time steps. Our algorithm is based on online mirror descent with a self-concordant barrier regularization that employs a novel increasing learning rate schedule.

We revisit one of the most basic and widely applicable techniques in the literature of differential privacy – the sparse vector technique [Dwork et al., STOC 2009]. This simple algorithm privately tests whether the value of a given query on a database is close to what we expect it to be. It allows to ask an unbounded number of queries as long as the answer is close to what we expect, and halts following the first query for which this is not the case. We suggest an alternative, equally simple, algorithm that can continue testing queries as long as any single individual does not contribute to the answer of too many queries whose answer deviates substantially form what we expect. Our analysis is subtle and some of its ingredients may be more widely applicable. In some cases our new algorithm allows to privately extract much more information from the database than the original. We demonstrate this by applying our algorithm to the shifting-heavy-hitters problem: On every time step, each of n users gets a new input, and the task is to privately identify all the current heavy-hitters. That is, on time step i, the goal is to identify all data elements x such that many of the users have x as their current input. We present an algorithm for this problem with improved error guarantees over what can be obtained using existing techniques. Specifically, the error of our algorithm depends on the maximal number of times that a single user holds a heavy-hitter as input, rather than the total number of times in which a heavy-hitter exists.

Clustering is a fundamental problem in data analysis. In differentially private clustering, the goal is to identify k cluster centers without disclosing information on individual data points. Despite significant research progress, the problem had so far resisted practical solutions. In this work we aim at providing simple implementable differentrially private clustering algorithms when the the data is "easy," e.g., when there exists a significant separation between the clusters. For the easy instances we consider, we have a simple implementation based on utilizing non-private clustering algorithms, and combining them privately. We are able to get improved sample complexity bounds in some cases of Gaussian mixtures and k-means. We complement our theoretical algorithms with experiments of simulated data.

We give an $(\varepsilon,\delta)$-differentially private algorithm for the Multi-Armed Bandit (MAB) problem in the shuffle model with a distribution-dependent regret of $O\left(\left(\sum_{a:\Delta_a>0}\frac{\log T}{\Delta_a}\right)+\frac{k\sqrt{\log\frac{1}{\delta}}\log T}{\varepsilon}\right)$, and a distribution-independent regret of $O\left(\sqrt{kT\log T}+\frac{k\sqrt{\log\frac{1}{\delta}}\log T}{\varepsilon}\right)$, where $T$ is the number of rounds, $\Delta_a$ is the suboptimality gap of the action $a$, and $k$ is the total number of actions. Our upper bound almost matches the regret of the best known algorithms for the centralized model, and significantly outperforms the best known algorithm in the local model.

Locality Sensitive Hashing (LSH) is an effective method of indexing a set of items to support efficient nearest neighbors queries in high-dimensional spaces. The basic idea of LSH is that similar items should produce hash collisions with higher probability than dissimilar items. We study LSH for (not necessarily convex) polygons, and use it to give efficient data structures for similar shape retrieval. Arkin et al. [Arkin et al., 1991] represent polygons by their "turning function" - a function which follows the angle between the polygon’s tangent and the x-axis while traversing the perimeter of the polygon. They define the distance between polygons to be variations of the L_p (for p = 1,2) distance between their turning functions. This metric is invariant under translation, rotation and scaling (and the selection of the initial point on the perimeter) and therefore models well the intuitive notion of shape resemblance. We develop and analyze LSH near neighbor data structures for several variations of the L_p distance for functions (for p = 1,2). By applying our schemes to the turning functions of a collection of polygons we obtain efficient near neighbor LSH-based structures for polygons. To tune our structures to turning functions of polygons, we prove some new properties of these turning functions that may be of independent interest. As part of our analysis, we address the following problem which is of independent interest. Find the vertical translation of a function f that is closest in L₁ distance to a function g. We prove tight bounds on the approximation guarantee obtained by the translation which is equal to the difference between the averages of g and f.

We present an explicit and efficient construction of additively weighted Voronoi diagrams on planar graphs. Let $G$ be a planar graph with $n$ vertices and $b$ sites that lie on a constant number of faces. We show how to preprocess $G$ in $\tilde O(nb^2)$ time so that one can compute any additively weighted Voronoi diagram for these sites in $\tilde O(b)$ time. We use this construction to compute the diameter of a directed planar graph with real arc lengths in $\tilde{O}(n^{5/3})$ time. This improves the recent breakthrough result of Cabello [ SODA 2017, SIAM, Philadelphia, 2017, pp. 2143--2152], both by improving the running time (from $\tilde{O}(n^{11/6})$), and by providing a deterministic algorithm. It is in fact the first truly subquadratic deterministic algorithm for this problem. Our use of Voronoi diagrams to compute the diameter follows that of Cabello, but he used abstract Voronoi diagrams, which makes his diameter algorithm more involved, more expensive, and randomized. As in Cabello's work, our algorithm can compute, for every vertex $v$, both the farthest vertex from $v$ (i.e., the eccentricity of $v$), and the sum of distances from $v$ to all other vertices. Hence, our algorithm can also compute the radius, median, and Wiener index (sum of all pairwise distances) of a planar graph within the same time bounds. Our construction of Voronoi diagrams for planar graphs is of independent interest.

We consider the applications of the Frank-Wolfe (FW) algorithm for Apprenticeship Learning (AL). In this setting, we are given a Markov Decision Process (MDP) without an explicit reward function. Instead, we observe an expert that acts according to some policy, and the goal is to find a policy whose feature expectations are closest to those of the expert policy. We formulate this problem as finding the projection of the feature expectations of the expert on the feature expectations polytope – the convex hull of the feature expectations of all the deterministic policies in the MDP. We show that this formulation is equivalent to the AL objective and that solving this problem using the FW algorithm is equivalent well-known Projection method of Abbeel and Ng (2004). This insight allows us to analyze AL with tools from convex optimization literature and derive tighter convergence bounds on AL. Specifically, we show that a variation of the FW method that is based on taking “away steps” achieves a linear rate of convergence when applied to AL and that a stochastic version of the FW algorithm can be used to avoid precise estimation of feature expectations. We also experimentally show that this version outperforms the FW baseline. To the best of our knowledge, this is the first work that shows linear convergence rates for AL.

We study the Thompson sampling algorithm in an adversarial setting, specifically, for adversarial bit prediction. We characterize the bit sequences with the smallest and largest expected regret. Among sequences of length $T$ with $k < \frac{T}{2}$ zeros, the sequences of largest regret consist of alternating zeros and ones followed by the remaining ones, and the sequence of smallest regret consists of ones followed by zeros. We also bound the regret of those sequences, the worst case sequences have regret $O(\sqrt{T})$ and the best case sequence have regret $O(1)$. We extend our results to a model where false positive and false negative errors have different weights. We characterize the sequences with largest expected regret in this generalized setting, and derive their regret bounds. We also show that there are sequences with $O(1)$ regret.

We consider a setting of hierarchical reinforcement learning, in which the reward is a sum of components. For each component, we are given a policy that maximizes it, and our goal is to assemble a policy from the individual policies that maximize the sum of the components. We provide theoretical guarantees for assembling such policies in deterministic MDPs with collectible rewards. Our approach builds on formulating this problem as a traveling salesman problem with a discounted reward. We focus on local solutions, i.e., policies that only use information from the current state; thus, they are easy to implement and do not require substantial computational resources. We propose three local stochastic policies and prove that they guarantee better performance than any deterministic local policy in the worst case; experimental results suggest that they also perform better on average.

We study the sample complexity of learning threshold functions under the constraint of differential privacy. It is assumed that each labeled example in the training data is the information of one individual and we would like to come up with a generalizing hypothesis $h$ while guaranteeing differential privacy for the individuals. Intuitively, this means that any single labeled example in the training data should not have a significant effect on the choice of the hypothesis. This problem has received much attention recently; unlike the non-private case, where the sample complexity is independent of the domain size and just depends on the desired accuracy and confidence, for private learning the sample complexity must depend on the domain size $X$ (even for approximate differential privacy). Alon et al. (STOC 2019) showed a lower bound of $\Omega(\log^*|X|)$ on the sample complexity and Bun et al. (FOCS 2015) presented an approximate-private learner with sample complexity $\tilde{O}\left(2^{\log^*|X|}\right)$. In this work we reduce this gap significantly, almost settling the sample complexity. We first present a new upper bound (algorithm) of $\tilde{O}\left(\left(\log^*|X|\right)^2\right)$ on the sample complexity and then present an improved version with sample complexity $\tilde{O}\left(\left(\log^*|X|\right)^{1.5}\right)$. Our algorithm is constructed for the related interior point problem, where the goal is to find a point between the largest and smallest input elements. It is based on selecting an input-dependent hash function and using it to embed the database into a domain whose size is reduced logarithmically; this results in a new database, an interior point of which can be used to generate an interior point of the original database in a differentially private manner.

We study the question of how to compute a point in the convex hull of an input set $S$ of $n$ points in ${\mathbb R}^d$ in a differentially private manner. This question, which is trivial non-privately, turns out to be quite deep when imposing differential privacy. In particular, it is known that the input points must reside on a fixed finite subset $G\subseteq{\mathbb R}^d$, and furthermore, the size of $S$ must grow with the size of $G$. Previous works focused on understanding how $n$ needs to grow with $|G|$, and showed that $n=O\left(d^{2.5}\cdot8^{\log^*|G|}\right)$ suffices (so $n$ does not have to grow significantly with $|G|$). However, the available constructions exhibit running time at least $|G|^{d^2}$, where typically $|G|=X^d$ for some (large) discretization parameter $X$, so the running time is in fact $Ω(X^{d^3})$. In this paper we give a differentially private algorithm that runs in $O(n^d)$ time, assuming that $n=Ω(d^4\log X)$. To get this result we study and exploit some structural properties of the Tukey levels (the regions $D_{\ge k}$ consisting of points whose Tukey depth is at least $k$, for $k=0,1,...$). In particular, we derive lower bounds on their volumes for point sets $S$ in general position, and develop a rather subtle mechanism for handling point sets $S$ in degenerate position (where the deep Tukey regions have zero volume). A naive approach to the construction of the Tukey regions requires $n^{O(d^2)}$ time. To reduce the cost to $O(n^d)$, we use an approximation scheme for estimating the volumes of the Tukey regions (within their affine spans in case of degeneracy), and for sampling a point from such a region, a scheme that is based on the volume estimation framework of Lovász and Vempala (FOCS 2003) and of Cousins and Vempala (STOC 2015). Making this framework differentially private raises a set of technical challenges that we address.

Traffic splitting is a required functionality in networks, for example for load balancing over multiple paths or among different servers. The capacities of the servers determine the partition by which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power consuming and are often also required for other tasks such as classification and routing. Previous work showed how to compute the smallest TCAM necessary to implement a given partition exactly. In this paper we solve the more practical case, where at most n TCAM rules are available, restricting the ability to implement the desired partition. We give simple and efficient algorithms to find n rules that generate a partition closest in L∞ to the desired one. We do the same for a one-sided version of L∞ which equals to the maximum overload on a server and for a relative version of it. We use our algorithms to evaluate how the expected error changes as a function of the number of rules, the number of servers, and the width of the TCAM.

Stochastic shortest path (SSP) is a well-known problem in planning and control, in which an agent has to reach a goal state in minimum total expected cost. In the learning formulation of the problem, the agent is unaware of the environment dynamics (i.e., the transition function) and has to repeatedly play for a given number of episodes, while learning the problem’s optimal solution. Unlike other well-studied models in reinforcement learning (RL), the length of an episode is not predetermined (or bounded) and is influenced by the agent’s actions. Recently, \cite{tarbouriech2019noregret} studied this problem in the context of regret minimization, and provided an algorithm whose regret bound is inversely proportional to the square root of the minimum instantaneous cost. In this work we remove this dependence on the minimum cost—we give an algorithm that guarantees a regret bound of $\widetilde{O}(B^{3/2} S \sqrt{A K})$, where $B$ is an upper bound on the expected cost of the optimal policy, $S$ is the number of states, $A$ is the number of actions and $K$ is the total number of episodes. We additionally show that any learning algorithm must have at least $\Omega(B \sqrt{S A K})$ regret in the worst case.

Graph datasets with billions of edges, such as social and Web graphs, are prevalent, and scalable computation is critical. All-distances sketches (ADS) [Cohen 1997], are a powerful tool for scalable approximation of statistics. The sketch is a small size sample of the distance relation of a node which emphasizes closer nodes. Sketches for all nodes are computed using a nearly linear computation and estimators are applied to sketches of nodes to estimate their properties. We provide, for the first time, a unified exposition of ADS algorithms and applications. We present the Historic Inverse Probability (HIP) estimators which are applied to the ADS of a node to estimate a large natural class of statistics. For the important special cases of neighborhood cardinalities (the number of nodes within some query distance) and closeness centralities, HIP estimators have at most half the variance of previous estimators and we show that this is essentially optimal. Moreover, HIP obtains a polynomial improvement for more general statistics and the estimators are simple, flexible, unbiased, and elegant. For approximate distinct counting on data streams, HIP outperforms the original estimators for the HyperLogLog MinHash sketches (Flajolet et al. 2007), obtaining significantly improved estimation quality for this state-of-the-art practical algorithm.

A streaming algorithm is said to be adversarially robust if its accuracy guarantees are maintained even when the data stream is chosen maliciously, by an adaptive adversary. We establish a connection between adversarial robustness of streaming algorithms and the notion of differential privacy. This connection allows us to design new adversarially robust streaming algorithms that outperform the current state-of-the-art constructions for many interesting regimes of parameters.

We present a differentially private learner for halfspaces over a finite grid $G$ in $\R^d$ with sample complexity $\approx d^{2.5}\cdot 2^{\log^*|G|}$, which improves the state-of-the-art result of [Beimel et al., COLT 2019] by a $d^2$ factor. The building block for our learner is a new differentially private algorithm for approximately solving the linear feasibility problem: Given a feasible collection of $m$ linear constraints of the form $Ax\geq b$, the task is to {\em privately} identify a solution $x$ that satisfies {\em most} of the constraints. Our algorithm is iterative, where each iteration determines the next coordinate of the constructed solution $x$.

Abstract. We extend the standard online worst-case model to accommodate past experience which is available to the online player in many practical scenarios. We do this by revealing a random sample of the adversarial input to the online player ahead of time. The online player competes with the expected optimal value on the part of the input that arrives online. Our model bridges between existing online stochastic models (e.g., items are drawn i.i.d. from a distribution) and the online worst-case model. We also extend in a similar manner (by revealing a sample) the online random-order model. We study the classical secretary problem in our new models. In the worst-case model we present a simple online algorithm with optimal competitive-ratio for any sample size. In the random-order model, we also give a simple online algorithm with an almost tight competitive-ratio for small sample sizes. Interestingly, we prove that for a large enough sample, no algorithm can be simultaneously optimal in both the worst-case and random-order models.

We derive and analyze learning algorithms for apprenticeship learning, policy evaluation and policy gradient for average reward criteria. Existing algorithms explicitly require an upper bound on the mixing time. In contrast, we build on ideas from Markov chain theory and derive sampling algorithms that do not require such an upper bound. For these algorithms, we provide theoretical bounds on their sample-complexity and running time.

Abstract We describe a new data structure for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions. These include $$L_p$$ L p -norms and additively weighted Euclidean distances. Our data structure supports general (convex, pairwise disjoint) sites that have constant description complexity (e.g., points, line segments, disks, etc.). Our structure uses $$O(n \log ^3 n)$$ O ( n log 3 n ) storage, and requires polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat, and Sharir which required $$O(n^{\varepsilon })$$ O ( n ε ) time for an update and $$O(\log n)$$ O ( log n ) time for a query [SICOMP 1999]. Our data structure has numerous applications. In all of them, it gives faster algorithms, typically reducing an $$O(n^{\varepsilon })$$ O ( n ε ) factor in the previous bounds to polylogarithmic. In addition, we give here two new applications: an efficient construction of a spanner in a disk intersection graph, and a data structure for efficient connectivity queries in a dynamic disk graph. To obtain this data structure, we combine and extend various techniques from the literature. Along the way, we obtain several side results that are of independent interest. Our data structure depends on the existence and an efficient construction of “vertical” shallow cuttings in arrangements of bivariate algebraic functions. We prove that an appropriate level in an arrangement of a random sample of a suitable size provides such a cutting. To compute it efficiently, we develop a randomized incremental construction algorithm for computing the lowest k levels in an arrangement of bivariate algebraic functions (we mostly consider here collections of functions whose lower envelope has linear complexity, as is the case in the dynamic nearest-neighbor context, under both types of norm). To analyze this algorithm, we also improve a longstanding bound on the combinatorial complexity of the vertical decomposition of these levels. Finally, to obtain our structure, we combine our vertical shallow cutting construction with Chan’s algorithm for efficiently maintaining the lower envelope of a dynamic set of planes in $${{\mathbb {R}}}^3$$ R 3 . Along the way, we also revisit Chan’s technique and present a variant that uses a single binary counter, with a simpler analysis and improved amortized deletion time (by a logarithmic factor; the insertion and query costs remain asymptotically the same).

We study the problem of clustering the vertices of a weighted hypergraph such that on average the vertices of each edge can be covered by a small number of clusters. This problem has many applications, such as for designing medical tests, clustering files on disk servers, and placing network services on servers. The edges of the hypergraph model groups of items that are likely to be needed together, and the optimization criteria that we use can be interpreted as the average delay (or cost) to serve the items of a typical edge. We describe and analyze algorithms for this problem for the case in which the clusters have to be disjoint and for the case where clusters can overlap. The analysis is often subtle and reveals interesting structure and invariants that one can utilize.

Traffic splitting is a required functionality in networks, for example for load balancing over multiple paths or among different servers. The capacity of each server or path implies the distribution by which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power hungry and are often also required for other tasks such as classification and routing. For splitting a universe of 2Waddresses into k pieces of particular sizes, we give a simple algorithm that computes an optimal representation in O(W k) time. Furthermore, we prove that a recently published load balancer, called Niagara, which runs in O(W k log k) time is in fact optimal. That is, both our algorithm and Niagara produce the smallest possible TCAM that splits the traffic exactly to the required pieces, where the only previously known algorithm for computing optimal exact representation has running time exponential in k. Finally, we use these optimal algorithms to experimentally study the number of TCAM rules required to split traffic in typical scenarios.

We consider the classical camera pose estimation problem that arises in many computer vision applications, in which we are given n 2D-3D correspondences between points in the scene and points in the camera image (some of which are incorrect associations), and where we aim to determine the camera pose (the position and orientation of the camera in the scene) from this data. We demonstrate that this posing problem can be reduced to the problem of computing ε-approximate incidences between two-dimensional surfaces (derived from the input correspondences) and points (on a grid) in a four-dimensional pose space. Similar reductions can be applied to other camera pose problems, as well as to similar problems in related application areas. We describe and analyze three techniques for solving the resulting ε-approximate incidences problem in the context of our camera posing application. The first is a straightforward assignment of surfaces to the cells of a grid (of side-length ε) that they intersect. The second is a variant of a primal-dual technique, recently introduced by a subset of the authors [2] for different (and simpler) applications. The third is a non-trivial generalization of a data structure Fonseca and Mount [3], originally designed for the case of hyperplanes. We present and analyze this technique in full generality, and then apply it to the camera posing problem at hand. We compare our methods experimentally on real and synthetic data. Our experiments show that for the typical values of n and ε, the primal-dual method is the fastest, also in practice.

Let $S \subset \mathbb{R}^2$ be a set of $n$ sites, where each $s \in S$ has an associated radius $r_s > 0$. The disk graph $D(S)$ is the undirected graph with vertex set $S$ and an undirected edge between two sites $s, t \in S$ if and only if $|st| \leq r_s + r_t$, i.e., if the disks with centers $s$ and $t$ and respective radii $r_s$ and $r_t$ intersect. Disk graphs are used to model sensor networks. Similarly, the transmission graph $T(S)$ is the directed graph with vertex set $S$ and a directed edge from a site $s$ to a site $t$ if and only if $|st| \leq r_s$, i.e., if $t$ lies in the disk with center $s$ and radius $r_s$. We provide algorithms for detecting (directed) triangles and, more generally, computing the length of a shortest cycle (the girth) in $D(S)$ and in $T(S)$. These problems are notoriously hard in general, but better solutions exist for special graph classes such as planar graphs. We obtain similarly efficient results for disk graphs and for transmission graphs. More precisely, we show that a shortest (Euclidean) triangle in $D(S)$ and in $T(S)$ can be found in $O(n \log n)$ expected time, and that the (weighted) girth of $D(S)$ can be found in $O(n \log n)$ expected time. For this, we develop new tools for batched range searching that may be of independent interest.

We study the computational complexity of solving mean payoff games. This class of games can be seen as an extension of parity games, and they have similar complexity status: in both cases solving them is in NP ∩ coNP and not known to be in P. In a breakthrough result Calude, Jain, Khoussainov, Li, and Stephan constructed in 2017 a quasipolynomial time algorithm for solving parity games, which was quickly followed by a few other algorithms with the same complexity. Our objective is to investigate how these techniques can be extended to mean payoff games. The starting point is the combinatorial notion of universal trees: all quasipolynomial time algorithms for parity games have been shown to exploit universal trees. Universal graphs extend universal trees to arbitrary (positionally determined) objectives. We show that they yield a family of value iteration algorithms for solving mean payoff games which includes the value iteration algorithm due to Brim, Chaloupka, Doyen, Gentilini, and Raskin. The contribution of this paper is to prove tight bounds on the complexity of algorithms for mean payoff games using universal graphs. We consider two parameters: the largest weight N in absolute value and the number k of weights. The dependence in N in the existing value iteration algorithm is linear, we show that this can be improved to N^{1 - 1/n} and obtain a matching lower bound. However, we show that we cannot break the linear dependence in the exponent in the number k of weights implying that universal graphs do not yield a quasipolynomial time algorithm for solving mean payoff games.

We present differentially private efficient algorithms for learning union of polygons in the plane (which are not necessarily convex). Our algorithms achieve $(\alpha,\beta)$-PAC learning and $(\epsilon,\delta)$-differential privacy using a sample of size $\tilde{O}\left(\frac{1}{\alpha\epsilon}k\log d\right)$, where the domain is $[d]\times[d]$ and $k$ is the number of edges in the union of polygons.

Traffic splitting is a required functionality in networks, for example for load balancing over multiple paths or among different servers. The capacity of each server or path implies the distribution by which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power hungry and are often also required for other tasks such as classification and routing. For splitting a universe of 2Waddresses into k pieces of particular sizes, we give a simple algorithm that computes an optimal representation in Õ(Wk) time. Furthermore, we prove that a recently published load balancer, called Niagara, which also runs in Õ(W k) time is in fact optimal. That is, both our algorithm and Niagara produce the smallest possible TCAM that splits the traffic exactly to the required pieces, where the only previously known algorithm for computing optimal exact representation has running time exponential in k. Finally, we rely on our optimal Õ(Wk) runtime algorithm to investigate through extensive experiments the amount of TCAM memory required to represent traffic splitting in typical scenarios.

Imagine a large firm with multiple departments that plans a large recruitment. Candidates arrive one-by-one, and for each candidate the firm decides, based on her data (CV, skills, experience, etc), whether to summon her for an interview. The firm wants to recruit the best candidates while minimizing the number of interviews. We model such scenarios as an assignment problem between items (candidates) and categories (departments): the items arrive one-by-one in an online manner, and upon processing each item the algorithm decides, based on its value and the categories it can be matched with, whether to retain or discard it (this decision is irrevocable). The goal is to retain as few items as possible while guaranteeing that the set of retained items contains an optimal matching. We consider two variants of this problem: (i) in the first variant it is assumed that the $n$ items are drawn independently from an unknown distribution $D$. (ii) In the second variant it is assumed that before the process starts, the algorithm has an access to a training set of $n$ items drawn independently from the same unknown distribution (e.g.\ data of candidates from previous recruitment seasons). We give tight bounds on the minimum possible number of retained items in each of these variants. These results demonstrate that one can retain exponentially less items in the second variant (with the training set). Our algorithms and analysis utilize ideas and techniques from statistical learning theory and from discrete algorithms.

We describe an efficient deterministic adversary that forces any comparison-based sorting algorithm to perform at least n log n comparisons. This improves on previous efficient adversaries of Atallah and Kosaraju (1981), Richards and Vaidya (1988), and of Brodal et al. (1996) that force any sorting algorithm to perform at least ψn log n comparisons.

The PPSZ algorithm, due to Paturi, Pudlak, Saks and Zane, is currently the fastest known algorithm for the k-SAT problem, for every k>3. For 3-SAT, a tiny improvement over PPSZ was obtained by Hertli. We introduce a biased version of the PPSZ algorithm using which we obtain an improvement over PPSZ for every k≥ 3. For k=3 we also improve on Herli’s result and get a much more noticeable improvement over PPSZ, though still relatively small. In particular, for Unique 3-SAT, we improve the current bound from 1.308n to 1.307n.

Let P be a set of n points in the plane in general position, and consider the problem of finding an axis-parallel rectangle with a given perimeter, or area, or diagonal, that encloses the maximum number of points of P . We present an exact algorithm that finds such a rectangle in O ( n 5 / 2 log ⁡ n ) time, and, for the case of a fixed perimeter or diagonal, we also obtain (i) an improved exact algorithm that runs in O ( n k 3 / 2 log ⁡ k ) time, and (ii) an approximation algorithm that finds, in O ( n + n k ε 5 log 5 / 2 ⁡ n k log ⁡ ( 1 ε log ⁡ n k ) ) time, a rectangle of the given perimeter that contains at least ( 1 − ε ) k points of P , where k is the optimum value. We then show how to turn this algorithm into one that finds, for a given k , an axis-parallel rectangle of smallest perimeter (or area, or diagonal) that contains k points of P . We obtain the first subcubic algorithms for these problems, significantly improving the current state of the art.

We describe a way of assigning labels to the vertices of any undirected graph on up to $n$ vertices, each composed of $n/2+O(1)$ bits, such that given the labels of two vertices, and no other information regarding the graph, it is possible to decide whether or not the vertices are adjacent in the graph. This is optimal, up to an additive constant, and constitutes the first improvement in almost 50 years of an $n/2+O(\log n)$ bound of Moon. As a consequence, we obtain an induced-universal graph for $n$-vertex graphs containing only $O(2^{n/2})$ vertices, which is optimal up to a multiplicative constant, solving an open problem of Vizing from 1968. We obtain similar tight results for directed graphs, tournaments, and bipartite graphs.

Clustering of data points is a fundamental tool in data analysis. We consider points X in a relaxed metric space, where the triangle inequality holds within a constant factor. A clustering of X is a partition of X defined by a set of points Q(centroids), according to the closest centroid. The cost of clustering X by Q is V(Q)= ∑x ∈ X dxQ. This formulation generalizes classic k-means clustering, which uses squared distances. Two basic tasks, parametrized by k ≥ 1, are cost estimation, which returns (approximate) V(Q) for queries Q such that |Q| = k and clustering, which returns an (approximate) minimizer of V(Q) of size |Q|= k. When the data set X is very large, we seek efficient constructions of small samples that can act as surrogates for performing these tasks. Existing constructions that provide quality guarantees, however, are either worst-case, and unable to benefit from structure of real data sets, or make explicit strong assumptions on the structure. We show here how to avoid both these pitfalls using adaptive designs. The core of our design are the novel one2all probabilities, computed for a set M of centroids and α ≥ 1: The clustering cost of each Q with cost V(Q) ≥ V(M)/α can be estimated well from a sample of size O(α |M| ε-2). For cost estimation, we apply one2all with a bicriteria approximate M, while adaptively balancing |M| and α to optimize sample size per quality. For clustering, we present a wrapper that adaptively applies a base clustering algorithm to a sample S, using the smallest sample that provides the desired statistical guarantees on quality. We demonstrate experimentally the huge gains of using our adaptive instead of worst-case methods.

We revisit multipass pairing heaps and path-balanced binary search trees (BSTs), two classical algorithms for data structure maintenance. The pairing heap is a simple and efficient "self-adjusting" heap, introduced in 1986 by Fredman, Sedgewick, Sleator, and Tarjan. In the multipass variant (one of the original pairing heap variants described by Fredman et al.) the minimum item is extracted via repeated pairing rounds in which neighboring siblings are linked. Path-balanced BSTs, proposed by Sleator (Subramanian, 1996), are a natural alternative to Splay trees (Sleator and Tarjan, 1983). In a path-balanced BST, whenever an item is accessed, the search path leading to that item is re-arranged into a balanced tree. Despite their simplicity, both algorithms turned out to be difficult to analyse. Fredman et al. showed that operations in multipass pairing heaps take amortized $O(\log{n} \cdot \log\log{n} / \log\log\log{n})$ time. For searching in path-balanced BSTs, Balasubramanian and Raman showed in 1995 the same amortized time bound of $O(\log{n} \cdot \log\log{n} / \log\log\log{n})$, using a different argument. In this paper we show an explicit connection between the two algorithms and improve the two bounds to $O\left(\log{n} \cdot 2^{\log^{\ast}{n}} \cdot \log^{\ast}{n}\right)$, respectively $O\left(\log{n} \cdot 2^{\log^{\ast}{n}} \cdot (\log^{\ast}{n})^2 \right)$, where $\log^{\ast}(\cdot)$ denotes the very slowly growing iterated logarithm function. These are the first improvements in more than three, resp. two decades, approaching in both cases the information-theoretic lower bound of $Ω(\log{n})$.

Let T={triangle_1,...,triangle_n} be a set of of n pairwise-disjoint triangles in R^3, and let B be a convex polytope in R^3 with a constant number of faces. For each i, let C_i = triangle_i oplus r_i B denote the Minkowski sum of triangle_i with a copy of B scaled by r_i>0. We show that if the scaling factors r_1, ..., r_n are chosen randomly then the expected complexity of the union of C_1, ..., C_n is O(n^{2+epsilon), for any epsilon > 0; the constant of proportionality depends on epsilon and the complexity of B. The worst-case bound can be Theta(n^3). We also consider a special case of this problem in which T is a set of points in R^3 and B is a unit cube in R^3, i.e., each C_i is a cube of side-length 2r_i. We show that if the scaling factors are chosen randomly then the expected complexity of the union of the cubes is O(n log^2 n), and it improves to O(n log n) if the scaling factors are chosen randomly from a "well-behaved" probability density function (pdf). We also extend the latter results to higher dimensions. For any fixed odd value of d, we show that the expected complexity of the union of the hypercubes is O(n^floor[d/2] log n) and the bound improves to O(n^floor[d/2]) if the scaling factors are chosen from a "well-behaved" pdf. The worst-case bounds are Theta(n^2) in R^3, and Theta(n^{ceil[d/2]}) in higher dimensions.

Our goal is to compare two planar point sets by finding subsets of a given size such that a minimum-weight matching between them has the smallest weight. This can be done by a translation of one set that minimizes the weight of the matching. We give efficient algorithms (a) for finding approximately optimal matchings, when the cost of a matching is the L_p-norm of the tuple of the Euclidean distances between the pairs of matched points, for any p in [1,infty], and (b) for constructing small-size approximate minimization (or matching) diagrams: partitions of the translation space into regions, together with an approximate optimal matching for each region.

Suppose we are given a set D of n pairwise intersecting disks in the plane. A planar point set P stabs D if and only if each disk in D contains at least one point from P. We present a deterministic algorithm that takes O(n) time to find five points that stab D. Furthermore, we give a simple example of 13 pairwise intersecting disks that cannot be stabbed by three points. This provides a simple - albeit slightly weaker - algorithmic version of a classical result by Danzer that such a set D can always be stabbed by four points.

The pairing heap is a classical heap data structure introduced in 1986 by Fredman, Sedgewick, Sleator, and Tarjan. It is remarkable both for its simplicity and for its excellent performance in practice. The "magic" of pairing heaps lies in the restructuring that happens after the deletion of the smallest item. The resulting collection of trees is consolidated in two rounds: a left-to-right pairing round, followed by a right-to-left accumulation round. Fredman et al. showed, via an elegant correspondence to splay trees, that in a pairing heap of size n all heap operations take O(log n) amortized time. They also proposed an arguably more natural variant, where both pairing and accumulation are performed in a combined left-to-right round (called the forward variant of pairing heaps). The analogy to splaying breaks down in this case, and the analysis of the forward variant was left open. In this paper we show that inserting an item and deleting the minimum in a forward-variant pairing heap both take amortized time O(log(n) * 4^(sqrt(log n))). This is the first improvement over the O(sqrt(n)) bound showed by Fredman et al. three decades ago. Our analysis relies on a new potential function that tracks parent-child rank-differences in the heap.

We design new differentially private algorithms for the Euclidean k-means problem, both in the centralized model and in the local model of differential privacy. In both models, our algorithms achieve significantly improved error guarantees than the previous state-of-the-art. In addition, in the local model, our algorithm significantly reduces the number of interaction rounds. Although the problem has been widely studied in the context of differential privacy, all of the existing constructions achieve only super constant approximation factors. We present, for the first time, efficient private algorithms for the problem with constant multiplicative error. Furthermore, we show how to modify our algorithms so they compute private coresets for k-means clustering in both models.

In the Prophet Secretary problem, samples from a known set of probability distributions arrive one by one in a uniformly random order, and an algorithm must irrevocably pick one of the samples as soon as it arrives. The goal is to maximize the expected value of the sample picked relative to the expected maximum of the distributions. This is one of the most simple and fundamental problems in online decision making that models the process selling one item to a sequence of costumers. For a closely related problem called the Prophet Inequality where the order of the random variables is adversarial, it is known that one can achieve in expectation 1/2 of the expected maximum, and no better ratio is possible. For the Prophet Secretary problem, that is, when the variables arrive in a random order, Esfandiari et al. (2015) showed that one can actually get 1-1/e of the maximum. The 1-1/e bound was recently extended to more general settings by Ehsani et al. (2018). Given these results, one might be tempted to believe that 1-1/e is the correct bound. We show that this is not the case by providing an algorithm for the Prophet Secretary problem that beats the 1-1/e bound and achieves 1-1/e+1/400 times the expected maximum. We also prove a hardness result on the performance of algorithms under a natural restriction which we call deterministic distribution-insensitivity.

We present an efficient construction of additively weighted Voronoi diagrams on planar graphs. Let G be a planar graph with n vertices and b sites that lie on a constant number of faces. We show how to preprocess G in Õ(nb2) time1 so that one can compute any additively weighted Voronoi diagram for these sites in Õ(b) time. We use this construction to compute the diameter of a directed planar graph with real arc lengths in Õ(n5/3) time. This improves the recent breakthrough result of Cabello (SODA’17), both by improving the running time (from Õ(n11/6)), and by providing a deterministic algorithm. It is in fact the first truly subquadratic deterministic algorithm for this problem. Our use of Voronoi diagrams to compute the diameter follows that of Cabello, but he used abstract Voronoi diagrams, which makes his diameter algorithm more involved, more expensive, and randomized. As in Cabello's work, our algorithm can also compute the Wiener index of a planar graph (i.e., the sum of all pairwise distances) within the same bound. Our construction of Voronoi diagrams for planar graphs is of independent interest. It has already been used to obtain fast exact distance oracles for planar graphs [Cohen-Addad et al., FOCS’17].

In 1999, Brodal and Fagerberg (BF) gave an algorithm for maintaining a low outdegree orientation of a dynamic uniformly sparse graph. Specifically, for a dynamic graph on n -vertices, with arboricity bounded by α at all times, the BF algorithm supports edge updates in $O(łog n)$ amortized update time, while keeping the maximum outdegree in the graph bounded by $O(α)$. Such an orientation provides a basic data structure for uniformly sparse graphs, which found applications to a plethora of dynamic graph algorithms. A significant weakness of the BF algorithm is the possible temporary blowup of the maximum outdegree, following edge insertions. Although BF eventually reduces all outdegrees to $O(α)$, some vertices may reach an outdegree of $Ømega(n)$ during the process, hence local memory usage at the vertices--an important quality measure in distributed systems--cannot be bounded. We show how to modify the BF algorithm to guarantee that the outdegrees of all vertices are bounded by $O(α)$ at all times, without hurting any of its other properties, and present an efficient distributed implementation of the modified algorithm. This provides the first representation of distributed networks in which the local memory usage at vertices is bounded by the arboricity (which is essentially the average degree of the densest subgraph) rather than the maximum degree. For settings where there is no local memory constraints, one may take the temporary outdegree blowup to the extreme and allow a permanent outdegree blowup. This allows us to address the second significant weakness of the BF algorithm -- its inherently global nature: An insertion of an edge $(u,v)$ may trigger changes in the orientations of edges that are arbitrarily far away from u and v . We suggest an alternative local scheme, which does not guarantee any outdegree bound on the vertices, yet is just as efficient as the BF scheme for some applications. For example, we obtain a local dynamic algorithm for maintaining a maximal matching with sub-logarithmic update time in uniformly sparse networks, providing an exponential improvement over the state-of-the-art in this context.

Traffic splitting is essential for load balancing over multiple servers, middleboxes, and paths. Often the target traffic distribution is not uniform (e.g., due to heterogeneous servers or path capacities). A natural approach is to implement traffic split in existing rule matching tables in commodity switches. In this paper we suggest an analytical study of such an approach. To do that, we relate the description of distributions in switches to signed representations of positive integers. We suggest an optimal algorithm that minimizes the number of rules needed to represent a weighted traffic distribution. Since switches often have limited rule-table space, the target distribution cannot always be exactly achieved. Accordingly, we also develop a solution that, given a restricted number of rules, finds a distribution that can be implemented within the limited space. To select among different solutions, we describe metrics for quantifying the accuracy of an approximation. We demonstrate the efficiency of the solutions through extensive experiments.

Traffic splitting is essential for load balancing over multiple servers, middleboxes, and paths. Often the target traffic distribution is not uniform (e.g., due to heterogeneous servers or path capacities). A natural approach is to implement traffic split in existing rule matching tables in commodity switches. In this paper, we conduct an analytical study to understand this ability of switches. To do that, we indicate on a surprising strong connection between the description of distributions in switches to signed representations of positive integers. We introduce an optimal algorithm that minimizes the number of rules needed to represent a weighted traffic distribution. Since switches often have limited rule-table space, the target distribution cannot always be exactly achieved. Accordingly, we also develop a solution that, given a restricted number of rules, finds a distribution that can be implemented within the limited space. To select among different solutions, we describe metrics for quantifying the accuracy of an approximation. We demonstrate the efficiency of the solutions through extensive experiments.

Let $P \subset \mathbb{R}^2$ be a planar $n$-point set such that each point $p \in P$ has an associated radius $r_p > 0$. The transmission graph $G$ for $P$ is the directed graph with vertex set $P$ such that for any $p, q \in P$, there is an edge from $p$ to $q$ if and only if $d(p, q) \leq r_p$. Let $t > 1$ be a constant. A $t$-spanner for $G$ is a subgraph $H \subseteq G$ with vertex set $P$ so that for any two vertices $p,q \in P$, we have $d_H(p, q) \leq t d_G(p, q)$, where $d_H$ and $d_G$ denote the shortest path distance in $H$ and $G$, respectively (with Euclidean edge lengths). We show how to compute a $t$-spanner for $G$ with $O(n)$ edges in $O(n (\log n + \log \Psi))$ time, where $\Psi$ is the ratio of the largest and smallest radius of a point in $P$. Using more advanced data structures, we obtain a construction that runs in $O(n \log^5 n)$ time, independent of $\Psi$. We give two applications for our spanners. First, we show how to use our spanner to find a BFS tree in $G$ from any given start vertex in $O(n \log n)$ time (in addition to the time it takes to build the spanner). Second, we show how to use our spanner to extend a reachability oracle to answer geometric reachability queries. In a geometric reachability query we ask whether a vertex $p$ in $G$ can “reach” a target $q$ which is an arbitrary point in the plane (rather than restricted to be another vertex $q$ of $G$ in a standard reachability query). Our spanner allows the reachability oracle to answer geometric reachability queries with an additive overhead of $O(\log n\log \Psi)$ to the query time and $O(n \log \Psi)$ to the space.

In the min-cost bipartite perfect matching with delays (MBPMD) problem, requests arrive online at points of a finite metric space. Each request is either positive or negative and has to be matched to a request of opposite polarity. As opposed to traditional online matching problems, the algorithm does not have to serve requests as they arrive, and may choose to match them later at a cost. Our objective is to minimize the sum of the distances between matched pairs of requests (the connection cost) and the sum of the waiting times of the requests (the delay cost). This objective exhibits a natural tradeoff between minimizing the distances and the cost of waiting for better matches. This tradeoff appears in many real-life scenarios, notably, ride-sharing platforms. MBPMD is related to its non-bipartite variant, min-cost perfect matching with delays (MPMD), in which each request can be matched to any other request. MPMD was introduced by Emek et al. (STOC'16), who showed an O(log^2(n)+log(Delta))-competitive randomized algorithm on n-point metric spaces with aspect ratio Delta. Our contribution is threefold. First, we present a new lower bound construction for MPMD and MBPMD. We get a lower bound of Omega(sqrt(log(n)/log(log(n)))) on the competitive ratio of any randomized algorithm for MBPMD. For MPMD, we improve the lower bound from Omega(sqrt(log(n))) (shown by Azar et al., SODA'17) to Omega(log(n)/log(log(n))), thus, almost matching their upper bound of O(log(n)). Second, we adapt the algorithm of Emek et al. to the bipartite case, and provide a simplified analysis that improves the competitive ratio to O(log(n)). The key ingredient of the algorithm is an O(h)-competitive randomized algorithm for MBPMD on weighted trees of height h. Third, we provide an O(h)-competitive deterministic algorithm for MBPMD on weighted trees of height h. This algorithm is obtained by adapting the algorithm for MPMD by Azar et al. to the apparently more complicated bipartite setting.

An $ε$-approximate incidence between a point and some geometric object (line, circle, plane, sphere) occurs when the point and the object lie at distance at most $ε$ from each other. Given a set of points and a set of objects, computing the approximate incidences between them is a major step in many database and web-based applications in computer vision and graphics, including robust model fitting, approximate point pattern matching, and estimating the fundamental matrix in epipolar (stereo) geometry. In a typical approximate incidence problem of this sort, we are given a set $P$ of $m$ points in two or three dimensions, a set $S$ of $n$ objects (lines, circles, planes, spheres), and an error parameter $ε>0$, and our goal is to report all pairs $(p,s)\in P\times S$ that lie at distance at most $ε$ from one another. We present efficient output-sensitive approximation algorithms for quite a few cases, including points and lines or circles in the plane, and points and planes, spheres, lines, or circles in three dimensions. Several of these cases arise in the applications mentioned above.

We study the problem of clustering the vertices of a weighted hypergraph such that on average the vertices of each edge can be covered by a small number of clusters. This problem has many applications such as for designing medical tests, clustering files on disk servers, and placing network services on servers. The edges of the hypergraph model groups of items that are likely to be needed together, and the optimization criteria which we use can be interpreted as the average delay (or cost) to serve the items of a typical edge. We describe and analyze algorithms for this problem for the case in which the clusters have to be disjoint and for the case where clusters can overlap. The analysis is often subtle and reveals interesting structure and invariants that one can utilize.

We consider the problem of online Min-cost Perfect Matching with Delays (MPMD) recently introduced by Emek et al, (STOC 2016). This problem is defined on an underlying n-point metric space. An adversary presents real-time requests online at points of the metric space, and the algorithm is required to match them, possibly after keeping them waiting for some time. The cost incurred is the sum of the distances between matched pairs of requests (the connection cost), and the sum of the waiting times of the requests (the delay cost). We prove the first logarithmic upper bound and the first polylogarithmic lower bound on the randomized competitive ratio of this problem. We present an algorithm with a competitive ratio of O(log n), which improves the upper bound of O log2 n + logΔ) of Emek et al, by removing the dependence on Δ, the aspect ratio of the metric space (which can be unbounded as a function of n). The core of our algorithm is a deterministic algorithm for MPMD on metrics induced by edge-weighted trees of height h, whose cost is guaranteed to be at most O(1) times the connection cost plus O(h) times the delay cost of every feasible solution. The reduction from MPMD on arbitrary metrics to MPMD on trees is achieved using the result on embedding n-point metric spaces into distributions over weighted hierarchically separated trees of height O(log n), with distortion O(log n). We also prove a lower bound of on the competitive ratio of any randomized algorithm. This is the first lower bound which increases with n, and is attained on the metric of n equally spaced points on a line.

An f-Sensitive Distance Oracle with stretch a preprocesses a graph G(V, E) and produces a small data structure that is used to answer subsequent queries. A query is a triple consisting of a set F ⊂ E of at most f edges, and vertices s and t. The oracle answers a query (F,s.,t) by returning a value d which is equal to the length of some path between s and t in the graph G\F (the graph obtained from G by discarding all edges in F). Moreover, d is at most a times the length of the shortest path between s and t in G \ F. The oracle can also construct a path between s and t in G\F of length d. To the best of our knowledge we give the first nontrivial f-sensitive distance oracle with fast query time and small stretch capable of handling multiple edge failures. Specifically, for any and a fixed ∊ > 0 our oracle answers queries (F,s,t) in time O(l) with (1 + ∊) stretch using a data structure of size n2+0(1) For comparison, the naive alternative requires mfn2 space for sublinear query time.

We describe a new data structure for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions that includes Lp-norms and additively weighted Euclidean distances, and for general (convex, pair- wise disjoint) sites that have constant description complexity (line segments, disks, etc.). Our data structure has a polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat and Sharir that required O(n∊) time for an update and O(log n) time for a query [1]. Our data structure has numerous applications, and in all of them it gives faster algorithms, typically reducing an O(n∊) factor in the bounds to polylogarithmic. To further demonstrate its effectiveness, we give here two new applications: an efficient construction of a spanner in a disk intersection graph, and a data structure for efficient connectivity queries in a dynamic disk graph. To obtain this data structure, we combine and extend various techniques and obtain several side results that are of independent interest. Our data structure depends on the existence and an efficient construction of “vertical” shallow cuttings in arrangements of bivariate algebraic functions. We prove that an appropriate level in an arrangement of a random sample of a suitable size provides such a cutting. To compute it efficiently, we develop a randomized incremental construction algorithm for finding the lowest k levels in an arrangement of bivariate algebraic functions (we mostly consider here collections of functions whose lower envelope has linear complexity, as is the case in the dynamic nearest- neighbor context). To analyze this algorithm, we improve a longstanding bound on the combinatorial complexity of the vertical decomposition of these levels. Finally, to obtain our structure, we plug our vertical shallow cutting construction into Chan's algorithm for efficiently maintaining the lower envelope of a dynamic set of planes in ℝ3. While doing this, we also revisit Chan's technique and present a variant that uses a single binary counter, with a simpler analysis and an improved amortized deletion time.

Often one would like to allocate shared resources in a fair way. A common and well-studied notion of fairness isMax-Min Fairness, where we first maximize the smallest allocation, and subject to that the second smallest, and so on. We consider a networking application where multiple commodities compete over the capacity of a network. In our setting, each commodity has multiple possible paths to route its demand (for example, a network using Multiprotocol Label Switching (MPLS) tunneling). In this setting, the only known way of finding a max-min fair allocation requires an iterative solution of multiple linear programs. Such an approach, although polynomial time, scales badly with the size of the network, the number of demands, and the number of paths, and is hard to implement in a distributed environment. More importantly, a network operator has limited control and understanding of the inner working of the algorithm. In this article we introduce Upward Max-Min Fairness, a novel relaxation of Max-Min Fairness, and present a family of simple dynamics that converge to it. These dynamics can be implemented in a distributed manner. Moreover, we present an efficient combinatorial algorithm for finding an upward max-min fair allocation. This algorithm is a natural extension of the well-known Water Filling Algorithm for a multiple path setting. We test the expected behavior of this new algorithm and show that on realistic networks upward max-min fair allocations are comparable to the max-min fair allocations both in fairness and in network utilization.

We introduce the hollow heap , a very simple data structure with the same amortized efficiency as the classical Fibonacci heap. All heap operations except delete and delete - min take O (1) time, worst case as well as amortized; delete and delete - min take O (log n ) amortized time on a heap of n items. Hollow heaps are the simplest structure to achieve these bounds. Hollow heaps combine two novel ideas: the use of lazy deletion and re-insertion to do decrease - key operations and the use of a dag (directed acyclic graph) instead of a tree or set of trees to represent a heap. Lazy deletion produces hollow nodes (nodes without items), giving the data structure its name.

We describe a data structure for submatrix maximum queries in Monge matrices or partial Monge matrices, where a query seeks the maximum element in a contiguous submatrix of the given matrix. The structure, for an n × n Monge matrix, takes O ( n log n ) space and O ( n log n ) preprocessing time, and answers queries in O (log 2 n ) time. For partial Monge matrices, the space grows by α( n ), the preprocessing grows by α( n )log n (α( n ) is the inverse Ackermann function), and the query remains O (log 2 n ). Our design exploits an interpretation of the column maxima in a Monge (partial Monge, respectively) matrix as an upper envelope of pseudo-lines (pseudo-segments, respectively). We give two applications: (1) For a planar set of n points in an axis-parallel rectangle B , we build a data structure, in O ( n α( n )log 4 n ) time and O ( n α( n )log 3 n ) space, that returns, for a query point p , the largest-area empty axis-parallel rectangle contained in B and containing p , in O (log 4 n ) time. This improves substantially the nearly quadratic storage and preprocessing obtained by Augustine et al. [2010]. (2) Given an n -node arbitrarily weighted planar digraph, with possibly negative edge weights, we build, in O ( n log 2 n /log log n ) time, a linear-size data structure that supports edge-weight updates and graph-distance queries between arbitrary pairs of nodes in O ( n 2/3 log 5/3 n ) time per operation. This improves a previous algorithm of Fakcharoenphol and Rao [2006]. Our data structure has already been applied in a recent maximum flow algorithm for planar graphs in Borradaile et al. [2011].

Let H be a set of n non-vertical planes in three dimensions, and let r < n be a parameter. We give a simple alternative proof of the existence of a O(1/r)-cutting of the first n/r levels of (H), which consists of O(r) semi-unbounded vertical triangular prisms. The same construction yields an approximation of the (n/r)-level by a terrain consisting of O(r/∊3) triangular faces, which lies entirely between the levels (1 ± ∊)n/r. The proof does not use sampling, and exploits techniques based on planar separators and various structural properties of levels in three-dimensional arrangements and of planar maps. The proof is constructive, and leads to a simple randomized algorithm, that computes the terrain in O(n + r2∊–6 log3 r) expected time. An application of this technique allows us to mimic Matoušek's construction of cuttings in the plane [36], to obtain a similar construction of “layered” (1/r)-cutting of the entire arrangement (H), of optimal size O(r3). Another application is a simplified optimal approximate range counting algorithm in three dimensions, competing with that of Afshani and Chan [1].

Gabow and Tarjan showed that the Bottleneck Path (BP) problem, i.e., finding a path between a given source and a given target in a weighted directed graph whose largest edge weight is minimized, as well as the Bottleneck spanning tree (BST) problem, i.e., finding a directed spanning tree rooted at a given vertex whose largest edge weight is minimized, can both be solved deterministically in O(m * log^*(n)) time, where m is the number of edges and n is the number of vertices in the graph. We present a slightly improved randomized algorithm for these problems with an expected running time of O(m * beta(m,n)), where beta(m,n) = min{k >= 1 | log^{(k)}n <= m/n } <= log^*(n) - log^*(m/n)+1. This is the first improvement for these problems in over 25 years. In particular, if m >= n * log^{(k)} * n, for some constant k, the expected running time of the new algorithm is O(m). Our algorithm, as that of Gabow and Tarjan, work in the comparison model. We also observe that in the word-RAM model, both problems can be solved deterministically in O(m) time. Finally, we solve an open problem of Andersson et al., giving a deterministic O(m)-time comparison-based algorithm for solving deterministic 2-player turn-based zero-sum terminal payoff games, also known as Deterministic Graphical Games (DGG).

Hardware-based packet classification has become an essential component in many networking devices. It often relies on ternary content-addressable memories (TCAMs), which compare the packet header against a set of rules. TCAMs are not well suited to encode range rules. Range rules are often encoded by multiple TCAM entries, and little is known about the smallest number of entries that one needs for a specific range. In this paper, we introduce the In/Out TCAM, a new architecture that combines a regular TCAM together with a modified TCAM. This custom architecture enables independent encoding of each rule in a set of rules. We provide the following theoretical results for the new architecture: 1) We give an upper bound on the worst-case expansion of range rules in one and two dimensions. 2) For extremal ranges, which are 89% of the ranges that occur in practice, we provide an efficient algorithm that computes an optimal encoding. 3) We present a closed-form formula for the average expansion of an extremal range.

The average distance from a node to all other nodes in a graph, or from a query point in a metric space to a set of points, is a fundamental quantity in data analysis. The inverse of the average distance, known as the (classic) closeness centrality of a node, is a popular importance measure in the study of social networks. We develop novel structural insights on the sparsifiability of the distance relation via weighted sampling. Based on that, we present highly practical algorithms with strong statistical guarantees for fundamental problems. We show that the average distance (and hence the centrality) for all nodes in a graph can be estimated using O(epsilon^{-2}) single-source distance computations. For a set V of n points in a metric space, we show that after preprocessing which uses O(n) distance computations we can compute a weighted sample S subset of V of size O(epsilon^{-2}) such that the average distance from any query point v to V can be estimated from the distances from v to S. Finally, we show that for a set of points V in a metric space, we can estimate the average pairwise distance using O(n+epsilon^{-2}) distance computations. The estimate is based on a weighted sample of O(epsilon^{-2}) pairs of points, which is computed using O(n) distance computations. Our estimates are unbiased with normalized mean square error (NRMSE) of at most epsilon. Increasing the sample size by a O(log(n)) factor ensures that the probability that the relative error exceeds epsilon is polynomially small.

Let P be a set of n points in d dimensions, each with an associated radius r_p > 0. The transmission graph G for P has vertex set P and an edge from p to q if and only if q lies in the ball with radius r_p around p. Let t > 1. A t-spanner H for G is a sparse subgraph of G such that for any two vertices p, q connected by a path of length l in G, there is a p-q-path of length at most tl in H. We show how to compute a t-spanner for G if d=2. The running time is O(n (log n + log Psi)), where Psi is the ratio of the largest and smallest radius of two points in P. We extend this construction to be independent of Psi at the expense of a polylogarithmic overhead in the running time. As a first application, we prove a property of the t-spanner that allows us to find a BFS tree in G for any given start vertex s of P in the same time. After that, we deal with reachability oracles for G. These are data structures that answer reachability queries: given two vertices, is there a directed path between them? The quality of a reachability oracle is measured by the space S(n), the query time Q(n), and the preproccesing time. For d=1, we show how to compute an oracle with Q(n) = O(1) and S(n) = O(n) in time O(n log n). For d=2, the radius ratio Psi again turns out to be an important measure for the complexity of the problem. We present three different data structures whose quality depends on Psi: (i) if Psi < sqrt(3), we achieve Q(n) = O(1) with S(n) = O(n) and preproccesing time O(n log n); (ii) if Psi >= sqrt(3), we get Q(n) = O(Psi^3 sqrt(n)) and S(n) = O(Psi^5 n^(3/2)); and (iii) if Psi is polynomially bounded in n, we use probabilistic methods to obtain an oracle with Q(n) = O(n^(2/3)log n) and S(n) = O(n^(5/3) log n) that answers queries correctly with high probability. We employ our t-spanner to achieve a fast preproccesing time of O(Psi^5 n^(3/2)) and O(n^(5/3) log^2 n) in case (ii) and (iii), respectively.

We obtain an essentially optimal tradeoff between the amortized cost of the three basic priority queue operations insert, delete and find-min in the comparison model. More specifically, we show that for any fixed ε > 0, where n is the number of items in the priority queue and A(insert), A(delete) and A(find-min) are the amortized costs of the insert, delete and find-min operations, respectively. In particular, if A(insert) + A(delete) = O(1), then A(find-min) = Ω(n), and A(find-min) = O(nα), for some α < 1, only if A(insert) + A(delete) = Ω(log n). (We can, of course, have A(insert) = O(1), A(delete) = O(log n), or vice versa, and A(find-min) = O(1).) Our lower bound holds even if randomization is allowed. Surprisingly, such fundamental bounds on the amortized cost of the operations were not known before. Brodal, Chaudhuri and Rad-hakrishnan, obtained similar bounds for the worst-case complexity of find-min.

We consider the minimum cost flow problem on graphs with unit capacities and its special cases. In previous studies, special purpose algorithms exploiting the fact that capacities are one have been developed. In contrast, for maximum flow with unit capacities, the best bounds are proven for slight modifications of classical blocking flow and push-relabel algorithms. In this paper we show that the classical cost scaling algorithms of Goldberg and Tarjan (for general integer capacities) applied to a problem with unit capacities achieve or improve the best known bounds. For weighted bipartite matching we establish a bound of O(\sqrt{rm}\log C) on a slight variation of this algorithm. Here r is the size of the smaller side of the bipartite graph, m is the number of edges, and C is the largest absolute value of an arc-cost. This simplifies a result of [Duan et al. 2011] and improves the bound, answering an open question of [Tarjan and Ramshaw 2012]. For graphs with unit vertex capacities we establish a novel O(\sqrt{n}m\log(nC)) bound. We also give the first cycle canceling algorithm for minimum cost flow with unit capacities. The algorithm naturally generalizes the single source shortest path algorithm of [Goldberg 1995].

We describe a way of assigning labels to the vertices of any undirected graph on up to n vertices, each composed of n/2+O(1) bits, such that given the labels of two vertices, and no other information regarding the graph, it is possible to decide whether or not the vertices are adjacent in the graph. This is optimal, up to an additive constant, and constitutes the first improvement in almost 50 years of an n/2+O(log n) bound of Moon. As a consequence, we obtain an induced-universal graph for n-vertex graphs containing only O(2n/2) vertices, which is optimal up to a multiplicative constant, solving an open problem of Vizing from 1968. We obtain similar tight results for directed graphs, tournaments and bipartite graphs.

The Fréchet distance is a well-studied similarity measure between curves. The discrete Fréchet distance is an analogous similarity measure, defined for two sequences of m and n points, where the points are usually sampled from input curves. We consider a variant, called the discrete Fréchet distance with shortcuts , which captures the similarity between (sampled) curves in the presence of outliers. When shortcuts are allowed only in one noise-containing curve, we give a randomized algorithm that runs in O (( m + n ) 6/5 + ε ) expected time, for any ε > 0. When shortcuts are allowed in both curves, we give an O (( m 2/3 n 2/3 + m + n )log 3 ( m + n ))-time deterministic algorithm. We also consider the semicontinuous Fréchet distance with one-sided shortcuts, where we have a sequence of m points and a polygonal curve of n edges, and shortcuts are allowed only in the sequence. We show that this problem can be solved in randomized expected time O (( m + n ) 2/3 m 2/3 n 1/3 log ( m + n )). Our techniques are novel and may find further applications. One of the main new technical results is: Given two sets of points A and B in the plane and an interval I , we develop an algorithm that decides whether the number of pairs ( x , y ) ∈ A × B whose distance dist( x , y ) is in I is less than some given threshold L . The running time of this algorithm decreases as L increases. In case there are more than L pairs of points whose distance is in I , we can get a small sample of pairs that contain a pair at approximate median distance (i.e., we can approximately “bisect” I ). We combine this procedure with additional ideas to search, with a small overhead, for the optimal one-sided Fréchet distance with shortcuts, using a very fast decision procedure. We also show how to apply this technique for approximating distance selection (with respect to rank), and a somewhat more involved variant of this technique is used in the solution of the semicontinuous Fréchet distance with one-sided shortcuts. In general, the new technique can be applied to optimization problems for which the decision procedure is very fast but standard techniques like parametric search makes the optimization algorithm substantially slower.

The Fréchet distance is a well studied similarity measure between curves. The discrete Fréchet distance is an analogous similarity measure, defined for two sequences of m and n points, where the points are usually sampled from input curves. We consider a variant, called the discrete Fréchet distance with shortcuts, which captures the similarity between (sampled) curves in the presence of outliers. When shortcuts are allowed only in one noise-containing curve, we give a randomized algorithm that runs in O((m+n)6/5+ϵ) expected time, for any ϵ > 0. When shortcuts are allowed in both curves, we give an O((m2/3n2/3 + m + n) log3(m + n))-time deterministic algorithm.

Dantzig's pivoting rule is one of the most studied pivoting rules for the simplex algorithm. While the simplex algorithm with Dantzig's rule may require an exponential number of pivoting steps on general linear programs, and even on min cost flow problems, Orlin showed that O(mn2 logn) Dantzig's pivoting steps suffice to solve shortest paths problems, where n and m are the number of vertices and edges, respectively, in the graph. Post and Ye recently showed that the simplex algorithm with Dantzig's rule requires only O(m2n3 log2 n) pivoting steps to solve deterministic MDPs with the same discount factor for each edge, and only O(m3n5 log2 n) pivoting steps to solve deterministic MDPs with possibly a distinct discount factor for each edge. We improve Orlin's bound for shortest paths and Post and Ye's bound for deterministic MDPs with the same discount factor by a factor of n to O(mnlogn), and O(m2n2 log2n), respectively. We also improve by a factor of n the bound for deterministic MDPs with varying discounts when all discount factors are sufficiently close to 1. These bounds follow from a new proof technique showing that after a certain number of steps, either many edges are excluded from participating in further policies, or there is a large decrease in the value. We also obtain an Ω(n2) lower bound on the number of Dantzig's pivoting steps required to solve shortest paths problems, even when m = Θ(n). Finally, we describe a reduction from the problem of finding a minimum cost to time ratio cycle to the problem of finding an optimal policy for a discounted deterministic MDP with varying discount factors that tend to 1. This gives a strongly polynomial time algorithm for the problem that does not use Megiddo's parametric search technique.

The Fréchet distance measures similarity between two curves $f$ and $g$ that takes into account the ordering of the points along the two curves: Informally, it is the minimum length of a leash required to connect a dog, walking along $f$, and its owner, walking along $g$, as they walk without backtracking along their respective curves from one endpoint to the other. The discrete Fréchet distance replaces the dog and its owner by a pair of frogs that can only reside on $m$ and $n$ specific stones, respectively. The stones are in fact sequences of points, typically sampled from the respective curves $f$ and $g$. These frogs hop from one stone to the next without backtracking, and the discrete Fréchet distance is the minimum length of a “leash” that connects the frogs and allows them to execute such a sequence of hops from the starting points to the terminal points of their sequences. The discrete Fréchet distance can be computed in $O(mn)$ time by a straightforward dynamic programming algorithm. We present the first subquadratic algorithm for computing the discrete Fréchet distance between two sequences of points in the plane. Assuming $m\le n$, the algorithm runs in $O(\frac{mn\log\log n}{\log n})$ time, in the word RAM model, using $O(n)$ storage. Our approach uses the geometry of the problem in a subtle way to encode legal positions of the frogs as states of a finite automaton.

We consider the following problem, which arises in many database and web-based applications: Given a set $P$ of $n$ points in a high-dimensional space $\mathbb{R}^d$ and a distance $r$, we want to report all pairs of points of $P$ at Euclidean distance at most $r$. We present two randomized algorithms, one based on randomly shifted grids, and the other on randomly shifted and rotated grids. The running time of both algorithms is of the form $C(d)(n+k)\log n$, where $k$ is the output size and $C(d)$ is a constant that depends on the dimension $d$. The $\log n$ factor is needed to guarantee, with high probability, that all neighbor pairs are reported and can be dropped if it suffices to report, in expectation, an arbitrarily large fraction of the pairs. When only translations are used, $C(d)$ is of the form $(a\sqrt{d})^d$ for some (small) absolute constant $a\approx 0.484$; this bound is worst-case tight, up to an exponential factor of about $2^d$. When both rotationsand translations are used, $C(d)$ can be improved to roughly $6.74^d$, getting rid of the superexponential factor $\sqrt{d}^d$. When the input set (lies in a subset of $d$-space that) has low doubling dimension $\delta$, the performance of the first algorithm improves to $C(d,\delta)(n+k)\log n$ (or to $C(d,\delta)(n+k)$), where $C(d,\delta) = O((ed/\delta)^\delta)$ for $\delta \le \sqrt{d}$. Otherwise, $C(d,\delta) = O( e^{\sqrt{d}} \sqrt{d}^\delta )$. We also present experimental results on several large data sets, demonstrating that our algorithms run significantly faster than all the leading existing algorithms for reporting neighbors.

Let C=C1,...,Cn} be a set of n pairwise-disjoint convex s-gons, for some constant s, and let p be a probability density function (pdf) over the non-negative reals. For each i, let Ki be the Minkowski sum of Ci with a disk of radius ri, where each ri is a random non-negative number drawn independently from the distribution determined by π. We show that the expected complexity of the union of K1,..,Kn is O(n log n), for any pdf p; the constant of proportionality depends on s, but not on the pdf. Next, we consider the following problem that arises in analyzing the vulnerability of a network under a physical attack. Let G=(V,E) be a planar geometric graph where E is a set of n line segments with pairwise-disjoint relative interiors. Let f: R -> [0,1] be an edge failure probability function, where a physical attack at a location x causes an edge e of E at distance r from x to fail with probability f(r); we assume that f is of the form f(x)=1-P(x), where P is a cumulative distribution function on the non-negative reals. The goal is to compute the most vulnerable location for G, i.e., the location of the attack that maximizes the expected number of failing edges of G. Using our bound on the complexity of the union of random Minkowski sums, we present a near-linear Monte-Carlo algorithm for computing a location that is an approximately most vulnerable location of attack for G.

Hardware-based packet classification has become an essential component in many networking devices. It often relies on TCAMs (ternary content-addressable memories), which need to compare the packet header against a set of rules. But efficiently encoding these rules is not an easy task. In particular, the most complicated rules are range rules, which usually require multiple TCAM entries to encode them. However, little is known on the optimal encoding of such non-trivial rules. In this work, we take steps towards finding an optimal encoding scheme for every possible range rule. We first present an optimal encoding for all possible generalized extremal rules. Such rules represent 89% of all non-trivial rules in a typical real-life classification database. We also suggest a new method of simply calculating the optimal expansion of an extremal range, and present a closed-form formula of the average optimal expansion over all extremal ranges. Next, we present new bounds on the worst-case expansion of general classification rules, both in one-dimensional and two-dimensional ranges. Last, we introduce a new TCAM architecture that can leverage these results by providing a guaranteed expansion on the tough rules, while dealing with simpler rules using a regular TCAM. We conclude by verifying our theoretical results in experiments with synthetic and real-life classification databases.

The Fréchet distance is a similarity measure between two curves A and B that takes into account the location and ordering of the points along the two curves: Informally, it is the minimum length of a leash required to connect a dog, walking along A, and its owner, walking along B, as they walk without backtracking along their respective curves from one endpoint to the other. The discrete Fréchet distance replaces the dog and its owner by a pair of frogs that can only reside on n and m specific stones on the curves A and B, respectively. These frogs hop from one stone to the next without backtracking, and the discrete Fréchet distance is the minimum length of a “leash” that connects the frogs and allows them to execute such a sequence of hops. It can be computed in quadratic time by a straightforward dynamic programming algorithm. We present the first subquadratic algorithm for computing the discrete Fréchet distance between two sequences of points in the plane. Assuming m ≤ n, the algorithm runs in time, in the standard RAM model, using O(n) storage. Our approach uses the geometry of the problem in a subtle way to encode legal positions of the frogs as states of a finite automaton.

We consider the following problem, which arises in many database and web-based applications: Given a set P of n points in a high-dimensional space ℝd and a distance r, we want to report all pairs of points of P at Euclidean distance at most r. We present two randomized algorithms, one based on randomly shifted grids, and the other on randomly shifted and rotated grids. The running time of both algorithms is of the form C(d)(n + k) log n, where k is the output size and C(d) is a constant that depends on the dimension d. The log n factor is needed to guarantee, with high probability, that all neighbor pairs are reported, and can be dropped if it suffices to report, in expectation, an arbitrarily large fraction of the pairs. When only translations are used, C(d) is of the form , for some (small) absolute constant a ≈ 0.484; this bound is worst-case tight, up to an exponential factor of about 2d. When both rotations and translations are used, C(d) can be improved to roughly 6.74d, getting rid of the super-exponential factor . When the input set (lies in a subset of d-space that) has low doubling dimension δ, the performance of the first algorithm improves to C(d, δ)(n + k) log n (or to C(d, δ)(n + k)), where C(d, δ) = O((ed/δ)δ), for . Otherwise, . We also present experimental results on several large datasets, demonstrating that our algorithms run significantly faster than all the leading existing algorithms for reporting neighbors.

Recent research has shown that crowd sourcing can be used effectively to solve problems that are difficult for computers, e.g., optical character recognition and identification of the structural configuration of natural proteins. In this paper we propose to use the power of the crowd to address yet another difficult problem that frequently occurs in a daily life - answering planning queries whose output is a sequence of objects/actions, when the goal, i.e, the notion of "best output", is hard to formalize. For example, planning the sequence of places/attractions to visit in the course of a vacation, where the goal is to enjoy the resulting vacation the most, or planning the sequence of courses to take in an academic schedule planning, where the goal is to obtain solid knowledge of a given subject domain. Such goals may be easily understandable by humans, but hard or even impossible to formalize for a computer. We present a novel algorithm for efficiently harnessing the crowd to assist in answering such planning queries. The algorithm builds the desired plans incrementally, choosing at each step the 'best' questions so that the overall number of questions that need to be asked is minimized. We prove the algorithm to be optimal within its class and demonstrate experimentally its effectiveness and efficiency.

In 1998, Chazelle [J. ACM, 47 (2000), pp. 1012--1027] introduced a new kind of meldable heap (priority queue) called the soft heap. Soft heaps trade accuracy for speed: the heap operations are allowed to increase the keys of certain items, thereby making these items bad, as long as the number of bad items in the data structure is at most $\varepsilon m$, where $m$ is the total number of insertions performed so far, and $\varepsilon$ is an error parameter. The amortized time per heap operation is $O(\lg \frac{1}{\varepsilon})$, reduced from $O(\lg n)$, where $n$ is the number of items in the heap. Chazelle used soft heaps in several applications, including a faster deterministic minimum-spanning-tree algorithm and a new deterministic linear-time selection algorithm. We give a simplified implementation of soft heaps that uses less space and avoids Chazelle's dismantling operations. We also give a simpler, improved analysis that yields an amortized time bound of $O(\lg \frac{1}{\varepsilon})$ for each deletion, $O(1)$ for each other operation.

Let P be a set of n points in the plane. We present an efficient algorithm for preprocessing P, so that, for a given query point q, we can quickly report the largest disk that contains q but its interior is disjoint from P. The storage required by the data structure is O(n log n), the preprocessing cost is O(n log2n), and a query takes O(log2n) time.

Often one would like to allocate shared resources in a fair way. A common and well studied notion of fairness is Max-Min Fairness, where we first maximize the smallest allocation, and subject to that the second smallest, and so on. We consider a networking application where multiple commodities compete over the capacity of a network. In our setting each commodity has multiple possible paths to route its demand (for example, a network using MPLS tunneling). In this setting, the only known way of finding a max-min fair allocation requires an iterative solution of multiple linear programs. Such an approach, although polynomial time, scales badly with the size of the network, the number of demands, and the number of paths. More importantly, a network operator has limited control and understanding of the inner working of the algorithm. Finally, this approach is inherently centralized and cannot be implemented via a distributed protocol. In this paper we introduce Upward Max-Min Fairness, a novel relaxation of Max-Min Fairness and present a family of simple dynamics that converge to it. These dynamics can be implemented in a distributed manner. Moreover, we present an efficient combinatorial algorithm for finding an upward max-min fair allocation, which is a natural extension of the well known Water Filling Algorithm for a multiple path setting. We test the expected behavior of this new algorithm and show that on realistic networks upward max-min fair allocations are comparable to the max-min fair allocations both in fairness and in network utilization.

Many practically deployed flow algorithms produce the output as a set of values associated with the network links. However, to actually deploy a flow in a network we often need to represent it as a set of paths between the source and destination nodes. In this paper we consider the problem of decomposing a flow into a small number of paths. We show that there is some fixed constant β >; 1 such that it is NP-hard to find a decomposition in which the number of paths is larger than the optimal by a factor of at most β. Furthermore, this holds even if arcs are associated only with three different flow values. We also show that straightforward greedy algorithms for the problem can produce much larger decompositions than the optimal one, on certain well tailored inputs. On the positive side we present a new approximation algorithm that decomposes all but an c-fraction of the flow into at most O(1/ϵ2) times the smallest possible number of paths. We compare the decompositions produced by these algorithms on real production networks and on synthetically generated data. Our results indicate that the dependency of the decomposition size on the fraction of flow covered is exponential. Hence, covering the last few percent of the flow may be costly, so if the application allows, it may be a good idea to decompose most but not all the flow. The experiments also reveal the fact that while for realistic data the greedy approach works very well, our novel algorithm which has a provable worst case guarantee, typically produces only slightly larger decompositions.

We describe a data structure for submatrix maximum queries in Monge matrices or Monge partial matrices, where a query specifies a contiguous submatrix of the given matrix, and its output is the maximum element of that submatrix. Our data structure for an n × n Monge matrix takes O(n log n) space, O(n log2 n) preprocessing time, and can answer queries in O(log2 n) time. For a Monge partial matrix the space bound and the preprocessing time both grow by the small factor α(n), where α(n) is the inverse Ackermann function. Our design exploits an interpretation of the column maxima in a Monge matrix (resp., Monge partial matrix) as an upper envelope of pseudo-lines (resp., pseudosegments). We give two applications for this data structure: (1) For a set of n points in a rectangle B in the plane, we build a data structure that, given a query point p, returns the largest-area empty axis-parallel rectangle contained in B and containing p, in O(log4 n) time. The preprocessing time is O(nα(n) log4 n), and the space required is O(nα(n) log3 n). This improves substantially a previous data structure of Augustine et al. [arXiv:1004.0558] that requires quadratic space. (2) Given an n-node arbitrarily weighted planar digraph, with possibly negative edge weights, we build, in O(n log2 n/log log n) time, a linear-size data structure that supports edge-weight updates and distance queries between arbitrary pairs of nodes (where the distance is minimum weight of a path in the graph between the pair of nodes), in O(n2/3 log5,3 n) time for each update and query. This improves the O(n4/5 log13/5 n)-time bound of Fakcharoenphol and Rao [JCSS 72, 2006]. Our data structure has already been applied in a recent maximum flow algorithm for planar graphs of Borradaile et al. [FOCS 2011], and we believe it will find additional applications.

Let S be a set of n intervals in $\mathbb{R}$, and let $(\mathbf{S}, +)$ be any commutative semigroup. We assign a weight $\omega(s) \in \mathbf{S}$ to each interval in S. For a point $x \in \mathbb{R}$, let $S(x) \subseteq S$ be the set of intervals that contain x. Given a point $q \in \mathbb{R}$, the stabbing-semigroup query asks for computing $\sum_{s \in S(q)} \omega(s)$. We propose a linear-size dynamic data structure, under the pointer-machine model, that answers queries in worst-case $O(\log n)$ time and supports both insertions and deletions of intervals in amortized $O(\log n)$ time. It is the first data structure that attains the optimal $O(\log n)$ bound for all three operations. Furthermore, our structure can easily be adapted to external memory, where we obtain a linear-size structure that answers queries and supports updates in $O(\log_B n)$ I/Os, where B is the disk block size. For the restricted case of a nested family of intervals (either every pair of intervals is disjoint or one contains the other), we present a simpler solution based on dynamic trees.

We study envy-free mechanisms for assigning tasks to agents, where every task may take a different amount of time to perform by each agent, and the goal is to get all the tasks done as soon as possible (i.e., minimize the makespan). For indivisible tasks, we put forward an envy-free polynomial mechanism that approximates the minimal makespan to within a factor of $O(\log m)$, where m is the number of machines. This bound is almost tight, as we also show that no envy-free mechanism can achieve a better bound than $\Omega(\log m / \log\log m)$. This improves the recent result of Mu'alem [On multi-dimensional envy-free mechanisms, in Proceedings of the First International Conference on Algorithmic Decision Theory, F. Rossi and A. Tsoukias, eds., Lecture Notes in Comput. Sci. 5783, Springer, Berlin, 2009, pp. 120–131] who introduced the model and gave an upper bound of $(m+1)/2$ and a lower bound of $2-1/m$. For divisible tasks, we show that there always exists an envy-free poly-time mechanism with optimal makespan. Finally, we demonstrate how our mechanism for envy-free makespan minimization can be interpreted as a market clearing problem.

We show that the number of geometric permutations of an arbitrary collection of n pairwise disjoint convex sets in ${\mathbb R}^d$, for $d\geq 3$, is $O(n^{2d-3}\log n)$, improving Wenger's 20-year-old bound of $O(n^{2d-2})$.

Random sampling is an essential tool in the processing and transmission of data. It is used to summarize data too large to store or manipulate and meet resource constraints on bandwidth or battery power. Estimators that are applied to the sample facilitate fast approximate processing of queries posed over the original data and the value of the sample hinges on the quality of these estimators.

No abstract available.

Consider the minimum s-t cut problem in an embedded undirected planar graph. Let p be the minimum number of faces that a curve from s to $t$ passes through. If p=1, that is, the vertices s and t are on the boundary of the same face, then the minimum cut can be found in O(n)time. For general planar graphs this cut can be found in O(n log n) time. We unify these results and give an O(n log p) time algorithm. We use cut-cycles to obtain the value of the minimum cut, and study the structure of these cycles to get an efficient algorithm.

From a high volume stream of weighted items, we want to maintain a generic sample of a certain limited size k that we can later use to estimate the total weight of arbitrary subsets. This is the classic context of on-line reservoir sampling, thinking of the generic sample as a reservoir. We present an efficient reservoir sampling scheme, $\textnormal{\sc VarOptk}$, that dominates all previous schemes in terms of estimation quality. $\textnormal{\sc VarOptk}$ provides variance optimal unbiased estimation of subset sums. More precisely, if we have seen n items of the stream, then for any subset size m, our scheme based on k samples minimizes the average variance over all subsets of size m. In fact, the optimality is against any off-line scheme with k samples tailored for the concrete set of items seen. In addition to optimal average variance, our scheme provides tighter worst-case bounds on the variance of particular subsets than previously possible. It is efficient, handling each new item of the stream in $O(\log k)$ time. Finally, it is particularly well suited for combinations of samples from different streams in a distributed setting.

Let P be a simple polygon, and let Q be a set of points in P. We present an almost-linear time algorithm for computing a minimum cover of Q by disks that are contained in P. We then generalize the algorithm so that it can compute a minimum cover of Q by homothets of any fixed compact convex set ${\cal O}$ of constant description complexity that are contained in P. This improves previous results of Katz and Morgenstern [Lecture Notes in Comput. Sci. 5664, 2009, pp. 447–458]. We also consider the minimum disk-cover problem when Q is contained in a (sufficiently narrow) annulus and present a nearly linear algorithm for this case, too.

Motivated by an application in computational geometry, we consider a novel variant of the problem of efficiently maintaining a forest of dynamic rooted trees. This variant includes an operation that merges two tree paths. In contrast to the standard problem, in which a single operation can only add or delete one arc, one merge can add and delete up to a linear number of arcs. In spite of this, we develop three different methods that need only polylogarithmic time per operation. The first method extends a solution of Farach and Thorup [1998] for the special case of paths. Each merge takes O (log 2 n ) amortized time on an n -node forest and each standard dynamic tree operation takes O (log n ) time; the latter bound is amortized, worst case, or randomized depending on the underlying data structure. For the special case that occurs in the motivating application, in which arbitrary arc deletions (cuts) do not occur, we give a method that takes O (log n ) time per operation, including merging. This is best possible in a model of computation with an Ω( n log n ) lower bound for sorting n numbers, since such sorting can be done in O ( n ) tree operations. For the even-more-special case in which there are no cuts and no parent queries, we give a method that uses standard dynamic trees as a black box: each mergeable tree operation becomes a constant number of standard dynamic tree operations. This third method can also be used in the motivating application, but only by changing the algorithm in the application. Each of our three methods needs different analytical tools and reveals different properties of dynamic trees.

The best known upper bound on the number of topological changes in the Delaunay triangulation of a set of moving points in ℜ2 is (nearly) cubic, even if each point is moving with a fixed velocity. We introduce the notion of a stable Delaunay graph (SDG in short), a dynamic subgraph of the Delaunay triangulation, that is less volatile in the sense that it undergoes fewer topological changes and yet retains many useful properties of the full Delaunay triangulation. SDG is defined in terms of a parameter ± > 0, and consists of Delaunay edges pq for which the (equal) angles at which p and q see the corresponding Voronoi edge epq are at least ±. We prove several interesting properties of SDG and describe two kinetic data structures for maintaining it. Both structures use O*(n) storage. They process O*(n2) events during the motion, each in O*(1) time, provided that the points of P move along algebraic trajectories of bounded degree; the O*(·) notation hides multiplicative factors that are polynomial in 1/± and polylogarithmic in n. The first structure is simpler but the dependency on 1/± in its performance is higher.

We present a simple randomized scheme for triangulating a set P of n points in the plane, and construct a kinetic data structure which maintains the triangulation as the points of P move continuously along piecewise algebraic trajectories of constant description complexity. Our triangulation scheme experiences an expected number of O(n2βs+2(n) log2 n) discrete changes, and handles them in a manner that satisfies all the standard requirements from a kinetic data structure: compactness, efficiency, locality and responsiveness. Here s is the maximum number of times where any specific triple of points of P can become collinear, βs+2(q) = λs+2(q)/q, and λs+2(q) is the maximum length of Davenport-Schinzel sequences of order s + 2 on n symbols. Thus, compared to the previous solution of Agarwal et al. [4], we achieve a (slightly) improved bound on the number of discrete changes in the triangulation. In addition, we believe that our scheme is simpler to implement and analyze.

We show that the number of geometric permutations of an arbitrary collection of n pairwise disjoint convex sets in Rd, for d ≥ 3, is O(n2d-3log n), improving Wenger's 20 years old bound of O(n2d-2).

We study envy-free mechanisms for scheduling tasks on unrelated machines (agents) that approximately minimize the makespan. For indivisible tasks, we put forward an envy-free poly-time mechanism that approximates the minimal makespan to within a factor of O(log m), where m is the number of machines. We also show a lower bound of γ(log m / log log m). This improves the recent result of Mu'alem [22] who give an upper bound of (m+1)/2, and a lower bound of 2-1/m. For divisible tasks, we show that there always exists an envy-free poly-time mechanism with optimal makespan. Finally, we demonstrate how our mechanism for envy free makespan minimization can be interpreted as a market clearing problem.

We consider in this paper a popular class of recommender systems that are based on Collaborative Filtering (CF for short). CF is the process of predicting customer ratings to items based on previous ratings of (similar) users to (similar) items, and is typically used by a single organization, using its own customer ratings.

We consider online algorithms to label the nodes of an XML tree which is subject to insertions and deletions of nodes. The labeling is done such that (1) each node is assigned a label immediately when it is inserted and this label remains unchanged, and (2) from a pair of labels alone, one can decide whether one node is an ancestor of the other. This problem arises in the context of XML databases that support queries on the structure of the documents as well as on the changes made to the documents over time. We consider here the length of the assigned labels. We prove lower bounds on the length of labels which satisfy these requirements and provide labeling algorithms that match these bounds (up to a constant factor). We also consider the same problem when “clues” that provide guarantees on possible future insertions are given together with newly inserted nodes. Such clues can be derived from the DTD/XML Schema or from statistics on similar XML trees. We present algorithms that use the clues to assign shorter labels. We also prove that the length of our labels is close to the minimum possible.

We establish a bound of $O(n^2k^{1+\varepsilon})$, for any $\varepsilon>0$, on the combinatorial complexity of the set $\mathcal{T}$ of line transversals of a collection $\mathcal{P}$ of k convex polyhedra in $\mathbb{R}^3$ with a total of n facets, and we present a randomized algorithm which computes the boundary of $\mathcal{T}$ in comparable expected time. Thus, when $k\ll n$, the new bounds on the complexity (and construction cost) of $\mathcal{T}$ improve upon the previously best known bounds, which are nearly cubic in n. To obtain the above result, we study the set $\mathcal{T}_{\ell_0}$ of line transversals which emanate from a fixed line $\ell_0$, establish an almost tight bound of $O(nk^{1+\varepsilon})$ on the complexity of $\mathcal{T}_{\ell_0}$, and provide a randomized algorithm which computes $\mathcal{T}_{\ell_0}$ in comparable expected time. Slightly improved combinatorial bounds for the complexity of $\mathcal{T}_{\ell_0}$ and comparable improvements in the cost of constructing this set are established for two special cases, both assuming that the polyhedra of $\mathcal{P}$ are pairwise disjoint: the case where $\ell_0$ is disjoint from the polyhedra of $\mathcal{P}$, and the case where the polyhedra of $\mathcal{P}$ are unbounded in a direction parallel to $\ell_0$. Our result is related to the problem of bounding the number of geometric permutations of a collection $\mathcal{C}$ of k pairwise-disjoint convex sets in $\mathbb{R}^3$, namely, the number of distinct orders in which the line transversals of $\mathcal{C}$ visit its members. We obtain a new partial result on this problem.

From a high volume stream of weighted items, we want to maintain a generic sample of a certain limited size k that we can later use to estimate the total weight of arbitrary subsets. This is the classic context of on-line reservoir sampling, thinking of the generic sample as a reservoir. We present an efficient reservoir sampling scheme, VarOptk, that dominates all previous schemes in terms of estimation quality. VarOptk provides variance optimal unbiased estimation of subset sums. More precisely, if we have seen n items of the stream, then for any subset size m, our scheme based on k samples minimizes the average variance over all subsets of size m. In fact, the optimality is against any off-line scheme with k samples tailored for the concrete set of items seen. In addition to optimal average variance, our scheme provides tighter worst-case bounds on the variance of particular subsets than previously possible. It is efficient, handling each new item of the stream in O(log k) time, which is optimal even on the word RAM. Finally, it is particularly well suited for combination of samples from different streams in a distributed setting.

We establish a bound of O(n2k1+∊), for any ∊ > 0, on the combinatorial complexity of the set Ƭ of line transversals of a collection of k convex polyhedra in ℝ3 with a total of n facets, and present a randomized algorithm which computes the boundary of Ƭ in comparable expected time. Thus, when k ≪ n, the new bounds on the complexity (and construction cost) of Ƭ improve upon the previously best known bounds, which are nearly cubic in n. To obtain the above result, we study the set Ƭℓ0 of line transversals which emanate from a fixed line ℓ0, establish an almost tight bound of O(nk1+∊) on the complexity of Ƭℓ0, and provide a randomized algorithm which computes Ƭℓ0 in comparable expected time. Slightly improved combinatorial bounds for the complexity of Ƭℓ0, and comparable improvements in the cost of constructing this set, are established for two special cases, both assuming that the polyhedra of are pairwise disjoint: the case where ℓ0 is disjoint from the polyhedra of , and the case where the polyhedra of are unbounded in a direction parallel to ℓ0.

Chazelle (JACM 47(6), 2000) devised an approximate meldable priority queue data structure, called Soft Heaps, and used it to obtain the fastest known deterministic comparison-based algorithm for computing minimum spanning trees, as well as some new algorithms for selection and approximate sorting problems. If n elements are inserted into a collection of soft heaps, then up to ∊n of the elements still contained in these heaps, for a given error parameter ∊, may be corrupted, i.e., have their keys artificially increased. In exchange for allowing these corruptions, each soft heap operation is performed in O(log-) amortized time. Chazelle's soft heaps are derived from the binomial heaps data structure in which each priority queue is composed of a collection of binomial trees. We describe a simpler and more direct implementation of soft heaps in which each priority queue is composed of a collection of standard binary trees. Our implementation has the advantage that no clean-up operations similar to the ones used in Chazelle's implementation are required. We also present a concise and unified potential-based amortized analysis of the new implementation.

A coreset of a point set P is a small weighted set of points that captures some geometric properties of $P$. Coresets have found use in a vast host of geometric settings. We forge a link between coresets, and differentially private sanitizations that can answer any number of queries without compromising privacy. We define the notion of private coresets, which are simultaneously both coresets and differentially private, and show how they may be constructed. We first show that the existence of a small coreset with low generalized sensitivity (i.e., replacing a single point in the original point set slightly affects the quality of the coreset) implies (in an inefficient manner) the existence of a private coreset for the same queries. This greatly extends the works of Blum, Ligett, and Roth [STOC 2008] and McSherry and Talwar [FOCS 2007]. We also give an efficient algorithm to compute private coresets for k-median and k-mean queries in Red, immediately implying efficient differentially private sanitizations for such queries. Following McSherry and Talwar, this construction also gives efficient coalition proof (approximately dominant strategy) mechanisms for location problems. Unlike coresets which only have a multiplicative approximation factor, we prove that private coresets must have an additive error. We present a new technique for showing lower bounds on this error.

Many data sets occur as unaggregated data sets , where multiple data points are associated with each key. In the aggregate view of the data, the weight of a key is the sum of the weights of data points associated with the key. Examples are measurements of IP packet header streams, distributed data streams produced by events registered by sensor networks, and Web page or multimedia requests to context distribution servers. We aim to combine sampling and aggregation to provide accurate and efficient summaries of the aggregate view. However, data points are scattered in time or across multiple servers and hence aggregation is subject to resource constraints on the size of summaries that can be stored or transmitted. We develop a summarization framework for unaggregated data where summarization is a scalable and composable operator, and as such, can be tailored to meet resource constraints. Our summaries support unbiased estimates of the weight of subpopulations of keys specified using arbitrary selection predicates. While we prove that under such scenarios there is no variance optimal scheme, our estimators have the desirable properties that the variance is progressively closer to the minimum possible when applied to a "more" aggregated data set. An extensive evaluation using synthetic and real data sets shows that our summarization framework outperforms all existing schemes for this fundamental problem, even for the special and well-studied case of data streams.

Many data sources are naturally modeled by multiple weight assignments over a set of keys: snapshots of an evolving database at multiple points in time, measurements collected over multiple time periods, requests for resources served at multiple locations, and records with multiple numeric attributes. Over such vector-weighted data we are interested in aggregates with respect to one set of weights, such as weighted sums, and aggregates over multiple sets of weights such as the L 1 difference. Sample-based summarization is highly effective for data sets that are too large to be stored or manipulated. The summary facilitates approximate processing queries that may be specified after the summary was generated. Current designs, however, are geared for data sets where a single scalar weight is associated with each key. We develop a sampling framework based on coordinated weighted samples that is suited for multiple weight assignments and obtain estimators that are orders of magnitude tighter than previously possible. We demonstrate the power of our methods through an extensive empirical evaluation on diverse data sets ranging from IP network to stock quotes data.

We present randomized algorithms for online conflict-free coloring (CF in short) of points in the plane, with respect to halfplanes, congruent disks, and nearly-equal axis-parallel rectangles. In all three cases, the coloring algorithms use O (log n ) colors, with high probability. We also present a deterministic algorithm for online CF coloring of points in the plane with respect to nearly-equal axis-parallel rectangles, using O (log 3 n ) colors. This is the first efficient (i.e, using polylog( n ) colors) deterministic online CF coloring algorithm for this problem.

We consider the dynamic vertical ray shooting problem against horizontal disjoint segments, that is, the task of maintaining a dynamic set S of n nonintersecting horizontal line segments in the plane under a query that reports the first segment in S intersecting a vertical ray from a query point. We develop a linear-size structure that supports queries, insertions, and deletion in O (log n ) worst-case time. Our structure works in the comparison model on a random access machine.

Many datasets, including market basket data, text or hypertext documents, and measurement data collected in different nodes or time periods, are modeled as a collection of sets over a ground set of (weighted) items. We consider the problem of estimating basic aggregates such as the weight or selectivity of a subpopulation of the items. We extend classic summarization techniques based on sampling to this scenario when we have multiple sets and selection predicates based on membership in particular sets.

We construct weak ε-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1/r-nets of size O(rα(r)), where α(r) denotes the inverse Ackermann function. For point sets along the moment curve in ℝ d we construct weak 1/r-nets of size r · 2 poly(α(r)) , where the degree of the polynomial in the exponent depends (quadratically) on d. Our constructions result from a reduction to a new problem, which we call stabbing interval chains with j-tuples. Given the range of integers N = [1, n], an interval chain of length k is a sequence of k consecutive, disjoint, nonempty intervals contained in N. A j-tuple $\bar{P}$ = (p1,…,pj) is said to stab an interval chain C = I 1 …I k if each p i falls on a different interval of C. The problem is to construct a small-size family Z of j-tuples that stabs all k-interval chains in N. Let z (j) k (n) denote the minimum size of such a family Z. We derive almost-tight upper and lower bounds for z (j) k (n) for every fixed j; our bounds involve functions α m (n) of the inverse Ackermann hierarchy. Specifically, we show that for j = 3 we have z (3) k (n) = Θ(nα $\lfloor$k/2$\rfloor$ (n)) for all k ≥ 6. For each j≥4, we construct a pair of functions Pʹ j (m), Qʹ j (m), almost equal asymptotically, such that z (j) Pʹ j(m)(n) = O(nα m (n)) and z (j) Qʹ j(m)(n) = Ω(nα m (n)).

Summaries of massive data sets support approximate query processing over the original data. A basic aggregate over a set of records is the weight of subpopulations specified as a predicate over records' attributes. Bottom-k sketches are a powerful summarization format of weighted items that includes priority sampling [22], and the classic weighted sampling without replacement. They can be computed efficiently for many representations of the data including distributed databases and data streams and support coordinated and all-distances sketches. We derive novel unbiased estimators and confidence bounds for subpopulation weight. Our rank conditioning (RC) estimator is applicable when the total weight of the sketched set cannot be computed by the summarization algorithm without a significant use of additional resources (such as for sketches of network neighborhoods) and the tighter subset conditioning (SC) estimator that is applicable when the total weight is available (sketches of data streams). Our estimators are derived using clever applications of the Horvitz-Thompson estimator (that is not directly applicable to bottom- k sketches). We develop efficient computational methods and conduct performance evaluation using a range of synthetic and real data sets. We demonstrate considerable benefits of the SC estimator on larger subpopulations (over all other estimators); of the RC estimator (over existing estimators for weighted sampling without replacement); and of our confidence bounds (over all previous approaches).

We present linear-time algorithms for the classic problem of finding dominators in a flowgraph, and for several other problems whose solutions require evaluating a function defined on paths in a tree. Although all these problems had linear-time solutions previously, our algorithms are simpler, in some cases substantially. Our improvements come from three new ideas: a refined analysis of path compression that gives a linear bound if the compressions favor certain nodes; replacement of random-access table look-up by a radix sort; and a more careful partitioning of a tree into easily managed parts. In addition to finding dominators, our algorithms find nearest common ancestors off-line, verify and construct minimum spanning trees, do interval analysis of a flowgraph, and build the component tree of a weighted tree. Our algorithms do not require the power of a random-access machine; they run in linear time on a pointer machine. The genesis of our work was the discovery of a subtle error in the analysis of a previous allegedly linear-time algorithm for finding dominators. That algorithm was an attempt to simplify a more complicated algorithm, which itself was intended to correct errors in a yet earlier algorithm. Our work provides a systematic study of the subtleties in the dominators problem, the techniques needed to solve it in linear time, and the range of application of the resulting methods. We have tried to make our techniques as simple and as general as possible and to understand exactly how earlier approaches to the dominators problem were either incorrect or overly complicated.

Let P be a set of n points in $\mathbb{R}^d$, so that each point is colored by one of C given colors. We present algorithms for preprocessing P into a data structure that efficiently supports queries of the following form: Given an axis-parallel box Q, count the number of distinct colors of the points of $P\cap Q$. We present a general and relatively simple solution that has a polylogarithmic query time and worst-case storage about $O(n^d)$. It is based on several interesting structural properties of the problem, which we establish here. We also show that for random inputs, the data structure requires almost linear expected storage. We then present several techniques for achieving space-time tradeoff. In $\mathbb{R}^2$, the most efficient solution uses fast matrix multiplication in the preprocessing stage. In higher dimensions we use simpler tradeoff mechanisms, which behave just as well. We give a reduction from matrix multiplication to the off-line version of problem, which shows that in $\mathbb{R}^2$ our time-space tradeoffs are reasonably sharp, in the sense that improving them substantially would improve the best exponent of matrix multiplication. Finally, we present a generalized matrix multiplication problem and show its intimate relation to counting colors in boxes in higher dimension.

We present simple, fully dynamic and kinetic data structures, which are variants of a dynamic two-dimensional range tree, for maintaining the closest pair and all nearest neighbors for a set of n moving points in the plane; insertions and deletions of points are also allowed. If no insertions or deletions take place, the structure for the closest pair uses O ( n log n ) space, and processes O ( n 2 β s +2 ( n )log n ) critical events, each in O (log 2 n ) time. Here s is the maximum number of times where the distances between any two specific pairs of points can become equal, β s ( q ) = λ s ( q )/ q , and λ s ( q ) is the maximum length of Davenport-Schinzel sequences of order s on q symbols. The dynamic version of the problem incurs a slight degradation in performance: If m ≥ n insertions and deletions are performed, the structure still uses O ( n log n ) space, and processes O ( mn β s +2( n )log 3 n ) events, each in O (log 3 n ) time. Our kinetic data structure for all nearest neighbors uses O ( n log 2 n ) space, and processes O ( n 2 β 2 s +2 ( n )log 3 n ) critical events. The expected time to process all events is O ( n 2 β s +2 2 ( n ) log 4 n ), though processing a single event may take Θ( n ) expected time in the worst case. If m ≥ n insertions and deletions are performed, then the expected number of events is O ( mn β 2 s +2 ( n ) log 3 n ) and processing them all takes O ( mn β 2 s +2 ( n ) log 4 n ). An insertion or deletion takes O ( n ) expected time.

The Fibonacci heap was devised to provide an especially efficient implementation of Dijkstra's shortest path algorithm. Although asyptotically efficient, it is not as fast in practice as other heap implementations. Expanding on ideas of Høyer [1995], we describe three heap implementations (two versions of thin heaps and one of thick heaps ) that have the same amortized efficiency as Fibonacci heaps, but need less space and promise better practical performance. As part of our development, we fill in a gap in Høyer's analysis.

Let C be a set of n axis-aligned cubes in R3, and let U(C) denote the union of C. We present an algorithmthat can compute the volume of U(C) in time O(n4/3 log n). The previously best known algorithm, by Overmars and Yap, computes the volume of the union ofany n axis-aligned boxes in R3 in O(n3/2log n) time.

Statistical summaries of traffic in IP networks are at the heart of network operation and are used to recover information on the traffic of arbitrary subpopulations of flows. It is therefore of great importance to collect the most accurate and informative summaries given the router's resource constraints. Cisco's sampled NetFlow, based on aggregating a sampled packet stream into flows, is the most widely deployed such system.

A Bottom-sketch is a summary of a set of items with nonnegative weights that supports approximate query processing. A sketch is obtained by associating with each item in a ground set an independent random rank drawn from a probability distribution that depends on the weight of the item and including the k items with smallest rank value.

IP packet streams consist of multiple interleaving IP flows. Statistical summaries of these streams, collected for different measurement periods, are used for characterization of traffic, billing, anomaly detection, inferring traffic demands, configuring packet filters and routing protocols, and more. While queries are posed over the set of flows, the summarization algorithmis applied to the stream of packets. Aggregation of traffic into flows before summarization requires storage of per-flow counters, which is often infeasible. Therefore, the summary has to be produced over the unaggregated stream.

A Bottom-k sketch is a summary of a set of items with nonnegative weights. Each such summary allows us to compute approximate aggregates over the set of items. Bottom-k sketches are obtained by associating with each item in a ground set an independent random rank drawn from a probability distribution that depends on the weight of the item. For each subset of interest, the bottom-k sketch is the set of the k minimum ranked items and their ranks. Bottom-k sketches have numerous applications. We develop and analyze data structures and estimators for bottom-k sketches to facilitate their deployment. We develop novel estimators and algorithms that show that they are a superior alternative to other sketching methods in both efficiency of obtaining the sketches and the accuracy of the estimates derived from the sketches.

We consider an online version of the conflict‐free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict‐free, in the sense that in every interval I there is a color that appears exactly once in I. We present deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring $\Omega(\sqrt{n})$ colors in the worst case. We then derive two efficient variants of this simple algorithm. The first is deterministic and uses $O(\log^2 n)$ colors, and the second is randomized and uses $O(\log n)$ colors with high probability. We also show that the $O(\log^2 n)$ bound on the number of colors used by our deterministic algorithm is tight on the worst case. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order and present an incomplete analysis that indicates that, with high probability, it uses only $O(\log n)$ colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case.

We study the point-to-point shortest path problem in a setting where preprocessing is allowed. We improve the reach-based approach of Gutman [17] in several ways. In particular, we introduce a bidirectional version of the algorithm that uses implicit lower bounds and we add shortcut arcs to reduce vertex reaches. Our modifications greatly improve both preprocessing and query times. The resulting algorithm is as fast as the best previous method, due to Sanders and Schultes [28]. However, our algorithm is simpler and combines in a natural way with A* search, which yields significantly better query times.

In a Batched Colored Intersection Searching Problem (CI), one is given a set of n geometric objects (of a certain class). Each object is colored by one of c colors, and the goal is to report all pairs of colors (c1,c2) such that there are two objects, one colored c1 and one colored c2, that intersect each other. We also consider the bipartite version of the problem, where we are interested in intersections between objects of one class with objects of another class (e.g., points and halfspaces).In a Sparse Rectangular Matrix Multiplication Problem (SRMM), one is given an n1×n2 matrix A and an n2×n3 matrix B, each containing at most m non-zero entries, and the goal is to compute their product AB.In this paper we present a technique for solving CI problems over a wide range of classes of geometric objects. The basic idea is first to use some decomposition method, such as geometric cuttings, to represent the intersection graph of the objects as a union of bi-cliques. Then, in each of these bi-cliques, contract all vertices of the same color. Finally, use an algorithm for sparse matrix multiplication (adapted from Yuster and Zwick [20]) to compute the union of the bi-cliques. We apply the technique to segments in R1, to segments in R2, to points and halfplanes in R2, and, more generally, to points and halfspaces in Rd, for any fixed d. However, the technique extends to colored intersection searching in any class (or pair of classes) of geometric objects of constant descriptive complexity.In particular, using our technique we obtain an algorithm that reports all the pairs of intersecting colors for n points and n halfplanes in R2, that are colored by c colors, in O(n4/3c0.46) time when n ≥ c1.44, and in O(n1.04c0.9 + c2) time when n≤c1.44.The algorithms that we give for CI use the algorithm for SRMM as a black box, which means that any improved algorithm for SRMM immediately leads to an improved algorithm for all colored intersection problems that our method applies to. We also show that the complexity of computing all intersecting colors in a set of segments on the real line is identical, up to a polylogarithmic multiplicative factor, to the complexity of SRMM with the appropriate parameters.

Top-k queries are desired aggregation operations on data sets. Examples of queries on network data include the top 100 source AS's, top 100 ports, or top Domain names over IP packets or over IP flow records. Since the complete dataset is often not available or not feasible to examine, we are interested in processing top-k queries from samples.

We consider the following problem. Given a rooted tree T, label the nodes of T in the most compact way such that, given the labels of two nodes u and v, one can determine in constant time, by looking only at the labels, whether u is ancestor of v. The best known labeling scheme is rather straightforward and uses labels of length at most $2\log_2 n$ bits each, where n is the number of nodes in the tree. Our main result in this paper is a labeling scheme with maximum label length $\log_2 n + \Oh(\sqrt{\log n})$. Our motivation for studying this problem is enhancing the performance of web search engines. In the context of this application each indexed document is a tree, and the labels of all trees are maintained in main memory. Therefore even small improvements in the maximum label length are important.

Given a polyhedral terrain T with n vertices, the two-watchtower problem for T calls for finding two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases) lie on T, and whose top endpoints guard T, in the sense that each point on T is visible from at least one of them. In this paper we present the following results for the two-watchtower problem in R2 and R3: (1) We show that the discrete two-watchtowers problem in R2, where the bases are constrained to lie at vertices of T, can be solved in O(n2 log4n) time, significantly improving previous solutions. The algorithm works, without increasing its asymptotic running time, even if, one of the towers is allowed to be placed anywhere on T. (2) We show that the continuous two-watchtower problem in R2, where the bases can lie anywhere on T, can be solved in O(n3α(n)log3n) time, again significantly improving previous results. (3) Still in R2, we show that the continuous version of the problem of guarding a finite set P ⊂ T of m points by two watchtowers of smallest height can be solved in O(mn log4n) time. (4) The discrete version of the two-watchtower problem in R3 can be solved in O(n11/3 polylog(n)) time; this is the first nontrivial result for this problem in R3.

We study an extension of the "standard" learning models to settings where observing the value of an attribute has an associated cost (which might be different for different attributes). Our model assumes that the correct classification is given by some target function f from a class of functions cal F; most of our results discuss the ability to learn a clause (an OR function of a subset of the variables) in various settings:Offline: We are given both the function f and the distribution D that is used to generate an input x. The goal is to design a strategy to decide what attribute of x to observe next so as to minimize the expected evaluation cost of f(x). (In this setting there is no "learning" to be done but only an optimization problem to be solved; this problem to be NP-hard and hence approximation algorithms are presented.)Distributional online: We study two types of "learning" problems; one where the target function f is known to the learner but the distribution D is unknown (and the goal is to minimize the expected cost including the cost that stems from "learning" D), and the other where f is unknown (except that f∈cal F) but D is known (and the goal is to minimize the expected cost while limiting the prediction error involved in "learning" f).Adversarial online: We are given f, however the inputs are selected adversarially. The goal is to compare the learner's cost to that of the best fixed evaluation order (i.e., we analyze the learner's performance by a competitive analysis).

A directed multigraph is said to be d -regular if the indegree and outdegree of every vertex is exactly d . By Hall's theorem, one can represent such a multigraph as a combination of at most n 2 cycle covers, each taken with an appropriate multiplicity. We prove that if the d -regular multigraph does not contain more than ⌊ d/2 ⌋ copies of any 2-cycle then we can find a similar decomposition into n 2 pairs of cycle covers where each 2-cycle occurs in at most one component of each pair. Our proof is constructive and gives a polynomial algorithm to find such a decomposition. Since our applications only need one such a pair of cycle covers whose weight is at least the average weight of all pairs, we also give an alternative, simpler algorithm to extract a single such pair.This combinatorial theorem then comes handy in rounding a fractional solution of an LP relaxation of the maximum Traveling Salesman Problem (TSP) problem. The first stage of the rounding procedure obtains two cycle covers that do not share a 2-cycle with weight at least twice the weight of the optimal solution. Then we show how to extract a tour from the 2 cycle covers, whose weight is at least 2/3 of the weight of the longest tour. This improves upon the previous 5/8 approximation with a simpler algorithm. Utilizing a reduction from maximum TSP to the shortest superstring problem, we obtain a 2.5-approximation algorithm for the latter problem, which is again much simpler than the previous one.For minimum asymmetric TSP, the same technique gives two cycle covers, not sharing a 2-cycle, with weight at most twice the weight of the optimum. Assuming triangle inequality, we then show how to obtain from this pair of cycle covers a tour whose weight is at most 0.842 log 2 n larger than optimal. This improves upon a previous approximation algorithm with approximation guarantee of 0.999 log 2 n . Other applications of the rounding procedure are approximation algorithms for maximum 3-cycle cover (factor 2/3, previously 3/5) and maximum asymmetric TSP with triangle inequality (factor 10/13, previously 3/4).

Corrigendum to ACM Transactions on Programming Languages and Systems , 20(6):1265--1296, 1998.

Data items are often associated with a location in which they are present or collected, and their relevance or influence decays with their distance. Aggregate values over such data thus depend on the observing location, where the weight given to each item depends on its distance from that location. We term such aggregation spatially-decaying.Spatially-decaying aggregation has numerous applications: Individual sensor nodes collect readings of an environmental parameter such as contamination level or parking spot availability; the nodes then communicate to integrate their readings so that each location obtains contamination level or parking availability in its neighborhood. Nodes in a p2p network could use a summary of content and properties of nodes in their neighborhood in order to guide search. In graphical databases such as Web hyperlink structure, properties such as subject of pages that can reach or be reached from a page using link traversals provide information on the page.We formalize the notion of spatially-decaying aggregation and develop efficient algorithms for fundamental aggregation functions, including sums and averages, random sampling, heavy hitters, quantiles, and Lp norms.

In many Internet applications, requests for a certain object are routed bottom-up over a tree where the root of the tree is the node containing the object. When an object becomes popular, the root node of the tree may become a hot-spot. Therefore, many applications allow intermediate nodes to acquire the ability to serve the requests, for example, by caching the object. We call such distinguished nodes primed. We propose and analyze different algorithms where nodes decide when to become primed; these algorithms balance the maximum load on a node and the number of primed nodes. Many applications require both fully distributed decisions and smooth convergence to a stable set of primed nodes. We first present optimal algorithms which require communication across the tree. We then consider the natural previously proposed {\sc threshold} algorithm, where a node becomes primed when the incoming flow of requests exceeds a threshold. We show examples where {\sc threshold} exhibits undesirable behavior during convergence. Finally, we propose another fully distributed algorithm, {\sc gap}, which converges gracefully.

A directed multigraph is said to be d-regular if the indegree and outdegree of every vertex is exactly d. By Hall's theorem one can represent such a multigraph as a combination of at most n/sup 2/ cycle covers each taken with an appropriate multiplicity. We prove that if the d-regular multigraph does not contain more than /spl lfloor/d/2/spl rfloor/ copies of any 2-cycle then we can find a similar decomposition into 0(n/sup 2/) pairs of cycle covers where each 2-cycle occurs in at most one component of each pair. Our proof is constructive and gives a polynomial algorithm to find such decomposition. Since our applications only need one such a pair of cycle covers whose weight is at least the average weight of all pairs, we also give a simpler algorithm to extract a single such pair. This combinatorial theorem then comes handy in rounding a fractional solution of an LP relaxation of the maximum and minimum TSP problems. For maximum TSP, we obtain a tour whose weight is at least 2/3 of the weight of the longest tour, improving a previous 5/8 approximation. For minimum TSP we obtain a tour whose weight is at most 0.842log/sub 2/ n times the optimal, improving a previous 0.999log/sub 2/ n approximation. Utilizing a reduction from maximum TSP to the shortest superstring problem we obtain a 2.5-approximation algorithm for the latter problem which is again much simpler than the previous one. Other applications of the rounding procedure are approximation algorithms for maximum 3-cycle cover (factor 2/3, previously 3/5) and maximum asymmetric TSP with triangle inequality (factor 10/13, previously 3/4 ).

The success of a P2P file-sharing network highly depends on the scalability and versatility of its search mechanism. Two particularly desirable search features are scope (ability to find infrequent items) and support for partial-match queries (queries that contain typos or include a subset of keywords). While centralized-index architectures (such as Napster) can support both these features, existing decentralized architectures seem to support at most one: prevailing unstructured P2P protocols (such as Gnutella and FastTrack) deploy a "blind" search mechanism where the set of peers probed is unrelated to the query; thus they support partial-match queries but have limited scope. On the other extreme, the recently-proposed distributed hash tables (DHTs) such as CAN and CHORD, couple index location with the item's hash value, and thus have good scope but can not effectively support partial-match queries. Another hurdle to DHTs deployment is their tight control of the overlay structure and the information (part of the index) each peer maintains, which makes them more sensitive to failures and frequent joins and disconnects. We develop a new class of decentralized P2P architectures. Our design is based on unstructured architectures such as gnutella and FastTrack, and retains many of their appealing properties including support for partial match queries, and relative resilience to peer failures. Yet, we obtain orders of magnitude improvement in the efficiency of locating rare items. Our approach exploits associations inherent in human selections to steer the search process to peers that are more likely to have an answer to the query. We demonstrate the potential of associative search using models, analysis, and simulations.

A recent seminal result of Racke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Racke's construction is not polynomial time. We give a polynomial time construction that guarantee's Racke's bounds, and more generally gives the true optimal ratio for any network.

We present efficient data structures to maintain dynamic set of rectangles, each with priority assigned to it, such that we can efficiently find the rectangle of maximum priority containing a query point. Our data structures support insertions and deletions of rectangles. In one dimension, when rectangles are intervals, our most efficient data structure supports queries and insertions in O(log n) time, deletions in O(log n loglog n) time and requires linear space. When intervals are guaranteed to be nonoverlapping (but one can be nested within the other) we obtain a simpler data structure that supports all operations in O(log n) time.

We study the patterns and predictability of Internet end-to-end service degradations, where a degradation is a significant deviation of the round-trip time (RTT) between a client and a server. We use simultaneous RTT measurements collected from several locations to a large representative set of Web sites and study the duration and extent of degradations. We combine these measurements with border gateway protocol cluster information to learn on the location of the cause. We evaluate a number of predictors based upon hidden Markov models and Markov models. Predictors typically exhibit a tradeoff between two types of errors, false positives (incorrect degradation prediction) and false negatives (a degradation is not predicted). The costs of these error types is application dependent, but we capture the entire spectrum using a precision versus recall tradeoff. Using this methodology, we learn what information is most valuable for prediction (recency versus quantity of past measurements). Surprisingly, we also conclude that predictors that utilize history in a very simple way perform as well as more sophisticated ones. One important application of prediction is gateway selection, which is applicable when a local-area network is connected through multiple gateways to one or several Internet service provider. Gateway selection can boost reliability and survivability by selecting for each connection the (hopefully) best gateway. We show that gateway selection using our predictors can reduce the degradations to half of that obtained by routing all the connections through the best gateway.

Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs and yet require fast query answering. We propose a new data structure for representing all distances in a graph. The data structure is distributed in the sense that it may be viewed as assigning labels to the vertices, such that a query involving vertices u and v may be answered using only the labels of u and v. Our labels are based on 2-hop covers of the shortest paths, or of all paths, in a graph. For shortest paths, such a cover is a collection S of shortest paths such that, for every two vertices u and v, there is a shortest path from u to v that is a concatenation of two paths from S. We describe an efficient algorithm for finding an almost optimal 2-hop cover of a given collection of paths. Our approach is general and can be applied to directed or undirected graphs, exact or approximate shortest paths, or to reachability queries. We study the proposed data structure using a combination of theoretical and experimental means. We implemented our algorithm and checked the size of the resulting data structure on several real-life networks from different application areas. Our experiments show that the total size of the labels is typically not much larger than the network itself, and is usually considerably smaller than an explicit representation of the transitive closure of the network.

We study the patterns and predictability of Internet End-to-End service degradations, where a degradation is a significant deviation of the round trip time between a client and a server. We use simultaneous RTT measurements collected from several locations to a large representative set of Web sites and study the duration and extent of degradations. We combine these measurements with BGP cluster information to learn on the location of the cause.We evaluate a number of predictors based upon Hidden Markov Models and Markov Models. Predictors typically exhibit a tradeoff between two types of errors, false positives (incorrect degradation prediction) and false negatives (a degradation is not predicted). The costs of these error-types is application dependent, but we capture the entire spectrum using a precision versus recall tradeoff. Using this methodology, we learn what information is most valuable for prediction (recency versus quantity of past measurements). Surprisingly, we also conclude that predictors that utilize history in a very simple way perform as well as more sophisticated ones.One important application of prediction is gateway selection, which is applicable when a LAN is connected through multiple gateways to one or several ISP's. Gateway selection can boost reliability and survivability by selecting for each connection the (hopefully) best gateway. We show that gateway selection using our predictors can reduce the degradations to half of that obtained by routing all the connections through the best gateway.

We present algorithms to label the nodes of an XML tree which is subject to insertions and deletions of nodes. The labeling is done such that (1) we label each node immediately when it is inserted and this label remains unchanged, and (2) from a pair of labels alone, we can decide whether one node is an ancestor of the other. This problem arises in the context of XML databases that support queries on the structure of the documents as well us on the changes made to the documents over time. We prove that our algorithms assign the shortest possible labels (up to a constant factor) which satisfy these requirements.We also consider the same problem when "clues" that provide guarantees on possible future insertions are given together with newly inserted nodes. Such clues can be derived from the DTD or from statistics on similar XML trees. We present algorithms that use the clues to assign shorter labels. We also prove that the length of our labels is close to the minimum possible.

Several papers describe linear time algorithms to preprocess a tree, such that one can answer subsequent nearest common ancestor queries in constant time. Here, we survey these algorithms and related results. A common idea used by all the algorithms for the problem is that a solution for complete binary trees is straightforward. Furthermore, for complete binary trees we can easily solve the problem in a distributed way by labeling the nodes of the tree such that from the labels of two nodes alone one can compute the label of their nearest common ancestor. Whether it is possible to distribute the data structure into short labels associated with the nodes is important for several applications such as routing. Therefore, related labeling problems have received a lot of attention recently.Previous optimal algorithms for nearest common ancestor queries work using some mapping from a general tree to a complete binary tree. However, it is not clear how to distribute the data structures obtained using these mappings. We conclude our survey with a new simple algorithm that labels the nodes of a rooted tree such that from the labels of two nodes alone one can compute in constant time the label of their nearest common ancestor. The labels assigned by our algorithm are of size $O(\log n)$ bits where $n$ is the number of nodes in the tree. The algorithm runs in $O(n)$ time.

In the classical meldable heap data type we maintain an item-disjoint collection of heaps under the operations find-min, insert, delete, decrease-key, and meld. In the usual definition decrease-key and delete get the item and the heap containing it as parameters. We consider the modified problem where decrease-key and delete get only the item but not the heap containing it. We show that for this problem one of the operations find-min, decrease-key, or meld must take non-constant time. This is in contrast with the original data type in which data structures supporting all these three operations in constant time are known (both in an amortized and a worst-case setting).To establish our results for meldable heaps we consider a weaker version of the union-find problem that is of independent interest, which we call Boolean union-find. In the Boolean union-find problem the find operation is a binary predicate that gets an item x and a set A and answers positively if and only if χ ε A. We prove that the lower bounds which hold for union-find in the cell probe model hold for Boolean union-find as well.We also suggest new heap data structures implementing the modified meldable heap data type that are based on redundant binary counters. Our data structures have good worst-case bounds. The best of our data structures matches the worst-case lower bounds which we establish for the problem. The simplest of our data structures is an interesting generalization of binomial queues.

Web content caches are often placed between end-users and origin servers as a mean to reduce server load, network usage, and ultimately, user-perceived latency. Cached objects typically have associated expiration times, after which they are considered stale and must be validated with a remote server (origin or another cache) before they can be sent to a client. A considerable fraction of cache hits involve stale copies that turned out to be current. These validations of current objects have small message size, but nonetheless, often induce latency comparable to full-fledged cache misses. Thus, the functionality of caches as a latency-reducing mechanism highly depends not only on content availability but also on its freshness. We propose policies for caches to preactively validate selected objects as they become stale, and thus allow for more client requests to be processed locally. Our policies operate within the existing protocols and exploit natural properties of request patterns such as frequency and recency. We evaluated and compared different policies using trace-based simulations.

A new general theory about restoration of network paths is first introduced. The theory pertains to restoration of shortest paths in a network following failure, e.g., we prove that a shortest path in a network after removing k edges is the concatenation of at most k + 1 shortest paths in the original network.

The Web is a distributed system, where data is stored and disseminated from both origin servers and caches. Origin servers provide the most up-to-date copy whereas caches store and serve copies that had been cached for a while. Origin servers do not maintain per-client state, and weak-consistency of cached copies is maintained by the origin server attaching to each copy an expiration time. Typically, the lifetime-duration of an object is fixed, and as a result, a copy fetched directly from its origin server has maximum time-to-live (TTL) whereas a copy obtained through a cache has a shorter TTL since its age (elapsed time since fetched from the origin) is deducted from its lifetime duration. Thus, a cache that is served from a cache would incur a higher miss-rate than a cache served from origin servers. Similarly, a high-level cache would receive more requests from the same client population than an origin server would have received. As Web caches are often served from other caches (e.g., proxy and reverse-proxy caches), age emerges as a performance factor. Guided by a formal model and analysis, we use different inter-request time distributions and trace-based simulations to explore the effect of age for different cache settings and configurations. We also evaluate the effectiveness of frequent pre-term refreshes by higher-level caches as a means to decrease client misses. Beyond Web content distribution, our conclusions generally apply to systems of caches deploying expiration-based consistency.

User-perceived latency is recognized as the central performance problem in the Web. We systematically measure factors contributing to this latency, across several locations. Our study reveals that DNS query times, TCP connection establishment, and start-of-session delays at HTTP servers, more so than transmission time, are major causes of long waits. Wait due to these factors also afflicts high-bandwidth users and has detrimental effect on perceived performance. We propose simple techniques that address these factors: (i) pre-resolving host-names (pre-performing DNS lookup); (ii) pre-connecting (prefetching TCP connections prior to issuance of HTTP request); and (iii) pre-warming (sending a "dummy" HTTP HEAD request to Web servers). Trace-based simulations demonstrate a potential to reduce perceived latency dramatically. Our techniques surpass document prefetching in performance improvement per bandwidth used and can be used with non-prefetchable URL. Deployment of these techniques at Web browsers or proxies does not require protocol modifications or the cooperation of other entities. Applicable servers can be identified, for example, by analyzing hyperlinks. Bandwidth overhead is minimal, and so is processing overhead at the user's browser. We propose scalable deployment solutions to control the potential overhead to proxies and particularly to Web servers.

Motivated by Web applications, we recently introduced the following theoretical model for connection-caching: Each host on a network can maintain (cache) a limited number of connections to other hosts. A message can be transmitted from one host to another only if the connection between these two hosts is open, i.e., it is cached by both endpoints. If a message request arrives and the respective connection is not open (a miss), the connection needs to be established and certain activation cost is incurred. The establishment of the new connection may force the termination (eviction) of other connections at each endpoint.

We consider the problem of maintaining persistent lists subject to concatenation and to insertions and deletions at both ends. Updates to a persistent data structure are nondestructive---each operation produces a new list incorporating the change, while keeping intact the list or lists to which it applies. Although general techniques exist for making data structures persistent, these techniques fail for structures that are subject to operations, such as catenation, that combine two or more versions. In this paper we develop a simple implementation of persistent double-ended queues (deques) with catenation that supports all deque operations in constant amortized time. Our implementation is functional if we allow memoization.

Caching web pages at proxies and in web servers' memories can greatly enhance performance. Proxy caching is known to reduce network load and both proxy and server caching can significantly decrease latency. web caching problems have different properties than traditional operating systems caching, and cache replacement can benet by recognizing and exploiting these differences. We address two aspects of the predictability of traffic patterns: the overall load experienced by large proxy and web servers, and the distinct access patterns of individual pages. We formalize the notion of "cache load" under various replacement policies, including LRU and LFU, and demonstrate that the trace of a large proxy server exhibits regular load. Predictable load allows for improved design, analysis, and experimental evaluation of replacement policies. We provide a simple and (near)-optimal replacement policy when each page request has an associated distribution function on the next request time of the page. Without the predictable load assumption, no such online policy is possible and it is known that even obtaining an offline optimum is hard. For experiments, predictable load enables comparing and evaluating cache replacement policies using partial traces, containing requests made to only a subset of the pages. Our results are based on considering a simpler caching model which we call the interval caching model. We relate traditional and interval-caching policies under predictable load, and derive (near)-optimal replacement policies from their optimal interval-caching counterparts.

Article Connection caching Share on Authors: Edith Cohen AT&T Labs-Research, 180 Park Avenue, Florham Park, NJ AT&T Labs-Research, 180 Park Avenue, Florham Park, NJView Profile , Haim Kaplan AT&T Labs-Research, 180 Park Avenue, Florham Park, NJ AT&T Labs-Research, 180 Park Avenue, Florham Park, NJView Profile , Uri Zwick Tel-Aviv University, Tel-Aviv 69978, Israel Tel-Aviv University, Tel-Aviv 69978, IsraelView Profile Authors Info & Claims STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of ComputingMay 1999 Pages 612–621https://doi.org/10.1145/301250.301416Online:01 May 1999Publication History 9citation221DownloadsMetricsTotal Citations9Total Downloads221Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We consider the problem of testing the uniqueness of maximum matchings, both in the unweighted and in the weighted case. For the unweighted case, we have two results. First, given a graph with n vertices and m edges, we can test whether the graph has a unique perfect matching, and find it if it exists, in O(m log^4 n) time. This algorithm uses a recent dynamic connectivity algorithm and an old result of Kotzig characterizing unique perfect matchings in terms of bridges. For the special case of...

We give a quadratic time algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its faster implementation by Berman and Hannenhalli. The algorithm is conceptually simple and does not require special data structures. Our study also considerably simplifies the combinatorial structures used by the analysis.

We study the parameterized complexity of three NP-hard graph completion problems. The minimum fill-in problem asks if a graph can be triangulated by adding at most k edges. We develop O(ck m) and O(k2mn+f(k)) algorithms for this problem on a graph with n vertices and m edges. Here f(k) is exponential in k and the constants hidden by the big-O notation are small and do not depend on k. In particular, this implies that the problem is fixed-parameter tractable (FPT). The proper interval graph completion problem, motivated by molecular biology, asks if a graph can be made proper interval by adding no more than k edges. We show that the problem is FPT by providing a simple search-tree-based algorithm that solves it in O(ck m)-time. Similarly, we show that the parameterized version of the strongly chordal graph completion problem is FPT by giving an O(ck m log n)-time algorithm for it. All of our algorithms can actually enumerate all possible k-completions within the same time bounds.

We present two new data structure tools—disjoint set union with bottom-up linking, and pointer-based radix sort—and combine them with bottom-level microtrees to devise the first linear-time pointer-machine algorithms for off-line least common ancestors, minimum spanning tree (MST) verification, randomized MST construction, and computing dominators in a flowgraph.

We present a new linear-time algorithm to find the immediate dominators of all vertices in a flowgraph. Our algorithm is simpler than previous linear-time algorithms: rather than employ complicated data structures, we combine the use of microtrees and memoization with new observations on a restricted class of path compressions. We have implemented our algorithm, and we report experimental results that show that the constant factors are low. Compared to the standard, slightly superlinear algorithm of Lengauer and Tarjan, which has much less overhead, our algorithm runs 10-20% slower on real flowgraphs of reasonable size and only a few percent slower on very large flowgraphs.

No abstract available.

We present a randomized procedure for rounding fractional perfect matchings to (integral) matchings. If the original fractional matching satisfies any linear inequality, then with high probability, the new matching satisfies that linear inequality in an approximate sense. This extends the well-known LP rounding procedure of Raghavan and Thompson (1987), which is usually used to round fractional solutions of linear programs. It also solves an open problem of Luby and Nisan (1993) ("Design an NC procedure for converting near-optimum fractional matchings to near-optimum matchings.") We use the rounding procedure to design n/sup 0(logn//spl epsiv/(2)/) time algorithms for the following: (i) an additive approximation to the 0-1 Quadratic Assignment problem (QAP); (ii) a (1+E)-approximation for "dense" instances of many well-known NP-hard problems, including (an optimization formulation of) GRAPH-ISOMORPHISM, MIN-CUT-LINEAR-ARRANGEMENT, MAX-ACYCLIC-SUBGRAPH, MIN-LINEAR-ARRANGEMENT, and BETWEENNESS. (A "dense" graph is one in which the number of edges is /spl Omega/(n/sup 2/); denseness for the other problems is defined in an analogous way).

tice, especially for applications that require worst-case time bounds or persistence.

We study two related problems motivated by molecular biology. • Given a graph G and a constant k, does there exist a supergraph $G'$ of G that is a unit interval graph and has clique size at most k? • Given a graph G and a proper k-coloring c of G, does there exist a supergraph $G'$ of G that is properly colored by c and is a unit interval graph? We show that those problems are polynomial for fixed k. On the other hand, we prove that the first problem is equivalent to deciding if the bandwidth of G is at most $k - 1$. Hence, it is NP-hard and $W[t]$-hard for all t. We also show that the second problem is $W[1]$-hard for all t-hard. This implies that for fixed k, both of the problems are unlikely to have an $O(n^\alpha )$ algorithm, where a is a constant independent of k. A central tool in our study is a new graph-theoretic parameter closely related to pathwidth. An unexpected useful consequence is the equivalence of this parameter to the bandwidth of the graph.

Article Persistent lists with catenation via recursive slow-down Share on Authors: Haim Kaplan Department of Computer Science, Princeton University, Princeton, NJ Department of Computer Science, Princeton University, Princeton, NJView Profile , Robert E. Tarjan Department of Computer Science, Princeton University, Princeton, NJ Department of Computer Science, Princeton University, Princeton, NJView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 93–102https://doi.org/10.1145/225058.225090Online:29 May 1995Publication History 31citation523DownloadsMetricsTotal Citations31Total Downloads523Last 12 Months13Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We study the parameterized complexity of several NP-Hard graph completion problems: The minimum fill-in problem is to decide if a graph can be triangulated by adding at most k edges. We develop an O(k/sup 5/ mn+f(K)) algorithm for the problem on a graph with n vertices and m edges. In particular, this implies that the problem is fixed parameter tractable (FPT). proper interval graph completion problems, motivated by molecular biology, ask for adding edges in order to obtain a proper interval graph, so that a parameter in that graph does not exceed k. We show that the problem is FPT when k is the number of added edges. For the problem where k is the clique size, we give an O(f(k)n/sup k-1/) algorithm, so it is polynomial for fixed k. On the other hand, we prove its hardness in the parameterized hierarchy, so it is probably not FPT. Those results are obtained even when a set of edges which should not be added is given. That set can be given either explicitly or by a proper vertex coloring which the added edges should respect.>