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

DOI10.4230/LIPICS.ESA.2019.43MaRDI QIDQ5075785zbMATH OpenOpenAlexFDO

Authors Kazuhisa Makino, Khaled Elbassioni

Publication date 11 May 2022

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2019/11164/pdf/LIPIcs-ESA-2019-43.pdf

zbMATH Keywords

approximate solutionssemidefinite programslogarithmic potentialprimal-dual algorithmspacking and covering

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Finding Sparse Solutions for Packing and Covering Semidefinite Programs
• Feasible and accurate algorithms for covering semidefinite programs
• Fast First-Order Algorithms for Packing–Covering Semidefinite Programs
• Approximating semidefinite packing programs
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization

Cites work

• scientific article; zbMATH DE number 5485455 (Why is no real title available?)
• scientific article; zbMATH DE number 1256751 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• A Parallel Approximation Algorithm for Positive Semidefinite Programming
• A combinatorial, primal-dual approach to semidefinite programs
• A sublinear-time randomized approximation algorithm for matrix games
• An SDP-based algorithm for linear-sized spectral sparsification
• Approximate max-min resource sharing for structured concave optimization
• Approximating semidefinite packing programs
• Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring
• Estimating a largest eigenvector by Lanczos and polynomial algorithms with a random start
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Randomized metarounding
• Robust optimization
• Robust optimization-methodology and applications
• Semidefinite Programming
• Smooth minimization of non-smooth functions
• Smoothing technique and its applications in semidefinite optimization
• Sparse sums of positive semidefinite matrices
• Spectral sparsification and regret minimization beyond matrix multiplicative updates
• Sublinear time algorithms for approximate semidefinite programming
• The multiplicative weights update method: a meta-algorithm and applications
• Twice-Ramanujan sparsifiers
• Using optimization to obtain a width-independent, parallel, simpler, and faster positive SDP solver

Cited in

(1)

• Finding Sparse Solutions for Packing and Covering Semidefinite Programs

This page was built for publication: Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5075785)