Approximating sparse quadratic programs
From MaRDI portal
Publication:6180751
DOI10.1016/j.tcs.2023.114319arXiv2007.01252MaRDI QIDQ6180751
Rolf Niedermeier, Rami Pugatch, Leon Kellerhals, Danny Hermelin
Publication date: 2 January 2024
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2007.01252
quadratic programmingcombinatorial optimizationcorrelation clusteringIsing spin glassgraph cutsMaxQP
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The max-cut problem on graphs not contractible to \(K_ 5\)
- Correlation clustering
- Lower bound of the Hadwiger number of graphs by their average degree
- Treewidth. Computations and approximations
- The size of the largest bipartite subgraphs
- Graph minors. XVI: Excluding a non-planar graph
- Diameter and treewidth in minor-closed graph families
- Local tree-width, excluded minors, and approximation algorithms
- Correlation clustering in general weighted graphs
- Clustering with qualitative information
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Approximation algorithms for NP-complete problems on planar graphs
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Subgraph Isomorphism in Planar Graphs and Related Problems
- A simpler algorithm and shorter proof for the graph minor decomposition
- Some optimal inapproximability results
- Approximating the Cut-Norm via Grothendieck's Inequality
- A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–
- Quadratic forms on graphs
