Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMore Compact Oracles for Approximate Distances in Planar Graphs
137
0
0.0
(
0
)
Added by
Christian Sommer
Publication date
2011
fields
Informatics Engineering
and research's language is
English
Authors
Christian Sommer
Ask ChatGPT about the research
No Arabic abstract
Distance oracles are data structures that provide fast (possibly approximate) answers to shortest-path and distance queries in graphs. The tradeoff between the space requirements and the query time of distance oracles is of particular interest and the main focus of this paper. In FOCS01, Thorup introduced approximate distance oracles for planar graphs. He proved that, for any eps>0 and for any planar graph on n nodes, there exists a (1+eps)-approximate distance oracle using space O(n eps^{-1} log n) such that approximate distance queries can be answered in time O(1/eps). Ten years later, we give the first improvements on the space-querytime tradeoff for planar graphs. * We give the first oracle having a space-time product with subquadratic dependency on 1/eps. For space ~O(n log n) we obtain query time ~O(1/eps) (assuming polynomial edge weights). The space shows a doubly logarithmic dependency on 1/eps only. We believe that the dependency on eps may be almost optimal. * For the case of moderate edge weights (average bounded by polylog(n), which appears to be the case for many real-world road networks), we hit a sweet spot, improving upon Thorups oracle both in terms of eps and n. Our oracle uses space ~O(n log log n) and it has query time ~O(log log log n + 1/eps). (Asymptotic notation in this abstract hides low-degree polynomials in log(1/eps) and log*(n).)
rate research
Read More
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}$.
A (1 + eps)-approximate distance oracle for a graph is a data structure that supports approximate point-to-point shortest-path-distance queries. The most relevant measures for a distance-oracle construction are: space, query time, and preprocessing time. There are strong distance-oracle constructions known for planar graphs (Thorup, JACM04) and, subsequently, minor-excluded graphs (Abraham and Gavoille, PODC06). However, these require Omega(eps^{-1} n lg n) space for n-node graphs. We argue that a very low space requirement is essential. Since modern computer architectures involve hierarchical memory (caches, primary memory, secondary memory), a high memory requirement in effect may greatly increase the actual running time. Moreover, we would like data structures that can be deployed on small mobile devices, such as handhelds, which have relatively small primary memory. In this paper, for planar graphs, bounded-genus graphs, and minor-excluded graphs we give distance-oracle constructions that require only O(n) space. The big O hides only a fixed constant, independent of epsilon and independent of genus or size of an excluded minor. The preprocessing times for our distance oracle are also faster than those for the previously known constructions. For planar graphs, the preprocessing time is O(n lg^2 n). However, our constructions have slower query times. For planar graphs, the query time is O(eps^{-2} lg^2 n). For our linear-space results, we can in fact ensure, for any delta > 0, that the space required is only 1 + delta times the space required just to represent the graph itself.
We study the classical Node-Disjoint Paths (NDP) problem: given an $n$-vertex graph $G$ and a collection $M={(s_1,t_1),ldots,(s_k,t_k)}$ of pairs of vertices of $G$ called demand pairs, find a maximum-cardinality set of node-disjoint paths connecting the demand pairs. NDP is one of the most basic routing problems, that has been studied extensively. Despite this, there are still wide gaps in our understanding of its approximability: the best currently known upper bound of $O(sqrt n)$ on its approximation ratio is achieved via a simple greedy algorithm, while the best current negative result shows that the problem does not have a better than $Omega(log^{1/2-delta}n)$-approximation for any constant $delta$, under standard complexity assumptions. Even for planar graphs no better approximation algorithms are known, and to the best of our knowledge, the best negative bound is APX-hardness. Perhaps the biggest obstacle to obtaining better approximation algorithms for NDP is that most currently known approximation algorithms for this type of problems rely on the standard multicommodity flow relaxation, whose integrality gap is $Omega(sqrt n)$ for NDP, even in planar graphs. In this paper, we break the barrier of $O(sqrt n)$ on the approximability of the NDP problem in planar graphs and obtain an $tilde O(n^{9/19})$-approximation. We introduce a new linear programming relaxation of the problem, and a number of new techniques, that we hope will be helpful in designing more powerful algorithms for this and related problems.
We study the problem of learning the causal relationships between a set of observed variables in the presence of latents, while minimizing the cost of interventions on the observed variables. We assume access to an undirected graph $G$ on the observed variables whose edges represent either all direct causal relationships or, less restrictively, a superset of causal relationships (identified, e.g., via conditional independence tests or a domain expert). Our goal is to recover the directions of all causal or ancestral relations in $G$, via a minimum cost set of interventions. It is known that constructing an exact minimum cost intervention set for an arbitrary graph $G$ is NP-hard. We further argue that, conditioned on the hardness of approximate graph coloring, no polynomial time algorithm can achieve an approximation factor better than $Theta(log n)$, where $n$ is the number of observed variables in $G$. To overcome this limitation, we introduce a bi-criteria approximation goal that lets us recover the directions of all but $epsilon n^2$ edges in $G$, for some specified error parameter $epsilon > 0$. Under this relaxed goal, we give polynomial time algorithms that achieve intervention cost within a small constant factor of the optimal. Our algorithms combine work on efficient intervention design and the design of low-cost separating set systems, with ideas from the literature on graph property testing.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
