3 ms·

It's an approximate algorithm (nothing wrong with that). I'm confused at how they claim O(m^{4/3}) (m is the number of edges) when even initializing an explici

It's an approximate algorithm (nothing wrong with that). I'm confused at how they claim O(m^{4/3}) (m is the number of edges) when even initializing an explicit n by n matrix is O(n^2), unless they assume that the graph isn't sparse (m>=k*n^1.5). Or perhaps the matrix is sparsely represented.

kenjackson 16y ago
On page 11 of the paper I reference above Spielman makes the following statement: "The most obvious way that sparsification can accelerate the solution of linear equations is by replacing the problem of solving systems in dense matrices by the problem of solving systems in sparse matrices. Recall that the Conjugate Gradient, used as a direct solver, can solve systems in n-dimensional matrices with m non-zero entries in time O(mn). So, if we could find a graph H with O(n) nonzero entries that was even a 1-approximation of G, then we could quickly solve systems in LG by using the Preconditioned Conjugate Gradient with LH as the preconditioner, and solving the systems in LH by the Conjugate Gradient. Each solve in H would then take time O(n^2), and the number of iterations of the PCG required to get an ǫ-accurate solution would be O(log ǫ−1). So, the total complexity would be O((m + n^2) log ǫ−1)." I'm not really sure how you get O(n) 1-approximations of G (or even really what a 1-approximation is yet, as I haven't really read the paper), but that seems to be the idea, I think.
- CountHackulus 16y ago
  A 1-approximation is an approximation within a factor of 1. Basically that means that the solution is nearly exact. A 2-approximation would be no more than twice as bad as the optimal solution, and an n-aproximation would be no more than n times as bad as the optimal solution. This is a common thing to use in randomized or approximate algorithms. For example, solving min-cut by assigning to 2 sets randomly is provably a 2-approximation.
  - JosefK 16y ago
    I believe you mean Max-Cut can be 2 approximated with the trivial random algorithm. Min cut can be solved exactly, and that algorithm would give an expected n^2 approx factor (for min cut).

kenjackson 16y ago

On page 11 of the paper I reference above Spielman makes the following statement: "The most obvious way that sparsification can accelerate the solution of linear equations is by replacing the problem of solving systems in dense matrices by the problem of solving systems in sparse matrices. Recall that the Conjugate Gradient, used as a direct solver, can solve systems in n-dimensional matrices with m non-zero entries in time O(mn). So, if we could find a graph H with O(n) nonzero entries that was even a 1-approximation of G, then we could quickly solve systems in LG by using the Preconditioned Conjugate Gradient with LH as the preconditioner, and solving the systems in LH by the Conjugate Gradient. Each solve in H would then take time O(n^2), and the number of iterations of the PCG required to get an ǫ-accurate solution would be O(log ǫ−1). So, the total complexity would be O((m + n^2) log ǫ−1)." I'm not really sure how you get O(n) 1-approximations of G (or even really what a 1-approximation is yet, as I haven't really read the paper), but that seems to be the idea, I think.

CountHackulus 16y ago
A 1-approximation is an approximation within a factor of 1. Basically that means that the solution is nearly exact. A 2-approximation would be no more than twice as bad as the optimal solution, and an n-aproximation would be no more than n times as bad as the optimal solution. This is a common thing to use in randomized or approximate algorithms. For example, solving min-cut by assigning to 2 sets randomly is provably a 2-approximation.
- JosefK 16y ago
  I believe you mean Max-Cut can be 2 approximated with the trivial random algorithm. Min cut can be solved exactly, and that algorithm would give an expected n^2 approx factor (for min cut).