TY - GEN
T1 - Oracle-based primal-dual algorithms for packing and covering semidefinite programs
AU - Elbassioni, Khaled
AU - Makino, Kazuhisa
N1 - Publisher Copyright:
© Khaled Elbassioni and Kazuhisa Makino.
PY - 2019/9
Y1 - 2019/9
N2 - 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.
AB - 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.
KW - Approximate solutions
KW - Logarithmic potential
KW - Packing and covering
KW - Primal-dual algorithms
KW - Semidefinite programs
UR - http://www.scopus.com/inward/record.url?scp=85074869110&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ESA.2019.43
DO - 10.4230/LIPIcs.ESA.2019.43
M3 - Conference contribution
AN - SCOPUS:85074869110
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 27th Annual European Symposium on Algorithms, ESA 2019
A2 - Bender, Michael A.
A2 - Svensson, Ola
A2 - Herman, Grzegorz
T2 - 27th Annual European Symposium on Algorithms, ESA 2019
Y2 - 9 September 2019 through 11 September 2019
ER -