VC-SNDP:spider decomposition - ประวัติรุ่นแก้ไข

Jittat: /* Spider decomposition บนกรณี bipartite */

2009-02-27T17:18:02Z

Spider decomposition บนกรณี bipartite

Jittat: /* Spider decomposition บนกรณี bipartite */

2009-02-27T17:16:13Z

Spider decomposition บนกรณี bipartite

Jittat: /* Spider decomposition บนกรณี bipartite */

2009-02-27T17:14:27Z

Spider decomposition บนกรณี bipartite

Jittat: /* Spider decomposition บนกรณี bipartite */

2009-02-27T16:52:18Z

Spider decomposition บนกรณี bipartite

Jittat: /* Spider decomposition บนกรณี bipartite */

2009-02-27T16:39:06Z

Spider decomposition บนกรณี bipartite

Jittat: /* Decomposition */

2009-02-27T16:37:00Z

Decomposition

Top: /* ค่าใช้จ่าย */

2009-02-25T10:00:09Z

ค่าใช้จ่าย

Jittat: /* ภาพรวม (ตาม Chekuri-Korula) */

2009-02-25T09:49:43Z

ภาพรวม (ตาม Chekuri-Korula)

Jittat: /* ค่าใช้จ่าย */

2009-02-25T09:32:47Z

ค่าใช้จ่าย

Jittat: /* บทพิสูจน์: มี spider decomposition */

2009-02-25T09:31:48Z

บทพิสูจน์: มี spider decomposition

@@ แถว 50: / แถว 50: @@
 ** ถ้ามีแค่ edge เดียว --- ให้เลือก edge ที่ติดกับ <math>v</math> ไปยัง อีก terminal หนึ่ง สมมติว่าเป็น <math>w</math>, ให้ <math>w</math> เป็น head ของ spider ที่มี <math>u</math> เป็น foot
-พิจารณารูปด้านล่าง (กรณี k=2)  สังเกตว่า black vertex ที่สามจากซ้าย เป็น foot ของ 2 spiders และเป็น head ของอีก 1 spider
+พิจารณารูปด้านล่าง (กรณี k=2)  รูปซ้ายแสดงการเลือก เส้นเชื่อมสีเขียวคือเส้นเชื่อมที่ไม่ถูกเลือก  รูปขวาแสดง spider 2 spider, สังเกตว่า black vertex ที่สามจากซ้าย เป็น foot ของ 2 spiders และเป็น head ของอีก 1 spider
 [[ภาพ:Spider-bipartite.png]]

@@ แถว 49: / แถว 49: @@
 ** ถ้ามีอย่างน้อย 2 edge --- ให้ vertex นั้นเป็น head ของ spider และให้แต่ละ terminal ที่เลือก edge เหล่านั้นเป็น foot ของ spider
 ** ถ้ามีแค่ edge เดียว --- ให้เลือก edge ที่ติดกับ <math>v</math> ไปยัง อีก terminal หนึ่ง สมมติว่าเป็น <math>w</math>, ให้ <math>w</math> เป็น head ของ spider ที่มี <math>u</math> เป็น foot
 [[ภาพ:Spider-bipartite.png]]

@@ แถว 49: / แถว 49: @@
 ** ถ้ามีอย่างน้อย 2 edge --- ให้ vertex นั้นเป็น head ของ spider และให้แต่ละ terminal ที่เลือก edge เหล่านั้นเป็น foot ของ spider
 ** ถ้ามีแค่ edge เดียว --- ให้เลือก edge ที่ติดกับ <math>v</math> ไปยัง อีก terminal หนึ่ง สมมติว่าเป็น <math>w</math>, ให้ <math>w</math> เป็น head ของ spider ที่มี <math>u</math> เป็น foot
 ===บทพิสูจน์: มี spider decomposition (Thm 4.4 ใน Chekuri-Korula)===

@@ แถว 40: / แถว 40: @@
 ===Spider decomposition บนกรณี bipartite===
 พิจารณากรณีที่ไม่มีเส้นเชื่อมระหว่าง 2 white vertices  เราสามารถสมมติว่าไม่มีเส้นเชื่อมระหว่าง black vertices ได้ด้วย โดยการใส่จุดขาวลงไปตรงกลางเส้นเชื่อมระหว่าง black vertices  ดังนั้นเราอยู่ในกรณีที่กราฟเป็น bipartite โดยกลุ่มหนึ่งคือ white vertices อีกกลุ่มคือ black vertices
 ===บทพิสูจน์: มี spider decomposition (Thm 4.4 ใน Chekuri-Korula)===

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 16:39, 27 กุมภาพันธ์ 2552
แถว 39:		แถว 39:

	===Spider decomposition บนกรณี bipartite===		===Spider decomposition บนกรณี bipartite===
		+	พิจารณากรณีที่ไม่มีเส้นเชื่อมระหว่าง 2 white vertices เราสามารถสมมติว่าไม่มีเส้นเชื่อมระหว่าง black vertices ได้ด้วย โดยการใส่จุดขาวลงไปตรงกลางเส้นเชื่อมระหว่าง black vertices ดังนั้นเราอยู่ในกรณีที่กราฟเป็น bipartite โดยกลุ่มหนึ่งคือ white vertices อีกกลุ่มคือ black vertices

	===บทพิสูจน์: มี spider decomposition (Thm 4.4 ใน Chekuri-Korula)===		===บทพิสูจน์: มี spider decomposition (Thm 4.4 ใน Chekuri-Korula)===

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 16:37, 27 กุมภาพันธ์ 2552
แถว 37:		แถว 37:

	ด้านบนคือหัวใจของบทพิสูจน์ของ Lemma 4.3 ใน Chekuri-Korula		ด้านบนคือหัวใจของบทพิสูจน์ของ Lemma 4.3 ใน Chekuri-Korula
		+
		+	===Spider decomposition บนกรณี bipartite===

	===บทพิสูจน์: มี spider decomposition (Thm 4.4 ใน Chekuri-Korula)===		===บทพิสูจน์: มี spider decomposition (Thm 4.4 ใน Chekuri-Korula)===

@@ แถว 92: / แถว 92: @@
 จาก claim ดังกล่าว approximation ratio สามารถพิสูจน์ได้โดยใช้ linearity of expectation.
 == Reduction lemma ==
 === Proof of the spider decomposition with the reduction lemma ===

@@ แถว 7: / แถว 7: @@
 === ภาพรวม (ตาม Chekuri-Korula) ===
 * อัลกอริทึมใช้ greedy augmentation บนลำดับแบบสุ่มของ terminal
-* cost พิสูจน์ด้วย '''Theorem 4.2''' ที่แสดงว่า cost ในการทำ augmentation '''จากทุกโหนด''' ไม่เกิน <math>8k\cdot OPT</math>
+* cost พิสูจน์ด้วย '''Theorem 4.2''' ที่แสดงว่า cost ในการทำ augmentation '''จากทุกโหนด''' ไม่เกิน <math>8k\cdot OPT</math> (ดูด้านล่าง)
 * key lemma คือ '''Lemma 4.3''' ที่แสดงว่ามีจากทุก ๆ terminal มี set ของ internal vertex disjoint path ไปยัง terminal อื่น ๆ  ที่ cost รวมไม่เกิน 2 เท่าของ opt, lemma นี้พิสูจน์ได้โดยแสดงว่ามี spider decomposition
 * spider decomposition พิสูจน์ด้วย Reduction Lemma

@@ แถว 89: / แถว 89: @@
 * <math>OPT(T')\leq OPT(T)</math>
 * ใช้ Theorem 4.2 บน <math>T_i</math> จะได้ว่า <math>\sum_{t\in T_i} AugCost(t)\leq 8k\cdot OPT(T_i)\leq 8k\cdot OPT(T)</math>
-* สังเกตว่า given <math>T_i</math> โหนดสุดท้ายที่จะถูก add (นั่นคือ <math>t_i</math> สามารถเป็นโหนดใด ๆ ก็ได้ใน <math>T_i</math> ดังนั้น expected cost คือ <math>8k\cdot OPT/i</math> ตามต้องการ เพราะ <math>|T_i|=i</math>
+* สังเกตว่า given <math>T_i</math> โหนดสุดท้ายที่จะถูก add (นั่นคือ <math>t_i</math>) สามารถเป็นโหนดใด ๆ ก็ได้ใน <math>T_i</math> ดังนั้น expected cost คือ <math>8k\cdot OPT/i</math> ตามต้องการ เพราะ <math>|T_i|=i</math>
 จาก claim ดังกล่าว approximation ratio สามารถพิสูจน์ได้โดยใช้ linearity of expectation.

@@ แถว 38: / แถว 38: @@
 ด้านบนคือหัวใจของบทพิสูจน์ของ Lemma 4.3 ใน Chekuri-Korula
-===บทพิสูจน์: มี spider decomposition===
+===บทพิสูจน์: มี spider decomposition (Thm 4.4 ใน Chekuri-Korula)===
   ส่วนนี้จะมาเขียนทีหลัง