TY - JOUR
T1 - FINDING SPARSE SOLUTIONS FOR PACKING AND COVERING SEMIDEFINITE PROGRAMS
AU - Elbassioni, Khaled
AU - Makino, Kazuhisa
AU - Najy, Waleed
N1 - Funding Information:
\ast Received by the editors October 26, 2020; accepted for publication (in revised form) December 30, 2021; published electronically April 4, 2022. An extended abstract version of this paper appeared in Proceedings of the 27th Annual European Symposium on Algorithms, ESA 2019, Munich/Garching, Germany, 2019, 43. https://doi.org/10.1137/20M137570X Funding: The work of the first author was partially supported by Abu Dhabi Education \& Knowledge - Abu Dhabi Award for Research Excellence (AARE18-152), and the work of the second author was partially supported by JST CREST JPMJCR1402 and Grants-in-Aid for Scientific Research 19K22841, 20H00609, and 20H05967. \dagger Khalifa University of Science and Technology, Abu Dhabi, UAE ([email protected]). \ddagger Research Institute for Mathematical Sciences (RIMS), Kyoto University, Kyoto 606-8502, Japan ([email protected]). \S New York University Abu Dhabi, Abu Dhabi, UAE ([email protected]).
Publisher Copyright:
© 2022 Society for Industrial and Applied Mathematics
PY - 2022
Y1 - 2022
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, which 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 may be desirable to obtain sparse dual solutions, i.e., those with support size (almost) independent of the number of primal constraints. In this paper, we give an algorithm that finds such solutions, which is an extension of a logarithmic-potential based algorithm of Grigoriadis et al. [SIAM J. Optim. 11 (2001), pp. 1081-1091] 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, which 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 may be desirable to obtain sparse dual solutions, i.e., those with support size (almost) independent of the number of primal constraints. In this paper, we give an algorithm that finds such solutions, which is an extension of a logarithmic-potential based algorithm of Grigoriadis et al. [SIAM J. Optim. 11 (2001), pp. 1081-1091] for packing/covering linear programs.
KW - approximate solutions
KW - covering SDPs
KW - logarithmic potential
KW - packing and covering
KW - primal-dual algorithms
KW - robust packing
KW - semidefinite programs
UR - http://www.scopus.com/inward/record.url?scp=85131253853&partnerID=8YFLogxK
U2 - 10.1137/20M137570X
DO - 10.1137/20M137570X
M3 - Article
AN - SCOPUS:85131253853
SN - 1052-6234
VL - 32
SP - 321
EP - 353
JO - SIAM Journal on Optimization
JF - SIAM Journal on Optimization
IS - 2
ER -