Finding Sparse Solutions for Packing and Covering Semidefinite Programs

DOI10.1137/20M137570XMaRDI QIDQ5071107zbMATH OpenOpenAlexFDO

Authors Kazuhisa Makino, Waleed Najy, Khaled Elbassioni

Publication date 20 April 2022

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.09698

zbMATH Keywords

approximate solutionslogarithmic potentialpacking and coveringprimal-dual algorithmsrobust packing and covering SDPssemidefinite programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Large-scale problems in mathematical programming (90C06) Semidefinite programming (90C22)

Recommendations

• Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs
• Feasible and accurate algorithms for covering semidefinite programs
• Approximating semidefinite packing programs
• Fast First-Order Algorithms for Packing–Covering Semidefinite Programs
• Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization

Cites work

• A combinatorial, primal-dual approach to semidefinite programs
• A Parallel Approximation Algorithm for Positive Semidefinite Programming
• 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
• Feasible and accurate algorithms for covering semidefinite programs
• scientific article; zbMATH DE number 5485455 (Why is no real title available?)
• scientific article; zbMATH DE number 4067101 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (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?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs
• Preconditioning Lanczos Approximations to the Matrix Exponential
• Quadratically Constrained Quadratic Programs on Acyclic Graphs With Application to Power Flow
• 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
• Solving semidefinite-quadratic-linear programs using SDPT3
• 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

(3)

• Fast First-Order Algorithms for Packing–Covering Semidefinite Programs
• Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs
• A conditional gradient homotopy method with applications to semidefinite programming

Describes a project that uses

Uses Software

• SDPT3

This page was built for publication: Finding Sparse Solutions 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 Q5071107)