Hi! How to prove that sparsest cut always has an optimal solution which is the cut for some vertex-subset. Looks like it's should be a kind of fundamental theorem for sparsest cut. But I didn't ...
Here is the simple algorithm for approximating set cover problem using rounding: Algorithm 14.1 (Set cover via LP-rounding) Find an optimal solution to the LP-relaxation. Pick all sets ...
Hi Both, the greedy and the LP approach for Set Cover give a O(log n) approximation. Is there some inherent difference on the two approximation approaches? thanks