1 Attachment(s)

algorithm for Max Cut problem using matrix decomposition

Hi all,

I am looking at the attached paper, trying to learn how to solve a Max Cut problem. The authors achieve this by decomposing the matrix in question into several cut matrices and then considering intersections of vertices represented by these matrices with the vertices in a cut. On page 7 in section 3.1 they approximate the number of elements in a specific intersections as \bar{f}_t and \bar{g}_t

They claim that each of these parameters can take O(1/\epsilon^3) values where \epsilon is chosen during the matrix decomposition. Does anyone have a clue why the parameters can take O(1/\epsilon^3) values?

Thanks

choschech