Help:Trolls on wheels! - Revision history

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

2019-04-15T07:31:59Z

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

Trampin' all the way: Undo revision 563 by Makar (talk)

2019-04-15T07:31:21Z

Undo revision 563 by Makar (talk)

Makar at 18:21, 2 September 2018

2018-09-02T18:21:06Z

Makar at 18:20, 2 September 2018

2018-09-02T18:20:19Z

Dbedrenko: Added colon

2017-12-16T13:51:34Z

Added colon

Dbedrenko: Removed counter-example one (it's wrong, see discussion page for explanation)

2017-12-16T13:50:44Z

Removed counter-example one (it's wrong, see discussion page for explanation)

Txmns at 19:04, 9 September 2017

2017-09-09T19:04:50Z

Ridgemcghee at 09:35, 4 December 2014

2014-12-04T09:35:59Z

Algowikiadmin: Recovering wiki

2014-09-11T18:22:32Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:13:15Z

Recovering wiki

New page

One counter-example consists of a series of subsets that increase in size exponentially, plus 2 additional subsets that each cover half of the elements. Example:

<math>S_1 = \{1, 2\}</math>
<br/>
<math>S_2 = \{3, 4, 5, 6\}</math>
<br/>
<math>S_3 = \{7, 8, 9, 10, 11, 12, 13, 14, 15, 16 \}</math>
<br/>
<math>S_4 = \{1, 2, 3, 4, 5, 6, 7, 8 \}</math>
<br/>
<math>S_5 = \{9, 10, 11, 12, 13, 14, 15, 16 \}</math>

The greedy algorithm will choose <math>S_3, S_2, S_1</math>, while the optimal solution is simply <math>S_4, S_5</math>

@@ Line 37: / Line 37: @@
 <br/>
 But the greedy algorithm might choose <math>S_2, S_3, S_1</math>.
 Counter-example 3:

@@ Line 37: / Line 37: @@
 <br/>
 But the greedy algorithm might choose <math>S_2, S_3, S_1</math>.
 Counter-example 3:

← Older revision		Revision as of 18:20, 2 September 2018
Line 37:		Line 37:
	<br/>		<br/>
	But the greedy algorithm might choose <math>S_2, S_3, S_1</math>.		But the greedy algorithm might choose <math>S_2, S_3, S_1</math>.
		+
		+	Counter-example 3:
		+
		+	<math>U = \{1, 2, 3, 4, 5, 6\}</math>
		+	<br/>
		+	<math>S_1 = \{2, 3, 4, 5\}</math>
		+	<br/>
		+	<math>S_2 = \{1, 2, 3\}</math>
		+	<br/>
		+	<math>S_3 = \{4, 5, 6\}</math>
		+
		+	There is an optimal solution: <math>S_2, S_3</math> (2 subsets).
		+	<br/>
		+	A greedy algorithm will choose <math>S_1, S_2, S_3</math> (3 subsets)

← Older revision		Revision as of 13:51, 16 December 2017
Line 1:		Line 1:
−	Counter-example 1	+	Counter-example 1:

	<math>U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14\}</math>		<math>U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14\}</math>

@@ Line 1: / Line 1: @@
-One counter-example consists of a series of subsets that increase in size exponentially, plus 2 additional subsets that each cover half of the elements. Example:
+Counter-example 1
 <math>U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14\}</math>
@@ Line 39: / Line 24: @@
-Counter-example 3:
+Counter-example 2:
 <math>U = \{1, 2, 3, 4, 5\}</math>

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

@@ Line 12: / Line 12: @@
 The greedy algorithm will choose <math>S_3, S_2, S_1</math>, while the optimal solution is simply <math>S_4, S_5</math>
-<br/>
-<br/>
 Counter-example 2 (in case you spot an error in counter-example 1 - see Discussion):
-<br/>
 <math>U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14\}</math>
 <br/>
@@ Line 27: / Line 27: @@
 <br/>
 <math>S_5 = \{8, 9, 10, 11, 12, 13, 14\}</math>
-<br/><br/>
 There is an optimal solution: <math>S_4, S_5</math> (2 subsets).
 <br/>
@@ Line 37: / Line 37: @@
 <br/>
 . <math>S_3</math> since it then contains 2 uncovered elements (more than any other subset)
 <br/>

← Older revision		Revision as of 09:35, 4 December 2014
Line 12:		Line 12:

	The greedy algorithm will choose <math>S_3, S_2, S_1</math>, while the optimal solution is simply <math>S_4, S_5</math>		The greedy algorithm will choose <math>S_3, S_2, S_1</math>, while the optimal solution is simply <math>S_4, S_5</math>
		+	<br/>
		+	<br/>
		+	Counter-example 2 (in case you spot an error in counter-example 1 - see Discussion):
		+	<br/>
		+	<math>U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14\}</math>
		+	<br/>
		+	<math>S_1 = \{1, 2, 4, 6, 8, 10, 12, 14\}</math>
		+	<br/>
		+	<math>S_2 = \{3, 5, 9, 11\}</math>
		+	<br/>
		+	<math>S_3 = \{7, 13\}</math>
		+	<br/>
		+	<math>S_4 = \{1, 2, 3, 4, 5, 6, 7\}</math>
		+	<br/>
		+	<math>S_5 = \{8, 9, 10, 11, 12, 13, 14\}</math>
		+	<br/><br/>
		+	There is an optimal solution: <math>S_4, S_5</math> (2 subsets).
		+	<br/>
		+	A greedy algorithm will choose <math>S_1, S_2, S_3</math> (3 subsets):
		+	<br/>
		+	1. <math>S_1</math> since it contains 8 uncovered elements (more than any other subset)
		+	<br/>
		+	2. <math>S_2</math> since it then contains 4 uncovered elements (more than any other subset)
		+	<br/>
		+	3. <math>S_3</math> since it then contains 2 uncovered elements (more than any other subset)
		+	<br/>

@@ Line 1: / Line 1: @@
 One counter-example consists of a series of subsets that increase in size exponentially, plus 2 additional subsets that each cover half of the elements. Example:
-&lt;math&gt;S_1 = \{1, 2\}&lt;/math&gt;
+<math>S_1 = \{1, 2\}</math>
-&lt;br/&gt;
+<br/>
-&lt;math&gt;S_2 = \{3, 4, 5, 6\}&lt;/math&gt;
+<math>S_2 = \{3, 4, 5, 6\}</math>
-&lt;br/&gt;
+<br/>
-&lt;math&gt;S_3 = \{7, 8, 9, 10, 11, 12, 13, 14, 15, 16 \}&lt;/math&gt;
+<math>S_3 = \{7, 8, 9, 10, 11, 12, 13, 14, 15, 16 \}</math>
-&lt;br/&gt;
+<br/>
-&lt;math&gt;S_4 = \{1, 2, 3, 4, 5, 6, 7, 8 \}&lt;/math&gt;
+<math>S_4 = \{1, 2, 3, 4, 5, 6, 7, 8 \}</math>
-&lt;br/&gt;
+<br/>
-&lt;math&gt;S_5 = \{9, 10, 11, 12, 13, 14, 15, 16 \}&lt;/math&gt;
+<math>S_5 = \{9, 10, 11, 12, 13, 14, 15, 16 \}</math>
-The greedy algorithm will choose &lt;math&gt;S_3, S_2, S_1&lt;/math&gt;, while the optimal solution is simply &lt;math&gt;S_4, S_5&lt;/math&gt;
+The greedy algorithm will choose <math>S_3, S_2, S_1</math>, while the optimal solution is simply <math>S_4, S_5</math>