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.ESA.2019.43
URN: urn:nbn:de:0030-drops-111642
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11164/
Go to the corresponding LIPIcs Volume Portal

Elbassioni, Khaled ; Makino, Kazuhisa

Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs

pdf-format:
LIPIcs-ESA-2019-43.pdf (0.6 MB)

Abstract

Packing and covering semidefinite programs (SDPs) appear in natural relaxations of many combinatorial optimization problems as well as a number of other applications. Recently, several techniques were proposed, that utilize the particular structure of this class of problems, to obtain more efficient algorithms than those offered by general SDP solvers. For certain applications, such as those described in this paper, it maybe required to deal with SDP's with exponentially or infinitely many constraints, which are accessible only via an oracle. In this paper, we give an efficient primal-dual algorithm to solve the problem in this case, which is an extension of a logarithmic-potential based algorithm of Grigoriadis, Khachiyan, Porkolab and Villavicencio (SIAM Journal of Optimization 41 (2001)) for packing/covering linear programs.

BibTeX - Entry

@InProceedings{elbassioni_et_al:LIPIcs:2019:11164,
  author =	{Khaled Elbassioni and Kazuhisa Makino},
  title =	{{Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{43:1--43:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Michael A. Bender and Ola Svensson and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11164},
  URN =		{urn:nbn:de:0030-drops-111642},
  doi =		{10.4230/LIPIcs.ESA.2019.43},
  annote =	{Keywords: Semidefinite programs, packing and covering, logarithmic potential, primal-dual algorithms, approximate solutions}
}

Keywords: Semidefinite programs, packing and covering, logarithmic potential, primal-dual algorithms, approximate solutions
Collection: 27th Annual European Symposium on Algorithms (ESA 2019)
Issue Date: 2019
Date of publication: 06.09.2019

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