News for hackers. Stuff that matters.
Re:First improvement of fundamental algorithm in 10 years by CountHackulus on Monday September 27, 2010 @10:30PM (#1734334)
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.

Re:First improvement of fundamental algorithm in 10 years by JosefK on Tuesday September 28, 2010 @12:41PM (#1736240)
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).