Finding Sparse Solutions for Packing and Covering Semidefinite Programs
Khaled Elbassioni, Kazuhisa Makino, Waleed Najy · SIAM Journal on Optimization · 2022
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.