An approximation algorithm for the maximum spectral subgraph problem
type: Item
instance of: scholarly article
title: An approximation algorithm for the maximum spectral subgraph problem
zbMATH Open document ID: 1502.90142
author: Cristina Bazgan
author: Paul Beaujean
author: Eric Gourdin
published in: Journal of Combinatorial Optimization
publication date: 2022-10-04T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C22
zbMATH DE Number: 7595923
zbMATH Keywords: approximation algorithm
zbMATH Keywords: relaxation and rounding
zbMATH Keywords: semidefinite programming
zbMATH Keywords: spectral graph theory
zbMATH Keywords: random graphs
MaRDI profile type: Publication
full work available at URL: s10878-020-00552-w
OpenAlex ID: W3009266587
cites work: Random Laplacian matrices and convex relaxations
cites work: On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
cites work: Q5690490
cites work: The distribution of the maximum degree of a random graph
cites work: On the spectra of general random graphs
cites work: On the Turing model complexity of interior point methods for semidefinite programming
cites work: Random Graphs
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Subgraph sparsification and nearly optimal ultrasparsifiers
cites work: The Largest Eigenvalue of Sparse Random Graphs
cites work: Global optimization with polynomials and the problem of moments
cites work: Q5292090
cites work: Concentration and regularization of random graphs
cites work: Maximum algebraic connectivity augmentation is NP-hard
cites work: Q4856179
cites work: Polynomial matrix inequality and semidefinite representation
cites work: The complexity of the matrix eigenproblem
cites work: Semidefinite programming relaxations for semialgebraic problems
cites work: Randomized rounding: A technique for provably good algorithms and algorithmic proofs
cites work: Q3549708
cites work: Resolution of AutoGraphiX conjectures relating the index and matching number of graphs
cites work: An Introduction to Matrix Concentration Inequalities
cites work: Structured random matrices
cites work: Graph Spectra for Complex Networks
cites work: Semidefinite Programming
cites work: The Design of Approximation Algorithms
DOI: 10.1007/S10878-020-00552-W
Recommended article: The approximation of maximum subgraph problems
Recommended article: Relaxation and matrix randomized rounding for the maximum spectral subgraph problem
Recommended article: Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems
Recommended article: Optimal approximation algorithms for maximum distance-bounded subgraph problems
Recommended article: On the approximability of the maximum common subgraph problem
Recommended article: On the complexity of the Maximum Subgraph Problem
Recommended article: Approximating Maximum Diameter-Bounded Subgraphs
Recommended article: Approximating Maximum Subgraphs without Short Cycles
description: scientific article; zbMATH DE number 7595923