• ### Pairing heaps: the forward variant(1709.01152)

June 21, 2018 cs.DS
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 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} \cdot 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.
• ### Spanners for Directed Transmission Graphs(1601.07798)

May 15, 2018 cs.CG
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.
• ### Differentially Private k-Means with Constant Multiplicative Error(1804.08001)

April 21, 2018 cs.DS
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 rates over the previous state-of-the-art. In addition, in the local model, our algorithm significantly reduces the number of needed interactions. 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.
• ### Hierarchical Reinforcement Learning: Approximating Optimal Discounted TSP Using Local Policies(1803.04674)

March 13, 2018 cs.AI, cs.LG, stat.ML
In this work, we provide theoretical guarantees for reward decomposition in deterministic MDPs. Reward decomposition is a special case of Hierarchical Reinforcement Learning, that allows one to learn many policies in parallel and combine them into a composite solution. Our approach builds on mapping this problem into a Reward Discounted Traveling Salesman Problem, and then deriving approximate solutions for it. In particular, we focus on approximate solutions that are local, i.e., solutions that only observe information about the current state. Local policies are easy to implement and do not require substantial computational resources as they do not perform planning. While local deterministic policies, like Nearest Neighbor, are being used in practice for hierarchical reinforcement learning, we propose three stochastic policies that guarantee better performance than any deterministic policy.
• ### Representations of Sparse Distributed Networks: A Locality-Sensitive Approach(1802.09515)

Feb. 26, 2018 cs.DS
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 $\alpha$ at all times, the BF algorithm supports edge updates in $O(\log n)$ amortized update time, while keeping the maximum outdegree in the graph bounded by $O(\alpha)$. 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 \emph{temporary} blowup of the maximum outdegree, following edge insertions. Although BF eventually reduces all outdegrees to $O(\alpha)$, local memory usage at the vertices, which is 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(\alpha)$ at all times, without hurting any of its other properties, and present an efficient distributed implementation of the modified algorithm. This provides the \emph{first} representation of distributed networks in which the local memory usage at all 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 are no local memory constraints, we 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 \emph{global} nature: An insertion of an edge $(u,v)$ may trigger changes in the orientations of edges that are far away from $u$ and $v$. We suggest an alternative \emph{local} scheme, which does not guarantee any outdegree bound on the vertices, yet is just as efficient as the BF scheme for various applications.
• ### Voronoi diagrams on planar graphs, and computing the diameter in deterministic $\tilde{O}(n^{5/3})$ time(1704.02793)

Feb. 25, 2018 cs.CG, cs.DS
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'17), 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 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].
• ### Selection from heaps, row-sorted matrices and $X+Y$ using soft heaps(1802.07041)

Feb. 20, 2018 cs.DS
We use soft heaps to obtain simpler optimal algorithms for selecting the $k$-th smallest item, and the set of~$k$ smallest items, from a heap-ordered tree, from a collection of sorted lists, and from $X+Y$, where $X$ and $Y$ are two unsorted sets. Our results match, and in some ways extend and improve, classical results of Frederickson (1993) and Frederickson and Johnson (1982). In particular, for selecting the $k$-th smallest item, or the set of~$k$ smallest items, from a collection of~$m$ sorted lists we obtain a new optimal "output-sensitive" algorithm that performs only $O(m+\sum_{i=1}^m \log(k_i+1))$ comparisons, where $k_i$ is the number of items of the $i$-th list that belong to the overall set of~$k$ smallest items.
• ### Stabbing pairwise intersecting disks by five points(1801.03158)

Jan. 9, 2018 cs.CG
We present an $O(n)$ expected time algorithm and an $O(n \log n)$ deterministic time algorithm to find a set of five points that stab a set of $n$ pairwise intersecting disks in the plane. We also give a simple construction with 13 pairwise intersecting disks that cannot be stabbed by three points.
• ### Clustering over Multi-Objective Samples: The one2all Sample(1706.03607)

June 12, 2017 cs.DS, cs.LG
Clustering is a fundamental technique in data analysis. Consider data points $X$ that lie in a (relaxed) metric space (where the triangle inequality can be relaxed by a constant factor). Each set of points $Q$ ({\em centers}) defines a clustering of $X$ according to the closest center with {\em cost} $V(Q)=\sum_{x\in X} d_{xQ}$. This formulation generalizes classic $k$-means clustering, which uses squared distances. Two basic tasks, parametrized by $k \geq 1$, are {\em cost estimation}, which returns (approximate) $V(Q)$ for queries $Q$ such that $|Q|=k$ and {\em clustering}, which returns an (approximate) minimizer of $V(Q)$ of size $|Q|=k$. With very large data sets $X$, we seek efficient constructions of small summaries that allow us to efficiently approximate clustering costs over the full data. We present a novel data reduction tool based on multi-objective probability-proportional-to-size (pps) sampling: Our {\em one2all} construction inputs any set of centers $M$ and efficiently computes a sample of size $O(|M|)$ from which we can tightly estimate the clustering cost $V(Q)$ for {\em any} $Q$ that has at least a fraction of the clustering cost of $M$. For cost queries, we apply one2all to a bicriteria approximation to obtain a sample of size $O(k\epsilon^{-2})$ for all $|Q|=k$. For clustering, we propose a wrapper that applies a black-box algorithm to a sample and tests clustering quality over $X$, adaptively increasing the sample size. Our approach exploits the structure of the data to provide quality guarantees through small samples, without the use of typically much larger worst-case-size summaries.
• ### Routing in Unit Disk Graphs(1510.01072)

