Approximating sparse quadratic programs

DOI10.1016/J.TCS.2023.114319MaRDI QIDQ6180751zbMATH OpenFDO

Authors Danny Hermelin, Leon Kellerhals, Rolf Niedermeier, Rami Pugatch

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

zbMATH Keywords

quadratic programmingcombinatorial optimizationcorrelation clusteringIsing spin glassgraph cutsMaxQP

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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.

Recommendations

• Algorithms – ESA 2005
• On quadratic programming with a ratio objective
• On the maximum quadratic assignment problem
• On the maximum quadratic assignment problem
• scientific article; zbMATH DE number 1256751

Cites work

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

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)