Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs

Khaled Elbassioni; Kazuhisa Makino

doi:10.1007/978-981-16-4095-7_4

Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs

Khaled Elbassioni
, Kazuhisa Makino

Computer Science

Kyoto University

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

1 Scopus citations

Abstract

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 have been proposed that utilize the particular structure of this class of problems in order to obtain more efficient algorithms than those offered by general SDP solvers. For certain applications, it may be necessary to deal with SDPs with a very large number of (e.g., exponentially or even infinitely many) constraints. In this chapter, we give an overview of some of the techniques that can be used to solve this class of problems, focusing onmultiplicative weight updates and logarithmic-potential methods.

Original language	British English
Title of host publication	Sublinear Computation Paradigm
Subtitle of host publication	Algorithmic Revolution in the Big Data Era
Publisher	Springer Nature
Pages	47-63
Number of pages	17
ISBN (Electronic)	9789811640957
ISBN (Print)	9789811640971
DOIs	https://doi.org/10.1007/978-981-16-4095-7_4
State	Published - 1 Jan 2021

Access to Document

10.1007/978-981-16-4095-7_4

Cite this

@inbook{cbaf45c112bb4fa9917bdbc37b9bb1de,

title = "Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs",

abstract = "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 have been proposed that utilize the particular structure of this class of problems in order to obtain more efficient algorithms than those offered by general SDP solvers. For certain applications, it may be necessary to deal with SDPs with a very large number of (e.g., exponentially or even infinitely many) constraints. In this chapter, we give an overview of some of the techniques that can be used to solve this class of problems, focusing onmultiplicative weight updates and logarithmic-potential methods.",

author = "Khaled Elbassioni and Kazuhisa Makino",

note = "Publisher Copyright: {\textcopyright} The Editor(s) (if applicable) and The Author(s) 2022.",

year = "2021",

month = jan,

day = "1",

doi = "10.1007/978-981-16-4095-7\_4",

language = "British English",

isbn = "9789811640971",

pages = "47--63",

booktitle = "Sublinear Computation Paradigm",

publisher = "Springer Nature",

address = "United Kingdom",

}

TY - CHAP

T1 - Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs

AU - Elbassioni, Khaled

AU - Makino, Kazuhisa

PY - 2021/1/1

Y1 - 2021/1/1

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 have been proposed that utilize the particular structure of this class of problems in order to obtain more efficient algorithms than those offered by general SDP solvers. For certain applications, it may be necessary to deal with SDPs with a very large number of (e.g., exponentially or even infinitely many) constraints. In this chapter, we give an overview of some of the techniques that can be used to solve this class of problems, focusing onmultiplicative weight updates and logarithmic-potential methods.

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 have been proposed that utilize the particular structure of this class of problems in order to obtain more efficient algorithms than those offered by general SDP solvers. For certain applications, it may be necessary to deal with SDPs with a very large number of (e.g., exponentially or even infinitely many) constraints. In this chapter, we give an overview of some of the techniques that can be used to solve this class of problems, focusing onmultiplicative weight updates and logarithmic-potential methods.

UR - https://www.scopus.com/pages/publications/85131227588

U2 - 10.1007/978-981-16-4095-7_4

DO - 10.1007/978-981-16-4095-7_4

M3 - Chapter

AN - SCOPUS:85131227588

SN - 9789811640971

SP - 47

EP - 63

BT - Sublinear Computation Paradigm

PB - Springer Nature

ER -

Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this