March 24, 2017 cs.CG, cs.DS
Let $S \subset \mathbb{R}^2$ be a set of $n$ sites. The unit disk graph $\text{UD}(S)$ on $S$ has vertex set $S$ and an edge between two distinct sites $s,t \in S$ if and only if $s$ and $t$ have Euclidean distance $|st| \leq 1$. A routing scheme $R$ for $\text{UD}(S)$ assigns to each site $s \in S$ a label $\ell(s)$ and a routing table $\rho(s)$. For any two sites $s, t \in S$, the scheme $R$ must be able to route a packet from $s$ to $t$ in the following way: given a current site $r$ (initially, $r = s$), a header $h$ (initially empty), and the label $\ell(t)$ of the target, the scheme $R$ consults the routing table $\rho(r)$ to compute a neighbor $r'$ of $r$, a new header $h'$, and the label $\ell(t')$ of an intermediate target $t'$. (The label of the original target may be stored at the header $h'$.) The packet is then routed to $r'$, and the procedure is repeated until the packet reaches $t$. The resulting sequence of sites is called the routing path. The stretch of $R$ is the maximum ratio of the (Euclidean) length of the routing path produced by $R$ and the shortest path in $\text{UD}(S)$, over all pairs of distinct sites in $S$. For any given $\varepsilon > 0$, we show how to construct a routing scheme for $\text{UD}(S)$ with stretch $1+\varepsilon$ using labels of $O(\log n)$ bits and routing tables of $O(\varepsilon^{-5}\log^2 n \log^2 D)$ bits, where $D$ is the (Euclidean) diameter of $\text{UD}(S)$. The header size is $O(\log n \log D)$ bits.
• ### Polylogarithmic Bounds on the Competitiveness of Min-cost (Bipartite) Perfect Matching with Delays(1610.05155)

Oct. 17, 2016 cs.DS
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 points (the connection cost), and the sum of the waiting times of the requests (the delay cost). We present an algorithm with a competitive ratio of $O(\log n)$, which improves the upper bound of $O(\log^2n+\log\Delta)$ of Emek et al, by removing the dependence on $\Delta$, 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 $\Omega(\sqrt{\log n})$ 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. The problem of Min-cost Bipartite Perfect Matching with Delays (MBPMD) is the same as MPMD except that every request is either positive or negative, and requests can be matched only if they have opposite polarity. We prove an upper bound of $O(\log n)$ and a lower bound of $\Omega(\log^{1/3}n)$ on the competitive ratio of MBPMD with a more involved analysis.
• ### The Discrete and Semi-continuous Fr\'echet Distance with Shortcuts via Approximate Distance Counting and Selection Techniques(1310.5245)

Sept. 7, 2016 cs.CG
The \emph{Fr\'echet distance} is a well studied similarity measures between curves. The \emph{discrete Fr\'echet distance} is an analogous similarity measure, defined for a sequence $A$ of $m$ points and a sequence $B$ of $n$ points, where the points are usually sampled from input curves. In this paper we consider a variant, called the \emph{discrete Fr\'echet distance with shortcuts}, which captures the similarity between (sampled) curves in the presence of outliers. For the \emph{two-sided} case, where shortcuts are allowed in both curves, we give an $O((m^{2/3}n^{2/3}+m+n)\log^3 (m+n))$-time algorithm for computing this distance. When shortcuts are allowed only in one noise-containing curve, we give an even faster randomized algorithm that runs in $O((m+n)^{6/5+\varepsilon})$ expected time, for any $\varepsilon>0$. 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$ and an interval $I$, we develop an algorithm that decides whether the number of pairs $(x,y)\in A\times B$ whose distance ${\rm 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 contains 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\'echet 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 for computing the semi-continuous Fr\'echet distance with one-sided shortcuts.
• ### Approximating the $k$-Level in Three-Dimensional Plane Arrangements(1601.04755)

May 17, 2016 cs.CG
• ### Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications(1604.03654)

June 4, 2019 cs.CG, cs.DS
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$-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)$ storage, and requires polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat and Sharir that required $O(n^\varepsilon)$ time for an update and $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)$ 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.
• ### Reachability Oracles for Directed Transmission Graphs(1601.07797)

Nov. 3, 2019 cs.CG
Let $P \subset \mathbb{R}^d$ be a set of $n$ points in $d$ dimensions 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 there is an edge from $p$ to $q$ if and only if $|pq| \leq r_p$, for any $p, q \in P$. A reachability oracle is a data structure that decides for any two vertices $p, q \in G$ whether $G$ has a path from $p$ to $q$. The quality of the oracle is measured by the space requirement $S(n)$, the query time $Q(n)$, and the preprocessing time. For transmission graphs of one-dimensional point sets, we can construct in $O(n \log n)$ time an oracle with $Q(n) = O(1)$ and $S(n) = O(n)$. For planar point sets, the ratio $\Psi$ between the largest and the smallest associated radius turns out to be an important parameter. We present three data structures whose quality depends on $\Psi$: the first works only for $\Psi < \sqrt{3}$ and achieves $Q(n) = O(1)$ with $S(n) = O(n)$ and preprocessing time $O(n\log n)$; the second data structure gives $Q(n) = O(\Psi^3 \sqrt{n})$ and $S(n) = O(\Psi^3 n^{3/2})$; the third data structure is randomized with $Q(n) = O(n^{2/3}\log^{1/3} \Psi \log^{2/3} n)$ and $S(n) = O(n^{5/3}\log^{1/3} \Psi \log^{2/3} n)$ and answers queries correctly with high probability.
• ### Hollow Heaps(1510.06535)

Oct. 22, 2015 cs.DS
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 by far the simplest structure to achieve this. 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.
• ### The Temp Secretary Problem(1507.01732)

July 8, 2015 cs.DS
We consider a generalization of the secretary problem where contracts are temporary, and for a fixed duration. This models online hiring of temporary employees, or online auctions for re-usable resources. The problem is related to the question of Finding a large independent set in a random unit interval graph.
• ### Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees(1503.08528)

June 26, 2015 cs.SI, cs.LG
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 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.
• ### Stable Delaunay Graphs(1504.06851)

April 26, 2015 math.MG, cs.CG
Let $P$ be a set of $n$ points in $\mathrm{R}^2$, and let $\mathrm{DT}(P)$ denote its Euclidean Delaunay triangulation. We introduce the notion of an edge of $\mathrm{DT}(P)$ being {\it stable}. Defined in terms of a parameter $\alpha>0$, a Delaunay edge $pq$ is called $\alpha$-stable, if the (equal) angles at which $p$ and $q$ see the corresponding Voronoi edge $e_{pq}$ are at least $\alpha$. A subgraph $G$ of $\mathrm{DT}(P)$ is called {\it $(c\alpha, \alpha)$-stable Delaunay graph} ($\mathrm{SDG}$ in short), for some constant $c \ge 1$, if every edge in $G$ is $\alpha$-stable and every $c\alpha$-stable of $\mathrm{DT}(P)$ is in $G$. We show that if an edge is stable in the Euclidean Delaunay triangulation of $P$, then it is also a stable edge, though for a different value of $\alpha$, in the Delaunay triangulation of $P$ under any convex distance function that is sufficiently close to the Euclidean norm, and vice-versa. In particular, a $6\alpha$-stable edge in $\mathrm{DT}(P)$ is $\alpha$-stable in the Delaunay triangulation under the distance function induced by a regular $k$-gon for $k \ge 2\pi/\alpha$, and vice-versa. Exploiting this relationship and the analysis in~\cite{polydel}, we present a linear-size kinetic data structure (KDS) for maintaining an $(8\alpha,\alpha)$-$\mathrm{SDG}$ as the points of $P$ move. If the points move along algebraic trajectories of bounded degree, the KDS processes nearly quadratic events during the motion, each of which can processed in $O(\log n)$ time. Finally, we show that a number of useful properties of $\mathrm{DT}(P)$ are retained by $\mathrm{SDG}$ of $P$.
• ### A faster algorithm for the discrete Fr\'echet distance under translation(1501.03724)

Jan. 15, 2015 cs.CG
The discrete Fr\'echet distance is a useful similarity measure for comparing two sequences of points $P=(p_1,\ldots, p_m)$ and $Q=(q_1,\ldots,q_n)$. In many applications, the quality of the matching can be improved if we let $Q$ undergo some transformation relative to $P$. In this paper we consider the problem of finding a translation of $Q$ that brings the discrete Fr\'echet distance between $P$ and $Q$ to a minimum. We devise an algorithm that computes the minimum discrete Fr\'echet distance under translation in $\mathbb{R}^2$, and runs in $O(m^3n^2(1+\log(n/m))\log(m+n))$ time, assuming $m\leq n$. This improves a previous algorithm of Jiang et al.~\cite{JXZ08}, which runs in $O(m^3n^3 \log(m + n))$ time.
• ### On the Complexity of Hub Labeling(1501.02492)

Jan. 11, 2015 cs.DS
Hub Labeling (HL) is a data structure for distance oracles. Hierarchical HL (HHL) is a special type of HL, that received a lot of attention from a practical point of view. However, theoretical questions such as NP-hardness and approximation guarantee for HHL algorithms have been left aside. In this paper we study HL and HHL from the complexity theory point of view. We prove that both HL and HHL are NP-hard, and present upper and lower bounds for the approximation ratios of greedy HHL algorithms used in practice. We also introduce a new variant of the greedy HHL algorithm and a proof that it produces small labels for graphs with small highway dimension.
• ### Epsilon-Nets for Halfspaces Revisited(1410.3154)

Oct. 12, 2014 cs.CG
Given a set $P$ of $n$ points in $\mathbb{R}^3$, we show that, for any $\varepsilon >0$, there exists an $\varepsilon$-net of $P$ for halfspace ranges, of size $O(1/\varepsilon)$. We give five proofs of this result, which are arguably simpler than previous proofs \cite{msw-hnlls-90, cv-iaags-07, pr-nepen-08}. We also consider several related variants of this result, including the case of points and pseudo-disks in the plane.
• ### Fibonacci Heaps Revisited(1407.5750)

July 22, 2014 cs.DS
The Fibonacci heap is a classic data structure that supports deletions in logarithmic amortized time and all other heap operations in O(1) amortized time. We explore the design space of this data structure. We propose a version with the following improvements over the original: (i) Each heap is represented by a single heap-ordered tree, instead of a set of trees. (ii) Each decrease-key operation does only one cut and a cascade of rank changes, instead of doing a cascade of cuts. (iii) The outcomes of all comparisons done by the algorithm are explicitly represented in the data structure, so none are wasted. We also give an example to show that without cascading cuts or rank changes, both the original data structure and the new version fail to have the desired efficiency, solving an open problem of Fredman. Finally, we illustrate the richness of the design space by proposing several alternative ways to do cascading rank changes, including a randomized strategy related to one previously proposed by Karger. We leave the analysis of these alternatives as intriguing open problems.
• ### Probe Scheduling for Efficient Detection of Silent Failures(1302.0792)

June 19, 2014 cs.NI, cs.DS
Most discovery systems for silent failures work in two phases: a continuous monitoring phase that detects presence of failures through probe packets and a localization phase that pinpoints the faulty element(s). This separation is important because localization requires significantly more resources than detection and should be initiated only when a fault is present. We focus on improving the efficiency of the detection phase, where the goal is to balance the overhead with the cost associated with longer failure detection times. We formulate a general model which unifies the treatment of probe scheduling mechanisms, stochastic or deterministic, and different cost objectives - minimizing average detection time (SUM) or worst-case detection time (MAX). We then focus on two classes of schedules. {\em Memoryless schedules} -- a subclass of stochastic schedules which is simple and suitable for distributed deployment. We show that the optimal memorlyess schedulers can be efficiently computed by convex programs (for SUM objectives) or linear programs (for MAX objectives), and surprisingly perhaps, are guaranteed to have expected detection times that are not too far off the (NP hard) stochastic optima. {\em Deterministic schedules} allow us to bound the maximum (rather than expected) cost of undetected faults, but like stochastic schedules, are NP hard to optimize. We develop novel efficient deterministic schedulers with provable approximation ratios. An extensive simulation study on real networks, demonstrates significant performance gains of our memoryless and deterministic schedulers over previous approaches. Our unified treatment also facilitates a clear comparison between different objectives and scheduling mechanisms.
• ### Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions(1404.4851)

April 18, 2014 math.MG, cs.CG, cs.DS
Let $P$ be a set of $n$ points and $Q$ a convex $k$-gon in ${\mathbb R}^2$. We analyze in detail the topological (or discrete) changes in the structure of the Voronoi diagram and the Delaunay triangulation of $P$, under the convex distance function defined by $Q$, as the points of $P$ move along prespecified continuous trajectories. Assuming that each point of $P$ moves along an algebraic trajectory of bounded degree, we establish an upper bound of $O(k^4n\lambda_r(n))$ on the number of topological changes experienced by the diagrams throughout the motion; here $\lambda_r(n)$ is the maximum length of an $(n,r)$-Davenport-Schinzel sequence, and $r$ is a constant depending on the algebraic degree of the motion of the points. Finally, we describe an algorithm for efficiently maintaining the above structures, using the kinetic data structure (KDS) framework.