Help talk:Trolls on wheels! - Revision history

Trampin' all the way: Trampin' all the way moved page Talk:TADM2E 1.6 to Help talk:Trolls on wheels!

2019-04-15T07:31:59Z

Trampin' all the way moved page Talk:TADM2E 1.6 to Help talk:Trolls on wheels!

Jprykop at 04:16, 24 December 2014

2014-12-24T04:16:45Z

Jprykop: Possible simpler example, depending on your views on unspecified tiebreakers

2014-12-24T04:15:42Z

Possible simpler example, depending on your views on unspecified tiebreakers

Ridgemcghee at 09:36, 4 December 2014

2014-12-04T09:36:50Z

Ridgemcghee at 09:05, 4 December 2014

2014-12-04T09:05:23Z

Ridgemcghee at 09:04, 4 December 2014

2014-12-04T09:04:41Z

Guwek: 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."

2014-11-06T15:43:26Z

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."

New page

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.

@@ Line 7: / Line 7: @@
 Is this more simply demonstrated with the following?
-<math>S_1 = \{1, 2\}</math>
+<math>S_1 = \{1, 3, 5\}</math><br>
-<math>S_1 = \{1, 3, 5\}</math>
+<math>S_2 = \{1, 2\}</math><br>
-<math>S_2 = \{1, 2\}</math>
+<math>S_3 = \{3, 4\}</math><br>
 <math>S_4 = \{5, 6\}</math>

← Older revision		Revision as of 04:15, 24 December 2014
Line 4:		Line 4:
	since it only contains 4 uncovered elements).		since it only contains 4 uncovered elements).
	The union of s3 and s4 cover all elements (2 sets).		The union of s3 and s4 cover all elements (2 sets).
		+
		+	Is this more simply demonstrated with the following?
		+
		+	<math>S_1 = \{1, 2\}</math>
		+	<math>S_1 = \{1, 3, 5\}</math>
		+	<math>S_2 = \{1, 2\}</math>
		+	<math>S_3 = \{3, 4\}</math>
		+	<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?

← Older revision		Revision as of 09:36, 4 December 2014
Line 4:		Line 4:
	since it only contains 4 uncovered elements).		since it only contains 4 uncovered elements).
	The union of s3 and s4 cover all elements (2 sets).		The union of s3 and s4 cover all elements (2 sets).
−
−	~~However, there is a correct counterexample (see counterexample 2).~~

← Older revision		Revision as of 09:05, 4 December 2014
Line 5:		Line 5:
	The union of s3 and s4 cover all elements (2 sets).		The union of s3 and s4 cover all elements (2 sets).

−	However, there is a ~~solution~~ counterexample (see counterexample 2).	+	However, there is a correct counterexample (see counterexample 2).

← Older revision		Revision as of 09:04, 4 December 2014
Line 1:		Line 1:
−	~~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.	+	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).
		+
		+	However, there is a solution counterexample (see counterexample 2).

← Older revision	Revision as of 07:31, 15 April 2019
(No difference)