Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPlane Gossip: Approximating rumor spread in planar graphs
128
0
0.0
(
0
)
Added by
Jennifer Iglesias
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the design of schedules for multi-commodity multicast; we are given an undirected graph $G$ and a collection of source destination pairs, and the goal is to schedule a minimum-length sequence of matchings that connects every source with its respective destination. Multi-commodity multicast models a classic information dissemination problem in networks where the primary communication constraint is the number of connections that a node can make, not link bandwidth. Multi-commodity multicast is closely related to the problem of finding a subgraph, $H$, of optimal poise, where the poise is defined as the sum of the maximum degree of $H$ and the maximum distance between any source-destination pair in $H$. We first show that the minimum poise subgraph for single-commodity multicast can be approximated to within a factor of $O(log k)$ with respect to the value of a natural LP relaxation in an instance with $k$ terminals. This is the first upper bound on the integrality gap of the natural LP. Using this poise result and shortest-path separators in planar graphs, we obtain a $O(log^3 klog n/(loglog n))$-approximation for multi-commodity multicast for planar graphs. We also study the minimum-time radio gossip problem in planar graphs where a message from each node must be transmitted to all other nodes under a model where nodes can broadcast to all neighbors in a single step but only nodes with a single broadcasting neighbor get a message. We give an $O(log^2 n)$-approximation for radio gossip in planar graphs breaking previous barriers. This is the first bound for radio gossip that does not rely on the maximum degree of the graph. Finally, we show that our techniques for planar graphs extend to graphs with excluded minors. We establish polylogarithmic-approximation algorithms for both multi-commodity multicast and radio gossip problems in minor-free graphs.
rate research
Read More
We study the problem of finding a minimum weight connected subgraph spanning at least $k$ vertices on planar, node-weighted graphs. We give a $(4+eps)$-approximation algorithm for this problem. We achieve this by utilizing the recent LMP primal-dual $3$-approximation for the node-weighted prize-collecting Steiner tree problem by Byrka et al (SWAT16) and adopting an approach by Chudak et al. (Math. Prog. 04) regarding Lagrangian relaxation for the edge-weighted variant. In particular, we improve the procedure of picking additional vertices (tree merging procedure) given by Sadeghian (2013) by taking a constant number of recursive steps and utilizing the limited guessing procedure of Arora and Karakostas (Math. Prog. 06). More generally, our approach readily gives a $( icefrac{4}{3}cdot r+eps)$-approximation on any graph class where the algorithm of Byrka et al. for the prize-collecting version gives an $r$-approximation. We argue that this can be interpreted as a generalization of an analogous result by Konemann et al. (Algorithmica~11) for partial cover problems. Together with a lower bound construction by Mestre (STACS08) for partial cover this implies that our bound is essentially best possible among algorithms that utilize an LMP algorithm for the Lagrangian relaxation as a black box. In addition to that, we argue by a more involved lower bound construction that even using the LMP algorithm by Byrka et al. in a emph{non-black-box} fashion could not beat the factor $ icefrac{4}{3}cdot r$ when the tree merging step relies only on the solutions output by the LMP algorithm.
In this paper, we study PUSH-PULL style rumor spreading algorithms in the mobile telephone model, a variant of the classical telephone model in which each node can participate in at most one connection per round; i.e., you can no longer have multiple nodes pull information from the same source in a single round. Our model also includes two new parameterized generalizations: (1) the network topology can undergo a bounded rate of change (for a parameterized rate that spans from no changes to changes in every round); and (2) in each round, each node can advertise a bounded amount of information to all of its neighbors before connection decisions are made (for a parameterized number of bits that spans from no advertisement to large advertisements). We prove that in the mobile telephone model with no advertisements and no topology changes, PUSH-PULL style algorithms perform poorly with respect to a graphs vertex expansion and graph conductance as compared to the known tight results in the classical telephone model. We then prove, however, that if nodes are allowed to advertise a single bit in each round, a natural variation of PUSH-PULL terminates in time that matches (within logarithmic factors) this strategys performance in the classical telephone model---even in the presence of frequent topology changes. We also analyze how the performance of this algorithm degrades as the rate of change increases toward the maximum possible amount. We argue that our model matches well the properties of emerging peer-to-peer communication standards for mobile devices, and that our efficient PUSH-PULL variation that leverages small advertisements and adapts well to topology changes is a good choice for rumor spreading in this increasingly important setting.
We present an approximation algorithm for the maximum independent set (MIS) problem over the class of equilateral $B_1$-VPG graphs. These are intersection graphs of $L$-shaped planar objects % (and their rotations by multiples of $90^o$) with both arms of each object being equal. We obtain a $36(log 2d)$-approximate algorithm running in $O(n(log n)^2)$ time for this problem, where $d$ is the ratio $d_{max}/d_{min}$ and $d_{max}$ and $d_{min}$ denote respectively the maximum and minimum length of any arm in the input equilateral $L$-representation of the graph. In particular, we obtain $O(1)$-factor approximation of MIS for $B_1$-VPG -graphs for which the ratio $d$ is bounded by a constant. % formed by unit length $L$-shapes. In fact, algorithm can be generalized to an $O(n(log n)^2)$ time and a $36(log 2d_x)(log 2d_y)$-approximate MIS algorithm over arbitrary $B_1$-VPG graphs. Here, $d_x$ and $d_y$ denote respectively the analogues of $d$ when restricted to only horizontal and vertical arms of members of the input. This is an improvement over the previously best $n^epsilon$-approximate algorithm cite{FoxP} (for some fixed $epsilon>0$), unless the ratio $d$ is exponentially large in $n$. In particular, $O(1)$-approximation of MIS is achieved for graphs with $max{d_x,d_y}=O(1)$.
We present a linear-time algorithm for simplifying flow networks on directed planar graphs: Given a directed planar graph on $n$ vertices, a source vertex $s$ and a sink vertex $t$, our algorithm removes all the arcs that do not participate in any simple $s,t$-path in linear-time. The output graph produced by our algorithm satisfies the prerequisite needed by the $O(nlog n)$-time algorithm of Weihe [FOCS94 & JCSS97] for computing maximum $s,t$-flow in directed planar graphs. Previously, Weihes algorithm could not run in $O(nlog n)$-time due to the absence of the preprocessing step; all the preceding algorithms run in $tilde{Omega}(n^2)$-time [Misiolek-Chen, COCOON05 & IPL06; Biedl, Brejov{{a}} and Vinar, MFCS00]. Consequently, this provides an alternative $O(nlog n)$-time algorithm for computing maximum $s,t$-flow in directed planar graphs in addition to the known $O(nlog n)$-time algorithms [Borradaile-Klein, SODA06 & J.ACM09; Erickson, SODA10]. Our algorithm can be seen as a (truly) linear-time $s,t$-flow sparsifier for directed planar graphs, which runs faster than any maximum $s,t$-flow algorithm (which can also be seen of as a sparsifier). The simplified structures of the resulting graph might be useful in future developments of maximum $s,t$-flow algorithms in both directed and undirected planar graphs.
We present new and improved data structures that answer exact node-to-node distance queries in planar graphs. Such data structures are also known as distance oracles. For any directed planar graph on n nodes with non-negative lengths we obtain the following: * Given a desired space allocation $Sin[nlglg n,n^2]$, we show how to construct in $tilde O(S)$ time a data structure of size $O(S)$ that answers distance queries in $tilde O(n/sqrt S)$ time per query. As a consequence, we obtain an improvement over the fastest algorithm for k-many distances in planar graphs whenever $kin[sqrt n,n)$. * We provide a linear-space exact distance oracle for planar graphs with query time $O(n^{1/2+eps})$ for any constant eps>0. This is the first such data structure with provable sublinear query time. * For edge lengths at least one, we provide an exact distance oracle of space $tilde O(n)$ such that for any pair of nodes at distance D the query time is $tilde O(min {D,sqrt n})$. Comparable query performance had been observed experimentally but has never been explained theoretically. Our data structures are based on the following new tool: given a non-self-crossing cycle C with $c = O(sqrt n)$ nodes, we can preprocess G in $tilde O(n)$ time to produce a data structure of size $O(n lglg c)$ that can answer the following queries in $tilde O(c)$ time: for a query node u, output the distance from u to all the nodes of C. This data structure builds on and extends a related data structure of Klein (SODA05), which reports distances to the boundary of a face, rather than a cycle. The best distance oracles for planar graphs until the current work are due to Cabello (SODA06), Djidjev (WG96), and Fakcharoenphol and Rao (FOCS01). For $sigmain(1,4/3)$ and space $S=n^sigma$, we essentially improve the query time from $n^2/S$ to $sqrt{n^2/S}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
