Why not to some constant like 3 or 4 dimension? I suspect that it is because Cholesky Decompostion will work only for $n \times n$ matrix $B$ where $B^TB = P$ where $P$ is a semidefinite matrix. Is it true? Or there is something else?
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ The short answer is because relaxing to vectors in n dimensions yields a problem that can be solved in polynomial time. Relaxing to vectors in fewer dimensions does not (unless e.g. P=NP). $\endgroup$– Neal YoungCommented Dec 30, 2017 at 3:40
-
$\begingroup$ @NealYoung Which problem? That of decomposing P into B^TB? $\endgroup$– Vimal Raj SharmaCommented Dec 30, 2017 at 8:08
-
$\begingroup$ The resulting optimization problem. That is, the relaxation of max cut that the algorithm uses. In that relaxation, if you were to restrict the vectors to smaller dimension, the problem would no longer be solvable in polynomial time. E.g. see Yuval's post. $\endgroup$– Neal YoungCommented Dec 31, 2017 at 4:22
-
$\begingroup$ Almost a duplicate of cs.stackexchange.com/questions/26262/… $\endgroup$– Neal YoungCommented Jan 10, 2018 at 14:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
The MAX-CUT algorithm relies on semidefinite programming, a convex optimization problem which can be solved in polynomial time. What you solve directly is the semidefinite program
$$ \begin{align*} & \max \sum_{ij} w_{ij} \frac{1-a_{ij}}{2} \\ s.t. \quad& (a_{ij})_{i,j=1}^n \text{ is positive semidefinite} \\ & a_{ii} = 1 \text{ for all $i$} \end{align*} $$
Given a solution for this program, you can extract the vectors using Cholesky decomposition.
The problem you are interested in is different:
$$ \begin{align*} & \max \sum_{ij} w_{ij} \frac{1-\langle v_i, v_j \rangle}{2} \\ s.t. \quad& v_i \in \mathbb{R}^d \\ & \|v_i\|^2 = 1 \end{align*} $$
When $d = 1$, this is just MAX-CUT. When $d$ is constant, optimizing over $\{v_i \in \mathbb{R}^d : \|v_i\| = 1 \}$ is likely NP-hard. When $d = n$, this can be solved using the semidefinite program described above. This is why we allow the dimension to be unbounded.
If you could force the dimension to be small, then you could improve the approximation ratio of the algorithm, see for example Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT by Avidor and Zwick. Assuming the unique games conjecture, however, the approximation guarantee of the Goemans–Williamson algorithm is tight. This shows that even in the particular case of MAX-CUT, it is likely that finding a low-dimensional solution cannot be done efficiently.
answered Dec 30, 2017 at 9:17
-
$\begingroup$ But where exactly is the problem arising? I am following this cs.cmu.edu/~anupamg/adv-approx/lecture14.pdf. The three points on page 2 will still remain valid for vectors of constant dimension and therefore the problem can still be formulated as semidefinite programming. I guess the problem will occur only in decomposition. Is it correct? $\endgroup$ Commented Dec 31, 2017 at 4:20
-
1$\begingroup$ Right, since what you're solving directly is the SDP, not the vector program. $\endgroup$ Commented Dec 31, 2017 at 6:32
-
$\begingroup$ @YuvalFilmus "When d is constant, optimizing over {vi∈Rd:∥vi∥=1} is likely NP-hard. ". Can you give a proof or perhaps elaborate? $d=1$ case is clearly $MAX$-$CUT$. $\endgroup$– TurboCommented Jul 2, 2020 at 23:09
-