License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.45
URN: urn:nbn:de:0030-drops-133891
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13389/
Go to the corresponding LIPIcs Volume Portal

Thắng, Nguyễn Kim

Online Primal-Dual Algorithms with Configuration Linear Programs

pdf-format:
LIPIcs-ISAAC-2020-45.pdf (0.5 MB)

Abstract

In this paper, we present primal-dual algorithms for online problems with non-convex objectives. Problems with convex objectives have been extensively studied in recent years where the analyses rely crucially on the convexity and the Fenchel duality. However, problems with non-convex objectives resist against current approaches and non-convexity represents a strong barrier in optimization in general and in the design of online algorithms in particular. In our approach, we consider configuration linear programs with the multilinear extension of the objectives. We follow the multiplicative weight update framework in which a novel point is that the primal update is defined based on the gradient of the multilinear extension. We introduce new notions, namely (local) smoothness, in order to characterize the competitive ratios of our algorithms. The approach leads to competitive algorithms for several problems with convex/non-convex objectives.

BibTeX - Entry

@InProceedings{thng:LIPIcs:2020:13389,
  author =	{Nguyễn Kim Thắng},
  title =	{{Online Primal-Dual Algorithms with Configuration Linear Programs}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{45:1--45:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13389},
  URN =		{urn:nbn:de:0030-drops-133891},
  doi =		{10.4230/LIPIcs.ISAAC.2020.45},
  annote =	{Keywords: Configuration Linear Programs, Primal-Dual, Smoothness}
}

Keywords: Configuration Linear Programs, Primal-Dual, Smoothness
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI