University:
Massachusetts Institute of Technology
Course:
18.S096 | Topics in Mathematics of Data Science
Academic year:

2024
Views:

45

Pages:

9
Author:

geontandajs2

8 8.1 Approximation Algorithms and Max-Cut The Max-Cut problem Unless the widely believed P 6= N P conjecture is false, there is no polynomial algorithm that can solve all instances of an NP-hard problem. Thus, when faced with an NP-hard problem (such as the Max-Cut problem discussed below) one has three options: to use an exponential type algorithm that solves exactly the problem in all instances, to design polynomial time algorithms that only work for some of the instances (hopefully the typical ones!), or to design polynomial algorithms that, in any instance, produce guaranteed approximate solutions. This section is about the third option. The second is discussed in later in the course, in the context of community detection. The Max-Cut problem is the following: Given a graph G = (V, E) with non-negative weights wij on the edges, find a set S ⊂ V for which cut(S) is maximal. Goemans and Williamson [GW95] introduced an approximation algorithm that runs in polynomial time and has a randomized component to it, and is able to obtain a cut whose expected value is guaranteed to be no smaller than a particular constant αGW times the optimum cut. The constant αGW is referred to as the approximation ratio. Let V = {1, . . . , n}. One can restate Max-Cut as P max 21 i 0.87. It is then clear that X 1 1X E[W ] = wij arccos(uTi uj ) ≥ αGW wij (1 − uTi uj ). π 2 i 0, the problem of distinguishing whether an instance of the Unique Games Problem is such that it is possible to agree with a ≥ 1 − fraction of the constraints or it is not possible to even agree with a fraction of them, is NP-hard. There is a sub-exponential time algorithm capable of distinguishing such instances of the unique games problem [ABS10], however no polynomial time algorithm has been found so far. At the moment one of the strongest candidates to break the Unique Games Conjecture is a relaxation based on the Sum-of-squares hierarchy that we will discuss below. Open Problem 8.1 Is the Unique Games conjecture true? In particular, can it be refuted by a constant degree Sum-of-squares relaxation? Remarkably, approximating Max-Cut with an approximation ratio better than αGW is has hard as refuting the Unique Games Conjecture (UG-hard) [KKMO05]. More generality, if the Unique Games Conjecture is true, the semidefinite programming approach described above produces optimal approximation ratios for a large class of problems [Rag08]. Not depending on the Unique Games Conjecture, there is a NP-hardness of approximation of 16 17 for Max-Cut [Has02]. Remark 8.3 Note that a simple greedy method that assigns membership to each vertex as to maximize the number of edges cut involving vertices already assigned achieves an approximation ratio of 12 (even of 12 of the total number of edges, not just of the optimal cut). 8.3 A Sums-of-Squares interpretation We now give a different interpretation to the approximation ratio obtained above. Let us first slightly reformulate the problem (recall that wii = 0). 1X wij (1 − yi yj ) = yi =±1 2 max i