Search Results

Documents authored by Shen, Xiangkun

Online Covering with Sum of $ell_q$-Norm Objectives

Authors: Viswanath Nagarajan and Xiangkun Shen

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

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.

Cite as

Viswanath Nagarajan and Xiangkun Shen. Online Covering with Sum of $ell_q$-Norm Objectives. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

  author =	{Nagarajan, Viswanath and Shen, Xiangkun},
  title =	{{Online Covering with Sum of \$ell\underlineq\$-Norm Objectives}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{12:1--12:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-73839},
  doi =		{10.4230/LIPIcs.ICALP.2017.12},
  annote =	{Keywords: online algorithm, covering/packing problem, convex, buy-at-bulk, throughput maximization}
Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail