All Questions
2 questions
1
vote
1
answer
70
views
Heuristic for choosing n-vectors from n-sets
my given problem is:
choose n-vectors from n-sets (one vector from each set) so that the biggest element in the sum of the chosen vectors is minimal. Unfortunately the problem is NP-hard. So I'm ...
- 11
1
vote
1
answer
639
views
Approximate Set Cover Problem by Rounding
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 $S$ for ...
