An SDP Primal-Dual Algorithm for Approximating the Lovász-Theta Function
Lists
Only you see this
Abstract
The Lovász ϑ-function (Lovász in IEEE Trans. Inf. Theory, 25:1–7, 1979) of a graph G=(V,E) can be defined as the maximum of the sum of the entries of a positive semidefinite matrix X, whose trace Tr(X) equals 1, and X ij =0 whenever {i,j}∈E. This function appears as a subroutine for many algorithms for graph problems such as maximum independent set and maximum clique. We apply Arora and Kale’s primal-dual method for SDP to design an algorithm to approximate the ϑ-function within an additive error of δ>0, which runs in time $O(\frac{\vartheta ^{2} n^{2}}{\delta^{2}} \log n \cdot M_{e})$ , where ϑ=ϑ(G) and M e =O(n 3) is the time for a matrix exponentiation operation. It follows that for perfect graphs G, our primal-dual method computes ϑ(G) exactly in time O(ϑ 2 n 5logn).Moreover, our techniques generalize to the weighted Lovász ϑ-function, and both the maximum independent set weight and the maximum clique weight for vertex weighted perfect graphs can be approximated within a factor of (1+ϵ) in time O(ϵ −2 n 5logn).
BibTeX
@inproceedings{chan2014sdp,
author = {T.-H. Hubert Chan and Kevin L. Chang and Rajiv Raman},
title = {{An SDP Primal-Dual Algorithm for Approximating the Lovász-Theta Function}},
booktitle = {Algorithmica},
year = {2014},
url = {https://openreview.net/forum?id=NTLW0fEvUFw},
}Loading related content...