An approximation algorithm for the maximum spectral subgraph problem
From MaRDI portal
Publication:2082202
DOI10.1007/s10878-020-00552-wzbMath1502.90142OpenAlexW3009266587MaRDI QIDQ2082202
Eric Gourdin, Cristina Bazgan, Paul Beaujean
Publication date: 4 October 2022
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-020-00552-w
semidefinite programmingapproximation algorithmrandom graphsspectral graph theoryrelaxation and rounding
Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Combinatorial optimization (90C27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the spectra of general random graphs
- Resolution of AutoGraphiX conjectures relating the index and matching number of graphs
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- The distribution of the maximum degree of a random graph
- Semidefinite programming relaxations for semialgebraic problems
- Random Laplacian matrices and convex relaxations
- Structured random matrices
- Maximum algebraic connectivity augmentation is NP-hard
- Global Optimization with Polynomials and the Problem of Moments
- The complexity of the matrix eigenproblem
- On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming
- Subgraph sparsification and nearly optimal ultrasparsifiers
- Polynomial Matrix Inequality and Semidefinite Representation
- The Design of Approximation Algorithms
- On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- The Largest Eigenvalue of Sparse Random Graphs
- Semidefinite Programming
- Graph Spectra for Complex Networks
- Concentration and regularization of random graphs
- An Introduction to Matrix Concentration Inequalities
- Random Graphs
