Difference between revisions of "Help talk:Trolls on wheels!"
From Algorithm Wiki
(Created page with "In my opinion the example solution is wrong as greedy would get an optimal solution here. A working construction can be found on the wikipedia page for set cover.") |
m (Trampin' all the way moved page Talk:TADM2E 1.6 to Help talk:Trolls on wheels!) |
||
| (5 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| − | + | The first counterexample shown is incorrect as greedy would get an optimal solution (2 sets). | |
| + | First, greedy would choose S3 since it contains 10 uncovered elements. | ||
| + | However, then, greedy would choose S4 since it contains 6 uncovered elements (not s2 | ||
| + | since it only contains 4 uncovered elements). | ||
| + | The union of s3 and s4 cover all elements (2 sets). | ||
| + | |||
| + | Is this more simply demonstrated with the following? | ||
| + | |||
| + | <math>S_1 = \{1, 3, 5\}</math><br> | ||
| + | <math>S_2 = \{1, 2\}</math><br> | ||
| + | <math>S_3 = \{3, 4\}</math><br> | ||
| + | <math>S_4 = \{5, 6\}</math> | ||
| + | |||
| + | Whatever you use as a tiebreaker is irrelevant in this counterexample, | ||
| + | and if you're really concerned about it, isn't the lack of any specified tiebreaker | ||
| + | in the problem a counterexample in and of itself? | ||
Latest revision as of 07:31, 15 April 2019
The first counterexample shown is incorrect as greedy would get an optimal solution (2 sets). First, greedy would choose S3 since it contains 10 uncovered elements. However, then, greedy would choose S4 since it contains 6 uncovered elements (not s2 since it only contains 4 uncovered elements). The union of s3 and s4 cover all elements (2 sets).
Is this more simply demonstrated with the following?
$ S_1 = \{1, 3, 5\} $
$ S_2 = \{1, 2\} $
$ S_3 = \{3, 4\} $
$ S_4 = \{5, 6\} $
Whatever you use as a tiebreaker is irrelevant in this counterexample, and if you're really concerned about it, isn't the lack of any specified tiebreaker in the problem a counterexample in and of itself?
