Results 1 to 1 of 1

Math Help - algorithm for Max Cut problem using matrix decomposition

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    5

    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
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Problem with the simplex algorithm with LU Decomposition
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: May 19th 2011, 09:34 AM
  2. Crout algorithm to finding LU decomposition
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: October 20th 2010, 09:19 AM
  3. Spectral Decomposition of a Matrix
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 17th 2010, 11:03 AM
  4. Need help in Matrix Decomposition
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: January 24th 2010, 02:28 AM
  5. Proof: every Hermitian matrix has eigenvalue decomposition
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: March 16th 2009, 10:53 AM

Search Tags


/mathhelpforum @mathhelpforum