3 ms·
The first approximation algorithm, invented by Erdős. The best known by Goemans and Williamson achieves about 0.868 (IIRC) approximation, and is a thing of beau
by karmakurtisaani 3y ago
The first approximation algorithm, invented by Erdős. The best known by Goemans and Williamson achieves about 0.868 (IIRC) approximation, and is a thing of beauty as well.
- akoboldfrying 3y agoA rare example of a constant-factor approximation algorithm with a constant that's... actually useful in practice.