Ioannis Lamprou, Ioannis Sigalas, Vassilis Zissimopoulos
2019-07-15
We consider the \emph{budgeted} version of the classical \emph{connected dominating set} problem (BCDS). Given a graph
and an integer budget , we seek to find a connected subset of at most vertices which maximizes the number of dominated vertices in . We answer an open question in [Khuller, Purohit, and Sarpatwar,\ \emph{SODA 2014}] and thus we improve over the previous approximation. Our algorithm provides a approximation guarantee by employing an improved method for enforcing connectivity and performing tree decompositions. We also consider the \emph{edge-vertex domination} variant, where an edge dominates its endpoints and all vertices neighboring them. In \emph{budgeted edge-vertex domination} (BEVD), we are given a graph , and a budget , and we seek to find a, not necessarily connected, subset of edges such that the number of dominated vertices in is maximized. We prove there exists a -approximation algorithm. Also, for any , we present a -inapproximability result by a gap-preserving reduction from the \emph{maximum coverage} problem. We notice that, in the connected case, BEVD becomes equivalent to BCDS. Moreover, we examine the ``dual'' \emph{partial edge-vertex domination} (PEVD) problem, where a graph and a quota are given. The goal is to select a minimum-size set of edges to dominate at least vertices in . In this case, we present a -approximation algorithm by a reduction to the \emph{partial cover} problem.
Jasjeet Dhaliwal, Kyle Hambrook
2019-07-15
We provide recovery guarantees for compressible signals that have been corrupted with noise and extend the framework introduced in [1] to defend neural networks against
-norm and -norm attacks. Concretely, for a signal that is approximately sparse in some transform domain and has been perturbed with noise, we provide guarantees for accurately recovering the signal in the transform domain. We can then use the recovered signal to reconstruct the signal in its original domain while largely removing the noise. Our results are general as they can be directly applied to most unitary transforms used in practice and hold for both -norm bounded noise and -norm bounded noise. In the case of -norm bounded noise, we prove recovery guarantees for Iterative Hard Thresholding (IHT) and Basis Pursuit (BP). For the case of -norm bounded noise, we provide recovery guarantees for BP. These guarantees theoretically bolster the defense framework introduced in [1] for defending neural networks against adversarial inputs. Finally, we experimentally demonstrate this defense framework using both IHT and BP against the One Pixel Attack [21], Carlini-Wagner and attacks [3], Jacobian Saliency Based attack [18], and the DeepFool attack [17] on CIFAR-10 [12], MNIST [13], and Fashion-MNIST [27] datasets. This expands beyond the experimental demonstrations of [1].
Michal Wlodarczyk
2019-07-15
In the
-Steiner Orientation problem we are given a mixed graph, that is, with both directed and undirected edges, and a set of terminal pairs. The goal is to find an orientation of the undirected edges that maximizes the number of terminal pairs for which there is a path from the source to the sink. The problem is known to be W[1]-hard when parameterized by and hard to approximate up to some constant for FPT algorithms assuming Gap-ETH. On the other hand, no approximation better than is known. We show that -Steiner Orientation admits no sublogarithmic approximation algorithm, even with a parameterized running time, assuming W[1] FPT. To obtain this result, we reduce the problem to itself via a hashing-based gap amplification technique, which turns out useful even outside of the FPT paradigm. Precisely, we rule out any approximation ratio of the form for parameterized algorithms and for purely polynomial running time, under the same assumption. This constitutes a novel inapproximability result for polynomial time algorithms obtained via tools from the FPT theory. Moreover, we prove -Steiner Orientation to be W[1]-complete, what provides an example of a natural approximation task that is complete in a parameterized complexity class. Finally, we apply our technique to the maximization version of Directed Multicut and obtain a simple proof that the problem admits no FPT approximation with ratio (assuming W[1] FPT) and no polynomial-time approximation with ratio (assuming NP co-RP).
Adam Lev-Libfeld
2019-06-26
As demand for Real-Time applications rises among the general public, the importance of enabling large-scale, unbound algorithms to solve conventional problems with low to no latency is critical for product viability. Timer algorithms are prevalent in the core mechanisms behind operating systems, network protocol implementation, stream processing, and several database capabilities. This paper presents a field-tested algorithm for low latency, unbound range timer structure, based upon the well excepted Timing Wheel algorithm. Using a set of queues hashed by TTL, the algorithm allows for a simpler implementation, minimal overhead no overflow and no performance degradation in comparison to the current state of the algorithms under typical use cases.
Yijie Han
2016-12-10
We show, for the input
matrices and , where 's and 's are real numbers, after ~{O} time preprocessing for each vector and , the vector multiplication can be computed in ~{O} time. This enables the matrix multiplication of two matrices to be computed in ~{O} time. Here ~{O} for a constant .
J. Ian Munro, Gonzalo Navarro, Yakov Nekrich
2017-12-20
We introduce the first index that can be built in
time for a text of length , and can also be queried in time for a pattern of length . On an alphabet of size , our index uses bits, is built in deterministic time, and computes the number of occurrences of the pattern in time . Each such occurrence can then be found in time. By slightly increasing the space and construction time, to and , respectively, for any constant , we can find the pattern occurrences in time . We build on a novel text sampling based on difference covers, which enjoys properties that allow us efficiently computing longest common prefixes in constant time. We extend our results to the secondary memory model as well, where we give the first construction in I/Os of a data structure with suffix array functionality; this data structure supports pattern matching queries with optimal or nearly-optimal cost.
Mahdi Bozorg, Saber Salehkaleybar, Matin Hashemi
2019-07-15
The graph matching problem refers to recovering the node-to-node correspondence between two correlated graphs. A previous work theoretically showed that recovering is feasible in sparse Erdos-Renyi graphs if and only if the probability of having an edge between a pair of nodes in one of the graphs and also between the corresponding nodes in the other graph is in the order of
, where n is the number of nodes. In this paper, we propose a graph matching algorithm which obtains correct matching with high probability in Erdos-Renyi graphs for the region of without using a seed set of pre-matched node pairs as an input. The algorithm assigns structurally innovative features to high-degree nodes based on the tail of empirical degree distribution of their neighbor nodes. Then, it matches the high-degree nodes according to these features, and finally obtains a matching for the remaining nodes. We evaluate the performance of proposed algorithm in the regions of and . Experiments show that it outperforms previous works in both regions.
Caleb C. Levy, Robert E. Tarjan
2019-07-15
Consider the task of performing a sequence of searches in a binary search tree. After each search, an algorithm is allowed to arbitrarily restructure the tree, at a cost proportional to the amount of restructuring performed. The cost of an execution is the sum of the time spent searching and the time spent optimizing those searches with restructuring operations. This notion was introduced by Sleator and Tarjan in (JACM, 1985), along with an algorithm and a conjecture. The algorithm, Splay, is an elegant procedure for performing adjustments while moving searched items to the top of the tree. The conjecture, called "dynamic optimality," is that the cost of splaying is always within a constant factor of the optimal algorithm for performing searches. The conjecture stands to this day. In this work, we attempt to lay the foundations for a proof of the dynamic optimality conjecture.
Caleb C. Levy, Robert E. Tarjan
2019-07-15
Let
be a binary search tree. We prove two results about the behavior of the Splay algorithm (Sleator and Tarjan 1985). Our first result is that inserting keys into an empty binary search tree via splaying in the order of either 's preorder or 's postorder takes linear time. Our proof uses the fact that preorders and postorders are pattern-avoiding: i.e. they contain no subsequences that are order-isomorphic to and , respectively. Pattern-avoidance implies certain constraints on the manner in which items are inserted. We exploit this structure with a simple potential function that counts inserted nodes lying on access paths to uninserted nodes. Our methods can likely be extended to permutations that avoid more general patterns. Second, if is any other binary search tree with the same keys as and is weight-balanced (Nievergelt and Reingold 1973), then splaying 's preorder sequence or 's postorder sequence starting from takes linear time. To prove this, we demonstrate that preorders and postorders of balanced search trees do not contain many large "jumps" in symmetric order, and exploit this fact by using the dynamic finger theorem (Cole et al. 2000). Both of our results provide further evidence in favor of the elusive "dynamic optimality conjecture."
Robert E. Tarjan, Caleb C. Levy, Stephen Timmel
2018-06-18
We introduce the zip tree, a form of randomized binary search tree that integrates previous ideas into one practical, performant, and pleasant-to-implement package. A zip tree is a binary search tree in which each node has a numeric rank and the tree is (max)-heap-ordered with respect to ranks, with rank ties broken in favor of smaller keys. Zip trees are essentially treaps (Seidel and Aragon 1996), except that ranks are drawn from a geometric distribution instead of a uniform distribution, and we allow rank ties. These changes enable us to use fewer random bits per node. We perform insertions and deletions by unmerging and merging paths ("unzipping" and "zipping") rather than by doing rotations, which avoids some pointer changes and improves efficiency. The methods of zipping and unzipping take inspiration from previous top-down approaches to insertion and deletion (Stephenson 1980; Mart'inez and Roura 1998; Sprugnoli 1980). From a theoretical standpoint, this work provides two main results. First, zip trees require only
bits (with high probability) to represent the largest rank in an -node binary search tree; previous data structures require bits for the largest rank. Second, zip trees are naturally isomorphic to skip lists (Pugh 1990), and simplify the mapping of (Dean and Jones 2007) between skip lists and binary search trees.
