Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMulti-level Weighted Additive Spanners
228
0
0.0
(
0
)
Added by
Abu Reyan Ahmed
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given a graph $G = (V,E)$, a subgraph $H$ is an emph{additive $+beta$ spanner} if $dist_H(u,v) le dist_G(u,v) + beta$ for all $u, v in V$. A emph{pairwise spanner} is a spanner for which the above inequality only must hold for specific pairs $P subseteq V times V$ given on input, and when the pairs have the structure $P = S times S$ for some subset $S subseteq V$, it is specifically called a emph{subsetwise spanner}. Spanners in unweighted graphs have been studied extensively in the literature, but have only recently been generalized to weighted graphs. In this paper, we consider a multi-level version of the subsetwise spanner in weighted graphs, where the vertices in $S$ possess varying level, priority, or quality of service (QoS) requirements, and the goal is to compute a nested sequence of spanners with the minimum number of total edges. We first generalize the $+2$ subsetwise spanner of [Pettie 2008, Cygan et al., 2013] to the weighted setting. We experimentally measure the performance of this and several other algorithms for weighted additive spanners, both in terms of runtime and sparsity of output spanner, when applied at each level of the multi-level problem. Spanner sparsity is compared to the sparsest possible spanner satisfying the given error budget, obtained using an integer programming formulation of the problem. We run our experiments with respect to input graphs generated by several different random graph generators: ErdH{o}s--R{e}nyi, Watts--Strogatz, Barab{a}si--Albert, and random geometric models. By analyzing our experimental results we developed a new technique of changing an initialization parameter value that provides better performance in practice.
rate research
Read More
A emph{spanner} of a graph $G$ is a subgraph $H$ that approximately preserves shortest path distances in $G$. Spanners are commonly applied to compress computation on metric spaces corresponding to weighted input graphs. Classic spanner constructions can seamlessly handle edge weights, so long as error is measured emph{multiplicatively}. In this work, we investigate whether one can similarly extend constructions of spanners with purely emph{additive} error to weighted graphs. These extensions are not immediate, due to a key lemma about the size of shortest path neighborhoods that fails for weighted graphs. Despite this, we recover a suitable amortized version, which lets us prove direct extensions of classic $+2$ and $+4$ unweighted spanners (both all-pairs and pairwise) to $+2W$ and $+4W$ weighted spanners, where $W$ is the maximum edge weight. Specifically, we show that a weighted graph $G$ contains all-pairs (pairwise) $+2W$ and $+4W$ weighted spanners of size $O(n^{3/2})$ and $widetilde{O}(n^{7/5})$ ($O(np^{1/3})$ and $O(np^{2/7})$) respectively. For a technical reason, the $+6$ unweighted spanner becomes a $+8W$ weighted spanner; closing this error gap is an interesting remaining open problem. That is, we show that $G$ contains all-pairs (pairwise) $+8W$ weighted spanners of size $O(n^{4/3})$ ($O(np^{1/4})$).
An emph{additive $+beta$ spanner} of a graph $G$ is a subgraph which preserves distances up to an additive $+beta$ error. Additive spanners are well-studied in unweighted graphs but have only recently received attention in weighted graphs [Elkin et al. 2019 and 2020, Ahmed et al. 2020]. This paper makes two new contributions to the theory of weighted additive spanners. For weighted graphs, [Ahmed et al. 2020] provided constructions of sparse spanners with emph{global} error $beta = cW$, where $W$ is the maximum edge weight in $G$ and $c$ is constant. We improve these to emph{local} error by giving spanners with additive error $+cW(s,t)$ for each vertex pair $(s,t)$, where $W(s, t)$ is the maximum edge weight along the shortest $s$--$t$ path in $G$. These include pairwise $+(2+eps)W(cdot,cdot)$ and $+(6+eps) W(cdot, cdot)$ spanners over vertex pairs $Pc subseteq V times V$ on $O_{eps}(n|Pc|^{1/3})$ and $O_{eps}(n|Pc|^{1/4})$ edges for all $eps > 0$, which extend previously known unweighted results up to $eps$ dependence, as well as an all-pairs $+4W(cdot,cdot)$ spanner on $widetilde{O}(n^{7/5})$ edges. Besides sparsity, another natural way to measure the quality of a spanner in weighted graphs is by its emph{lightness}, defined as the total edge weight of the spanner divided by the weight of an MST of $G$. We provide a $+eps W(cdot,cdot)$ spanner with $O_{eps}(n)$ lightness, and a $+(4+eps) W(cdot,cdot)$ spanner with $O_{eps}(n^{2/3})$ lightness. These are the first known additive spanners with nontrivial lightness guarantees. All of the above spanners can be constructed in polynomial time.
This tutorial review provides a guiding reference to researchers who want to have an overview of the large body of literature about graph spanners. It reviews the current literature covering various research streams about graph spanners, such as different formulations, sparsity and lightness results, computational complexity, dynamic algorithms, and applications. As an additional contribution, we offer a list of open problems on graph spanners.
For a set A of n applicants and a set I of m items, we consider a problem of computing a matching of applicants to items, i.e., a function M mapping A to I; here we assume that each applicant $x in A$ provides a preference list on items in I. We say that an applicant $x in A$ prefers an item p than an item q if p is located at a higher position than q in its preference list, and we say that x prefers a matching M over a matching M if x prefers M(x) over M(x). For a given matching problem A, I, and preference lists, we say that M is more popular than M if the number of applicants preferring M over M is larger than that of applicants preferring M over M, and M is called a popular matching if there is no other matching that is more popular than M. Here we consider the situation that A is partitioned into $A_{1},A_{2},...,A_{k}$, and that each $A_{i}$ is assigned a weight $w_{i}>0$ such that w_{1}>w_{2}>...>w_{k}>0$. For such a matching problem, we say that M is more popular than M if the total weight of applicants preferring M over M is larger than that of applicants preferring M over M, and we call M an k-weighted popular matching if there is no other matching that is more popular than M. In this paper, we analyze the 2-weighted matching problem, and we show that (lower bound) if $m/n^{4/3}=o(1)$, then a random instance of the 2-weighted matching problem with $w_{1} geq 2w_{2}$ has a 2-weighted popular matching with probability o(1); and (upper bound) if $n^{4/3}/m = o(1)$, then a random instance of the 2-weighted matching problem with $w_{1} geq 2w_{2}$ has a 2-weighted popular matching with probability 1-o(1).
Maintaining and updating shortest paths information in a graph is a fundamental problem with many applications. As computations on dense graphs can be prohibitively expensive, and it is preferable to perform the computations on a sparse skeleton of the given graph that roughly preserves the shortest paths information. Spanners and emulators serve this purpose. This paper develops fast dynamic algorithms for sparse spanner and emulator maintenance and provides evidence from fine-grained complexity that these algorithms are tight. Under the popular OMv conjecture, we show that there can be no decremental or incremental algorithm that maintains an $n^{1+o(1)}$ edge (purely additive) $+n^{delta}$-emulator for any $delta<1/2$ with arbitrary polynomial preprocessing time and total update time $m^{1+o(1)}$. Also, under the Combinatorial $k$-Clique hypothesis, any fully dynamic combinatorial algorithm that maintains an $n^{1+o(1)}$ edge $(1+epsilon,n^{o(1)})$-spanner or emulator must either have preprocessing time $mn^{1-o(1)}$ or amortized update time $m^{1-o(1)}$. Both of our conditional lower bounds are tight. As the above fully dynamic lower bound only applies to combinatorial algorithms, we also develop an algebraic spanner algorithm that improves over the $m^{1-o(1)}$ update time for dense graphs. For any constant $epsilonin (0,1]$, there is a fully dynamic algorithm with worst-case update time $O(n^{1.529})$ that whp maintains an $n^{1+o(1)}$ edge $(1+epsilon,n^{o(1)})$-spanner. Our new algebraic techniques and spanner algorithms allow us to also obtain (1) a new fully dynamic algorithm for All-Pairs Shortest Paths (APSP) with update and path query time $O(n^{1.9})$; (2) a fully dynamic $(1+epsilon)$-approximate APSP algorithm with update time $O(n^{1.529})$; (3) a fully dynamic algorithm for near-$2$-approximate Steiner tree maintenance.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
