2026-07-23T10:34:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11164 2024-03-06T10:47:36Z ddc:004 open_access

Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs Elbassioni, Khaled Makino, Kazuhisa Semidefinite programs packing and covering logarithmic potential primal-dual algorithms approximate solutions 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Khaled Elbassioni and Kazuhisa Makino 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.43 urn:nbn:de:0030-drops-111642 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.43 eng https://creativecommons.org/licenses/by/3.0/legalcode