文章基本信息

标题：The Norms of Graph Spanners
本地全文：下载
作者：Eden Chlamt{'a}c ; Michael Dinitz ; Thomas Robinson 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：132
页码：1-15
DOI：10.4230/LIPIcs.ICALP.2019.40
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：A t-spanner of a graph G is a subgraph H in which all distances are preserved up to a multiplicative t factor. A classical result of Althöfer et al. is that for every integer k and every graph G, there is a (2k-1)-spanner of G with at most O(n^{1+1/k}) edges. But for some settings the more interesting notion is not the number of edges, but the degrees of the nodes. This spurred interest in and study of spanners with small maximum degree. However, this is not necessarily a robust enough objective: we would like spanners that not only have small maximum degree, but also have "few" nodes of "large" degree. To interpolate between these two extremes, in this paper we initiate the study of graph spanners with respect to the l_p-norm of their degree vector, thus simultaneously modeling the number of edges (the l_1-norm) and the maximum degree (the l_{infty}-norm). We give precise upper bounds for all ranges of p and stretch t: we prove that the greedy (2k-1)-spanner has l_p norm of at most max(O(n), O(n^{{k+p}/{kp}})), and that this bound is tight (assuming the Erdös girth conjecture). We also study universal lower bounds, allowing us to give "generic" guarantees on the approximation ratio of the greedy algorithm which generalize and interpolate between the known approximations for the l_1 and l_{infty} norm. Finally, we show that at least in some situations, the l_p norm behaves fundamentally differently from l_1 or l_{infty}: there are regimes (p=2 and stretch 3 in particular) where the greedy spanner has a provably superior approximation to the generic guarantee.
关键词：spanners; approximations