Text

Finding Sparse Solutions for Packing and Covering Semidefinite Programs

acking 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.

Ketersediaan

Informasi Detail

Judul Seri

SIAM JOURNAL ON OPTIMIZATION; Vol.32 No.2 April-June 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 321-353

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

PRIMAL-DUAL ALGORITHMS
SEMIDEFINITE PROGRAMS
PACKING AND COVERING
LOGARITHMIC POTENTIAL
APPROXIMATE SOLUTIONS
ROBUST PACKING AND COVERING SDPS

Info Detail Spesifik

https://doi.org/10.1137/20M137570X

Pernyataan Tanggungjawab

Khaled Elbassioni, Kazuhisa Makino, Waleed Najy

Versi lain/terkait

Lampiran Berkas

Komentar