Approximating sparse quadratic programs

DOI10.1016/J.TCS.2023.114319arXiv2007.01252MaRDI QIDQ6180751FDOQ6180751

Rolf Niedermeier, Rami Pugatch, Leon Kellerhals, Danny Hermelin

Publication date: 2 January 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Given a matrix $Ainmathbb{R}^{nimesn}$, we consider the problem of maximizing $x^{T}Ax$ subject to the constraint $xin{-1,1}^n$. This problem, called MaxQP by Charikar and Wirth [FOCS'04], generalizes MaxCut and has natural applications in data clustering and in the study of disordered magnetic phases of matter. Charikar and Wirth showed that the problem admits an $Omega(1/lgn)$ approximation via semidefinite programming, and Alon, Makarychev, Makarychev, and Naor [STOC'05] showed that the same approach yields an $Omega(1)$ approximation when $A$ corresponds to a graph of bounded chromatic number. Both these results rely on solving the semidefinite relaxation of MaxQP, whose currently best running time is $ildeO(n^{1.5}cdotminN,n^{1.5})$, where $N$ is the number of nonzero entries in $A$ and $ildeO$ ignores polylogarithmic factors. In this sequel, we abandon the semidefinite approach and design purely combinatorial approximation algorithms for special cases of MaxQP where $A$ is sparse (i.e., has $O(n)$ nonzero entries). Our algorithms are superior to the semidefinite approach in terms of running time, yet are still competitive in terms of their approximation guarantees. More specifically, we show that: - MaxQP admits a $(1/2Delta)$-approximation in $O(nlgn)$ time, where $Delta$ is the maximum degree of the corresponding graph. - UnitMaxQP, where $Ain{-1,0,1}^{nimesn}$, admits a $(1/2d)$-approximation in $O(n)$ time when the corresponding graph is $d$-degenerate, and a $(1/3delta)$-approximation in $O(n^{1.5})$ time when the corresponding graph has $deltan$ edges. - MaxQP admits a $(1-varepsilon)$-approximation in $O(n)$ time when the corresponding graph and each of its minors have bounded local treewidth. - UnitMaxQP admits a $(1-varepsilon)$-approximation in $O(n^2)$ time when the corresponding graph is $H$-minor free.

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

zbMATH Keywords

quadratic programmingcombinatorial optimizationcorrelation clusteringIsing spin glassgraph cutsMaxQP

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Clustering with qualitative information
• Approximating the Cut-Norm via Grothendieck's Inequality
• Correlation clustering
• Approximation algorithms for NP-complete problems on planar graphs
• Some optimal inapproximability results
• Lower bound of the Hadwiger number of graphs by their average degree
• Treewidth. Computations and approximations
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Diameter and treewidth in minor-closed graph families
• Correlation clustering in general weighted graphs
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Graph minors. XVI: Excluding a non-planar graph
• Local tree-width, excluded minors, and approximation algorithms
• Quadratic forms on graphs
• Subgraph Isomorphism in Planar Graphs and Related Problems
• A simpler algorithm and shorter proof for the graph minor decomposition
• The size of the largest bipartite subgraphs
• A \(c^k n\) 5-approximation algorithm for treewidth
• A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–

This page was built for publication: Approximating sparse quadratic programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6180751)