文章基本信息

标题：Approximating the Norms of Graph Spanners
本地全文：下载
作者：Eden Chlamt{'a}c ; Michael Dinitz ; Thomas Robinson 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：145
页码：1-22
DOI：10.4230/LIPIcs.APPROX-RANDOM.2019.11
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The l_p-norm of the degree vector was recently introduced by [Chlamtác, Dinitz, Robinson ICALP '19] as a new cost metric for graph spanners, as it interpolates between two traditional notions of cost (the sparsity l_1 and the max degree l_infty) and is well-motivated from applications. We study this from an approximation algorithms point of view, analyzing old algorithms and designing new algorithms for this new context, as well as providing hardness results. Our main results are for the l_2-norm and stretch 3, where we give a tight analysis of the greedy algorithm and a new algorithm specifically tailored to this setting which gives an improved approximation ratio.
关键词：Spanners; Approximations