# Finding Sparse Solutions for Packing and Covering Semidefinite Programs

arXiv: https://arxiv.org/abs/1809.09698 · HTML: https://mlsanity.com/paper/1809.09698/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Sep 2018.

## Built on by (most cited first, 1 of 1)

- [A conditional gradient homotopy method with applications to Semidefinite Programming](https://mlsanity.com/paper/2207.03101/) (2022)

## Abstract (arXiv)

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 may be desirable to obtain it 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 it logarithmic-potential based algorithm of Grigoriadis, Khachiyan, Porkolab and Villavicencio (SIAM Journal of Optimization 41 (2001)) for packing/covering linear programs.