Energy is often the most constrained resource for battery-powered wireless devices, and most of the energy is often spent on transceiver usage (i.e., transmitting and receiving packets) rather than computation. In this article, we study the energy complexity of fundamental problems in several models of wireless radio networks. It turns out that energy complexity is very sensitive to whether the devices can generate random bits and their ability to detect collisions. We consider four collision detection models: Strong-CD (in which transmitters and listeners detect collisions), Sender-CD (in which only transmitters detect collisions), Receiver-CD (in which only listeners detect collisions), and No-CD (in which no one detects collisions). PubDate: Fri, 04 Oct 2019 00:00:00 GMT

Abstract: Hugo A. Akitaya, Radoslav Fulek, Csaba D. Tóth

We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding ϕ : G → M of a graph G into a 2-manifold M maps the vertices in V(G) to distinct points and the edges in E(G) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to the same point or overlapping arcs due to data compression or low resolution. This raises the computational problem of deciding whether a given map ϕ : G → M comes from an embedding. A map ϕ : G → M is a weak embedding if it can be perturbed into an embedding ψ ϵ : G → M with ‖ ϕ − ψ ϵ ‖ < ϵ for every ϵ> 0, where ‖.‖ is the unform norm. PubDate: Fri, 04 Oct 2019 00:00:00 GMT

We present a new locally differentially private algorithm for the heavy hitters problem that achieves optimal worst-case error as a function of all standardly considered parameters. Prior work obtained error rates that depend optimally on the number of users, the size of the domain, and the privacy parameter but depend sub-optimally on the failure probability. We strengthen existing lower bounds on the error to incorporate the failure probability and show that our new upper bound is tight with respect to this parameter as well. Our lower bound is based on a new understanding of the structure of locally private protocols. We further develop these ideas to obtain the following general results beyond heavy hitters. PubDate: Fri, 04 Oct 2019 00:00:00 GMT

Abstract: Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh

We consider the fundamental Matroid Theory problem of finding a circuit in a matroid containing a set T of given terminal elements. For graphic matroids, this corresponds to the problem of finding a simple cycle passing through a set of given terminal edges in a graph. The algorithmic study of the problem on regular matroids, a superclass of graphic matroids, was initiated by Gavenčiak, Král’, and Oum [ICALP’12], who proved that the case of the problem with ∣T∣ = 2 is fixed-parameter tractable (FPT) when parameterized by the length of the circuit. We extend the result of Gavenčiak, Král’, and Oum by showing that for regular matroids • the Minimum Spanning Circuit problem, deciding whether there is a circuit with at most ℓ elements containing T, is FPT parameterized by k = ℓ − ∣T∣ • the Spanning Circuit problem, deciding whether there is a circuit containing ∣T∣, is FPT ... PubDate: Fri, 04 Oct 2019 00:00:00 GMT

We introduce and study the problem Ordered Level Planarity, which asks for a planar drawing of a graph such that vertices are placed at prescribed positions in the plane and such that every edge is realized as a y-monotone curve. This can be interpreted as a variant of Level Planarity in which the vertices on each level appear in a prescribed total order. We establish a complexity dichotomy with respect to both the maximum degree and the level-width, that is, the maximum number of vertices that share a level. Our study of Ordered Level Planarity is motivated by connections to several other graph drawing problems. PubDate: Fri, 04 Oct 2019 00:00:00 GMT

Abstract: Marek Cygan, Łukasz Kowalik, Arkadiusz Socała

Given a traveling salesman problem (TSP) tour H in graph G, a k-move is an operation that removes k edges from H and adds k edges of G so that a new tour H′ is formed. The popular k-OPT heuristic for TSP finds a local optimum by starting from an arbitrary tour H and then improving it by a sequence of k-moves. Until 2016, the only known algorithm to find an improving k-move for a given tour was the naive solution in time O(nk). At ICALP’16, de Berg, Buchin, Jansen, and Woeginger showed an O(n⌊2k/3⌋+1)-time algorithm. We show an algorithm that runs in O(n(1/4+εk)k) time, where limk→ ∞ εk = 0. PubDate: Fri, 04 Oct 2019 00:00:00 GMT

Abstract: Christoph Hunkenschröder, Santosh Vempala, Adrian Vetta

We present a factor 4/3 approximation algorithm for the problem of finding a minimum 2-edge connected spanning subgraph of a given undirected multigraph. The algorithm is based upon a reduction to a restricted class of graphs. In these graphs, the approximation algorithm constructs a 2-edge connected spanning subgraph by modifying the smallest 2-edge cover. PubDate: Fri, 04 Oct 2019 00:00:00 GMT

For geometric optimization problems we often understand the computational complexity on a rough scale, but not very well on a finer scale. One example is the two-dimensional knapsack problem for squares. There is a polynomial time (1+ε)-approximation algorithm for it (i.e., a PTAS) but the running time of this algorithm is triple exponential in 1/ε, i.e., Ω (n221/ε). A double or triple exponential dependence on 1/ε is inherent in how this and other algorithms for other geometric problems work. In this article, we present an efficient PTAS (EPTAS) for knapsack for squares, i.e., a (1+ε)-approximation algorithm with a running time of Oε(1)ṡ nO(1). PubDate: Thu, 08 Aug 2019 00:00:00 GMT

Abstract: Massimo Cairo, Paul Medvedev, Nidia Obscura Acosta, Romeo Rizzi, Alexandru I. Tomescu

In this article, we consider the following problem. Given a directed graph G, output all walks of G that are sub-walks of all closed edge-covering walks of G. This problem was first considered by Tomescu and Medvedev (RECOMB 2016), who characterized these walks through the notion of omnitig. Omnitigs were shown to be relevant for the genome assembly problem from bioinformatics, where a genome sequence must be assembled from a set of reads from a sequencing experiment. Tomescu and Medvedev (RECOMB 2016) also proposed an algorithm for listing all maximal omnitigs, by launching an exhaustive visit from every edge. In this article, we prove new insights about the structure of omnitigs and solve several open questions about them. PubDate: Mon, 29 Jul 2019 00:00:00 GMT

We consider the fundamental problem of constructing fast circuits for the carry bit computation in binary addition. Up to a small additive constant, the carry bit computation reduces to computing an And-Or path, i.e., a formula of type t0 ∧ (t1 ∨ (t2 ∧ (… tm−1) …) or t0 ∨ (t1 ∧ (t2 ∨ (… tm−1) …). We present an algorithm that computes the fastest known Boolean circuit for an And-Or path with given arrival times a(t0), …, a(tm−1) for the input signals. Our objective function is delay, a natural generalization of depth with respect to arrival times. The maximum delay of the circuit we compute is log2 W + log2 log2m + log2 log2 log2 m + 4.3, where W := ∑i = 0m−1 2a(ti). PubDate: Thu, 25 Jul 2019 00:00:00 GMT

Abstract: Marcin Bienkowski, Jarosław Byrka, Marcin Mucha

We construct a deterministic 4-competitive algorithm for the online file migration problem, beating the currently best 20-year-old, 4.086-competitive Move-To-Local-Min (Mtlm) algorithm by Bartal et al. (SODA 1997). Like Mtlm, our algorithm also operates in phases, but it adapts their lengths dynamically depending on the geometry of requests seen so far. The improvement was obtained by carefully analyzing a linear model (factor-revealing linear program) of a single phase of the algorithm. PubDate: Thu, 25 Jul 2019 00:00:00 GMT