Approximating sparse quadratic programs

Given a matrix A ∈ R n × n, we consider the problem of maximizing x T A x subject to the constraint x ∈ { − 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 Ω ( 1 / lg ⁡ n ) approximation via semidefinite programming, and Alon, Makarychev, Makarychev, and Naor [STOC'05] showed that the same approach yields an Ω ( 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 O ˜ ( n 1. 5 ⋅ min ⁡ { N, n 1. 5 } ), where N is the number of nonzero entries in A and O ˜ 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 / 2 Δ ) -approximation in O ( n lg ⁡ n ) time, where Δ = O ( 1 ) is the maximum degree of the corresponding graph. • Unit MaxQP, where A ∈ { − 1, 0, 1 } n × n, admits a ( 1 / 2 d ) -approximation in O ( n ) time when the corresponding graph is d-degenerate, and a ( 1 / 3 δ ) -approximation in O ( n 1. 5 ) time when the corresponding graph has δn edges for δ = O ( 1 ). • MaxQP admits a ( 1 − ε ) -approximation in O ( n ) time when the corresponding graph and each of its minors have bounded local treewidth. • Unit MaxQP admits a ( 1 − ε ) -approximation in O ( n 2 ) time for H-minor free graphs.

Authors

• Danny Hermelin
• Leon Kellerhals TU Berlin
• Rolf Niedermeier Technische Universität Berlin
• Rami Pugatch

Keywords

• Combinatorial optimization
• Quadratic programming
• MaxQP
• Graph cuts
• Correlation clustering
• Ising spin glass