A Faster Algorithm for Max Cut in Dense Graphs
share
We design an algorithm for approximating the size of Max Cut in dense graphs. Given a proximity parameter ε∈ (0,1), our algorithm approximates the size of Max Cut of a graph G with n vertices, within an additive error of ε n^2, with sample complexity 𝒪(1/ε^3log^2 1/εloglog1/ε) and query complexity of 𝒪(1/ε^4log^3 1/εloglog1/ε). Since Goldreich, Goldwasser and Ron (JACM 98) gave the first algorithm with sample complexity 𝒪(1/ε^5log1/ε) and query complexity of 𝒪(1/ε^7log^2 1/ε), there have been several efforts employing techniques from diverse areas with a focus on improving the sample and query complexities. Our work makes the first improvement in the sample complexity as well as query complexity after more than a decade from the previous best results of Alon, Vega, Kannan and Karpinski (JCSS 03) and of Mathieu and Schudy (SODA 08) respectively, both with sample complexity 𝒪(1/ε^4log1/ε). We also want to note that the best time complexity of this problem was by Alon, Vega, Karpinski and Kannan (JCSS 03). By combining their result with an approximation technique by Arora, Karger and Karpinski (STOC 95), they obtained an algorithm with time complexity of 2^𝒪(1/ε^2log1/ε). In this work, we have improved this further to 2^𝒪(1/εlog1/ε ).
READ FULL TEXT