文章基本信息

标题：Online Covering with Sum of $ell_q$-Norm Objectives
本地全文：下载
作者：Viswanath Nagarajan ; Xiangkun Shen
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：80
页码：12:1-12:12
DOI：10.4230/LIPIcs.ICALP.2017.12
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We consider fractional online covering problems with lq-norm objectives. The problem of interest is of the form min{ f(x) : Ax >= 1, x >= 0} where f(x) is the weighted sum of lq-norms and A is a non-negative matrix. The rows of A (i.e. covering constraints) arrive online over time. We provide an online O(log d+log p)-competitive algorithm where p is the maximum to minimum ratio of A and A is the row sparsity of A. This is based on the online primal-dual framework where we use the dual of the above convex program. Our result expands the class of convex objectives that admit good online algorithms: prior results required a monotonicity condition on the objective which is not satisfied here. This result is nearly tight even for the linear special case. As direct applications, we obtain (i) improved online algorithms for non-uniform buy-at-bulk network design and (ii) the first online algorithm for throughput maximization under lq-norm edge capacities.
关键词：online algorithm; covering/packing problem; convex; buy-at-bulk; throughput maximization