文章基本信息

标题：Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs
本地全文：下载
作者：Khaled Elbassioni ; Kazuhisa Makino
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：144
页码：1-15
DOI：10.4230/LIPIcs.ESA.2019.43
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Semidefinite programs; packing and covering; logarithmic potential; primal-dual algorithms; approximate solutions