论文标题
近似稀疏二次程序
Approximating Sparse Quadratic Programs
论文作者
论文摘要
给定一个矩阵$ a \ in \ mathbb {r}^{n \ times n} $，我们考虑了最大化$ x^税$受约束$ x \ in \ in \ { - 1,1 \}^n $约束的问题。 Charikar和Wirth [focs'04]称之为MAXQP的这个问题概括了Maxcut，并在数据聚类和物质无序磁相的研究中具有自然应用。 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.这两个结果都取决于求解MAXQP的半芬矿放松，其目前最好的运行时间是$ \ tilde {o}（n^{1.5} \ cdot \ cdot \ cdot \ min \ {n，n^{1.5} \}）$，$ n $是$ n $ in $ a $ a $ a $ a $ and tilde cartire and $ \ tilde; 在此续集中，我们放弃了半fine的方法和设计纯粹的组合近似算法，用于MaxQp的特殊情况，其中$ a $稀疏（即具有$ O（n）$ nonzero条目）。就运行时间而言，我们的算法优于半决赛方法，但就其近似保证而言，仍然具有竞争力。更具体地说，我们表明： -MAXQP在$ O（n \ lg n）$ time中承认$（1/2δ）$ - 近似，其中$δ$是相应图的最大程度。 -unitmaxqp，其中$ a \ in \ { - 1,0,1 \}^{n \ times n} $，在$ O（n）$ in $ o（n）$ in相应图为$ d $ -degeenate和a $（1/3Δ）$ o（$ o（1/3Δ）$ o（n^n^n^n^n^n^$ o（1/3δ）中时边缘。 -MAXQP承认$（1- \ varepsilon）$ - $ O（n）$时间近似相应的图表及其每个未成年人都限制了本地树宽。 -UnitMaxQP承认$（1- \ varepsilon）$ - $ O（n^2）$ time在相应图为$ h $ -minor免费时。
Given a matrix $A \in \mathbb{R}^{n\times n}$, we consider the problem of maximizing $x^TAx$ subject to the constraint $x \in \{-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 $\tilde{O}(n^{1.5}\cdot \min\{N,n^{1.5}\})$, where $N$ is the number of nonzero entries in $A$ and $\tilde{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 $Δ$ is the maximum degree of the corresponding graph. - UnitMaxQP, where $A \in \{-1,0,1\}^{n\times n}$, admits a $(1/2d)$-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. - 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.
