Finding Sparse Solutions for Packing and Covering Semidefinite Programs

DOI10.1137/20M137570XOpenAlexW2892399746MaRDI QIDQ5071107

Waleed Najy, Kazuhisa Makino, Khaled M. 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 potentialsemidefinite programsprimal-dual algorithmspacking and coveringrobust packing and covering SDPs

Mathematics Subject Classification ID

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

Uses Software

• SDPT3

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving semidefinite-quadratic-linear programs using SDPT3
• Smooth minimization of non-smooth functions
• Sublinear time algorithms for approximate semidefinite programming
• Smoothing technique and its applications in semidefinite optimization
• Robust optimization-methodology and applications
• A sublinear-time randomized approximation algorithm for matrix games
• Approximate Max-Min Resource Sharing for Structured Concave Optimization
• Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
• Approximating Semidefinite Packing Programs
• A Combinatorial, Primal-Dual Approach to Semidefinite Programs
• Feasible and Accurate Algorithms for Covering Semidefinite Programs
• Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Randomized metarounding
• Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Semidefinite Programming
• Estimating a largest eigenvector by Lanczos and polynomial algorithms with a random start
• Sparse Sums of Positive Semidefinite Matrices
• An SDP-based algorithm for linear-sized spectral sparsification
• Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs
• Twice-Ramanujan Sparsifiers
• Quadratically Constrained Quadratic Programs on Acyclic Graphs With Application to Power Flow
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Preconditioning Lanczos Approximations to the Matrix Exponential
• A Parallel Approximation Algorithm for Positive Semidefinite Programming

This page was built for publication: Finding Sparse Solutions for Packing and Covering Semidefinite Programs