https://www.esoterum.org/mw/index.php?action=history&feed=atom&title=CSE550_Combinatorial_Algorithms%2FIntractability
CSE550 Combinatorial Algorithms/Intractability - Revision history
2026-10-23T10:12:27Z
Revision history for this page on the wiki
MediaWiki 1.43.11
https://www.esoterum.org/mw/index.php?title=CSE550_Combinatorial_Algorithms/Intractability&diff=1332&oldid=prev
Baker at 05:37, 8 December 2007
2007-12-08T05:37:51Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 23:37, 7 December 2007</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l55">Line 55:</td>
<td colspan="2" class="diff-lineno">Line 55:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*Taehan Lee, Sungsoo Park, [http://www.sciencedirect.com.ezproxy1.lib.asu.edu/science?_ob=MImg&_imagekey=B6VCT-43T1P14-6-37&_cdi=5963&_user=56861&_orig=search&_coverDate=11%2F16%2F2001&_sk=998649998&view=c&wchp=dGLzVzz-zSkWz&md5=9651f4b5c3225410d86e1cdfa7d4cc5c&ie=/sdarticle.pdf "An integer programming approach to the time slot assignment problem in SS/TDMA systems with intersatellite links"], European Journal of Operational Research, November 2001</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*Taehan Lee, Sungsoo Park, [http://www.sciencedirect.com.ezproxy1.lib.asu.edu/science?_ob=MImg&_imagekey=B6VCT-43T1P14-6-37&_cdi=5963&_user=56861&_orig=search&_coverDate=11%2F16%2F2001&_sk=998649998&view=c&wchp=dGLzVzz-zSkWz&md5=9651f4b5c3225410d86e1cdfa7d4cc5c&ie=/sdarticle.pdf "An integer programming approach to the time slot assignment problem in SS/TDMA systems with intersatellite links"], European Journal of Operational Research, November 2001</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*William Cook, László Lovász, Paul D. Seymour, [http://books.google.com/books?id=Mhf4Zmq1Q3cC&pg=PA387&lpg=PA387&dq=linear+program+for+edge+coloring&source=web&ots=wJ7HXep1lM&sig=upC44m0pbk95WLjNyOz5FSKYl-U "Combinatorial Optimization: Papers from the Dimacs Special Year"], Mathematics, 1995 </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*William Cook, László Lovász, Paul D. Seymour, [http://books.google.com/books?id=Mhf4Zmq1Q3cC&pg=PA387&lpg=PA387&dq=linear+program+for+edge+coloring&source=web&ots=wJ7HXep1lM&sig=upC44m0pbk95WLjNyOz5FSKYl-U "Combinatorial Optimization: Papers from the Dimacs Special Year"], Mathematics, 1995 </div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">*Richard Cole, Kirstin Ost, Stefan Schirra, "EdgeColoring Bipartite Multigraphs in 0(E log D) Time", April 18, 2000 </ins></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q5 ===</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q5 ===</div></td></tr>
</table>
Baker
https://www.esoterum.org/mw/index.php?title=CSE550_Combinatorial_Algorithms/Intractability&diff=1331&oldid=prev
Baker at 10:28, 7 December 2007
2007-12-07T10:28:49Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 04:28, 7 December 2007</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l54">Line 54:</td>
<td colspan="2" class="diff-lineno">Line 54:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://books.google.com/books?id=ymJTEjPg6CcC&pg=PT125&lpg=PT125&dq=edge+coloring+bipartite+multigraph+lp&source=web&ots=2J_0-ug5n6&sig=kOcj0lJmyQk5DmQty0pbnOVwQXQ ''Handbook of Scheduling: Algorithms, Models, and Performance Analysis''], By Joseph Y-T. Leung (bipartite multi-graph edge coloring)</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://books.google.com/books?id=ymJTEjPg6CcC&pg=PT125&lpg=PT125&dq=edge+coloring+bipartite+multigraph+lp&source=web&ots=2J_0-ug5n6&sig=kOcj0lJmyQk5DmQty0pbnOVwQXQ ''Handbook of Scheduling: Algorithms, Models, and Performance Analysis''], By Joseph Y-T. Leung (bipartite multi-graph edge coloring)</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*Taehan Lee, Sungsoo Park, [http://www.sciencedirect.com.ezproxy1.lib.asu.edu/science?_ob=MImg&_imagekey=B6VCT-43T1P14-6-37&_cdi=5963&_user=56861&_orig=search&_coverDate=11%2F16%2F2001&_sk=998649998&view=c&wchp=dGLzVzz-zSkWz&md5=9651f4b5c3225410d86e1cdfa7d4cc5c&ie=/sdarticle.pdf "An integer programming approach to the time slot assignment problem in SS/TDMA systems with intersatellite links"], European Journal of Operational Research, November 2001</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*Taehan Lee, Sungsoo Park, [http://www.sciencedirect.com.ezproxy1.lib.asu.edu/science?_ob=MImg&_imagekey=B6VCT-43T1P14-6-37&_cdi=5963&_user=56861&_orig=search&_coverDate=11%2F16%2F2001&_sk=998649998&view=c&wchp=dGLzVzz-zSkWz&md5=9651f4b5c3225410d86e1cdfa7d4cc5c&ie=/sdarticle.pdf "An integer programming approach to the time slot assignment problem in SS/TDMA systems with intersatellite links"], European Journal of Operational Research, November 2001</div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">*William Cook, László Lovász, Paul D. Seymour, [http://books.google.com/books?id=Mhf4Zmq1Q3cC&pg=PA387&lpg=PA387&dq=linear+program+for+edge+coloring&source=web&ots=wJ7HXep1lM&sig=upC44m0pbk95WLjNyOz5FSKYl-U "Combinatorial Optimization: Papers from the Dimacs Special Year"], Mathematics, 1995 </ins></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q5 ===</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q5 ===</div></td></tr>
</table>
Baker
https://www.esoterum.org/mw/index.php?title=CSE550_Combinatorial_Algorithms/Intractability&diff=1330&oldid=prev
Baker at 06:55, 7 December 2007
2007-12-07T06:55:31Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 00:55, 7 December 2007</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l14">Line 14:</td>
<td colspan="2" class="diff-lineno">Line 14:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*> Alexander Schrijver, [http://homepages.cwi.nl/~lex/files/histco.pdf "On the history of combinatorial optimization (till 1960)"]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*> Alexander Schrijver, [http://homepages.cwi.nl/~lex/files/histco.pdf "On the history of combinatorial optimization (till 1960)"]</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://ioe.engin.umich.edu/people/fac/books/murty/network_programming/ Network Programming (Internet Edition)], Katta G. Murty</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://ioe.engin.umich.edu/people/fac/books/murty/network_programming/ Network Programming (Internet Edition)], Katta G. Murty</div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">*> [ftp://ftp.nada.kth.se/Theory/Viggo-Kann/compendium.ps A Compendium of NP-Complete Problems]</ins></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== HW 6 ==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== HW 6 ==</div></td></tr>
</table>
Baker
https://www.esoterum.org/mw/index.php?title=CSE550_Combinatorial_Algorithms/Intractability&diff=1328&oldid=prev
Baker at 05:26, 7 December 2007
2007-12-07T05:26:00Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 23:26, 6 December 2007</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l56">Line 56:</td>
<td colspan="2" class="diff-lineno">Line 56:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q5 ===</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q5 ===</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*M. R. Garey; R. L. Graham; D. S. Johnson; D. E. Knuth, [http://www.jstor.org.ezproxy1.lib.asu.edu/cgi-bin/jstor/printpage/00361399/di974712/97p0084s/0.pdf?backcontext=page&dowhat=Acrobat&config=jstor&userID=81dbf4d5@asu.edu/01c0a8487432ec116b3088727&0.pdf "Complexity Results for Bandwidth Minimization"], SIAM Journal on Applied Mathematics, Vol. 34, No. 3., May, 1978</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*M. R. Garey; R. L. Graham; D. S. Johnson; D. E. Knuth, [http://www.jstor.org.ezproxy1.lib.asu.edu/cgi-bin/jstor/printpage/00361399/di974712/97p0084s/0.pdf?backcontext=page&dowhat=Acrobat&config=jstor&userID=81dbf4d5@asu.edu/01c0a8487432ec116b3088727&0.pdf "Complexity Results for Bandwidth Minimization"], SIAM Journal on Applied Mathematics, Vol. 34, No. 3., May, 1978</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>*David Muradian, [http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6V1G-48GFSHM-6-1&_cdi=5674&_user=56861&_orig=search&_coverDate=10%2F14%2F2003&_sk=996929996&view=c&wchp=<del style="font-weight: bold; text-decoration: none;">dGLbVzW</del>-<del style="font-weight: bold; text-decoration: none;">zSkWA</del>&md5=5809648ff08491822375b595ea376e9a&ie=/sdarticle.pdf "The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete"], Theoretical Computer Science 307, 2003</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>*David Muradian, [http://www.sciencedirect.com<ins style="font-weight: bold; text-decoration: none;">.ezproxy1.lib.asu.edu</ins>/science?_ob=MImg&_imagekey=B6V1G-48GFSHM-6-1&_cdi=5674&_user=56861&_orig=search&_coverDate=10%2F14%2F2003&_sk=996929996&view=c&wchp=<ins style="font-weight: bold; text-decoration: none;">dGLzVzz</ins>-<ins style="font-weight: bold; text-decoration: none;">zSkzk</ins>&md5=5809648ff08491822375b595ea376e9a&ie=/sdarticle.pdf "The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete"], Theoretical Computer Science 307, 2003</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Project ==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Project ==</div></td></tr>
</table>
Baker
https://www.esoterum.org/mw/index.php?title=CSE550_Combinatorial_Algorithms/Intractability&diff=1327&oldid=prev
Baker at 05:18, 7 December 2007
2007-12-07T05:18:32Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 23:18, 6 December 2007</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l55">Line 55:</td>
<td colspan="2" class="diff-lineno">Line 55:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q5 ===</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q5 ===</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>*M. R. Garey; R. L. Graham; D. S. Johnson; D. E. Knuth, [http://www.jstor.org/<del style="font-weight: bold; text-decoration: none;">view</del>/00361399/di974712/97p0084s/0 "Complexity Results for Bandwidth Minimization"], SIAM Journal on Applied Mathematics, Vol. 34, No. 3., May, 1978</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>*M. R. Garey; R. L. Graham; D. S. Johnson; D. E. Knuth, [http://www.jstor.org<ins style="font-weight: bold; text-decoration: none;">.ezproxy1.lib.asu.edu</ins>/<ins style="font-weight: bold; text-decoration: none;">cgi-bin/jstor/printpage</ins>/00361399/di974712/97p0084s/0<ins style="font-weight: bold; text-decoration: none;">.pdf?backcontext=page&dowhat=Acrobat&config=jstor&userID=81dbf4d5@asu.edu/01c0a8487432ec116b3088727&0.pdf </ins>"Complexity Results for Bandwidth Minimization"], SIAM Journal on Applied Mathematics, Vol. 34, No. 3., May, 1978</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*David Muradian, [http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6V1G-48GFSHM-6-1&_cdi=5674&_user=56861&_orig=search&_coverDate=10%2F14%2F2003&_sk=996929996&view=c&wchp=dGLbVzW-zSkWA&md5=5809648ff08491822375b595ea376e9a&ie=/sdarticle.pdf "The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete"], Theoretical Computer Science 307, 2003</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*David Muradian, [http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6V1G-48GFSHM-6-1&_cdi=5674&_user=56861&_orig=search&_coverDate=10%2F14%2F2003&_sk=996929996&view=c&wchp=dGLbVzW-zSkWA&md5=5809648ff08491822375b595ea376e9a&ie=/sdarticle.pdf "The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete"], Theoretical Computer Science 307, 2003</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
</table>
Baker
https://www.esoterum.org/mw/index.php?title=CSE550_Combinatorial_Algorithms/Intractability&diff=1325&oldid=prev
Baker at 03:57, 7 December 2007
2007-12-07T03:57:47Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 21:57, 6 December 2007</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l43">Line 43:</td>
<td colspan="2" class="diff-lineno">Line 43:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://people.brunel.ac.uk/~mastjjb/jeb/or/netflow.html Minimum Cost Flow (Linear Programming)]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://people.brunel.ac.uk/~mastjjb/jeb/or/netflow.html Minimum Cost Flow (Linear Programming)]</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://www.engr.pitt.edu/hunsaker/2082/hw10_solutions.pdf Caterer Problem] (Network graph)</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://www.engr.pitt.edu/hunsaker/2082/hw10_solutions.pdf Caterer Problem] (Network graph)</div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">*S. Vajda, "An Outline of Linear Programming", Journal of the Royal Statistical Society, 1955</ins></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q3 ===</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q3 ===</div></td></tr>
</table>
Baker
https://www.esoterum.org/mw/index.php?title=CSE550_Combinatorial_Algorithms/Intractability&diff=1324&oldid=prev
Baker at 22:48, 6 December 2007
2007-12-06T22:48:26Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 16:48, 6 December 2007</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l42">Line 42:</td>
<td colspan="2" class="diff-lineno">Line 42:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q2 ===</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q2 ===</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://people.brunel.ac.uk/~mastjjb/jeb/or/netflow.html Minimum Cost Flow (Linear Programming)]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://people.brunel.ac.uk/~mastjjb/jeb/or/netflow.html Minimum Cost Flow (Linear Programming)]</div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">*[http://www.engr.pitt.edu/hunsaker/2082/hw10_solutions.pdf Caterer Problem] (Network graph)</ins></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q3 ===</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q3 ===</div></td></tr>
</table>
Baker
https://www.esoterum.org/mw/index.php?title=CSE550_Combinatorial_Algorithms/Intractability&diff=1323&oldid=prev
Baker at 10:43, 6 December 2007
2007-12-06T10:43:20Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 04:43, 6 December 2007</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l50">Line 50:</td>
<td colspan="2" class="diff-lineno">Line 50:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q4 ===</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q4 ===</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://books.google.com/books?id=ymJTEjPg6CcC&pg=PT125&lpg=PT125&dq=edge+coloring+bipartite+multigraph+lp&source=web&ots=2J_0-ug5n6&sig=kOcj0lJmyQk5DmQty0pbnOVwQXQ ''Handbook of Scheduling: Algorithms, Models, and Performance Analysis''], By Joseph Y-T. Leung (bipartite multi-graph edge coloring)</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://books.google.com/books?id=ymJTEjPg6CcC&pg=PT125&lpg=PT125&dq=edge+coloring+bipartite+multigraph+lp&source=web&ots=2J_0-ug5n6&sig=kOcj0lJmyQk5DmQty0pbnOVwQXQ ''Handbook of Scheduling: Algorithms, Models, and Performance Analysis''], By Joseph Y-T. Leung (bipartite multi-graph edge coloring)</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">*Taehan Lee, Sungsoo Park, [http://www.sciencedirect.com.ezproxy1.lib.asu.edu/science?_ob=MImg&_imagekey=B6VCT-43T1P14-6-37&_cdi=5963&_user=56861&_orig=search&_coverDate=11%2F16%2F2001&_sk=998649998&view=c&wchp=dGLzVzz-zSkWz&md5=9651f4b5c3225410d86e1cdfa7d4cc5c&ie=/sdarticle.pdf "An integer programming approach to the time slot assignment problem in SS/TDMA systems with intersatellite links"], European Journal of Operational Research, November 2001</ins></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q5 ===</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q5 ===</div></td></tr>
</table>
Baker
https://www.esoterum.org/mw/index.php?title=CSE550_Combinatorial_Algorithms/Intractability&diff=1321&oldid=prev
Baker at 09:39, 6 December 2007
2007-12-06T09:39:06Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 03:39, 6 December 2007</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l46">Line 46:</td>
<td colspan="2" class="diff-lineno">Line 46:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://books.google.com/books?id=EILqAmzKgYIC&pg=PA100&lpg=PA100&dq=max+flow+min+cut+duality+complementary+slackness&source=web&ots=XicYGOVV8-&sig=Xa-U-NVuTyUcThBYpM_jb60on_8#PPA101,M1 Max-Cut, Min-Flow and information on complementary slackness]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://books.google.com/books?id=EILqAmzKgYIC&pg=PA100&lpg=PA100&dq=max+flow+min+cut+duality+complementary+slackness&source=web&ots=XicYGOVV8-&sig=Xa-U-NVuTyUcThBYpM_jb60on_8#PPA101,M1 Max-Cut, Min-Flow and information on complementary slackness]</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://www.econ.ucsd.edu/~jsobel/172aw02/notes6.pdf Duality and Complementary Slackness]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://www.econ.ucsd.edu/~jsobel/172aw02/notes6.pdf Duality and Complementary Slackness]</div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">*[http://www.cs.brown.edu/courses/cs157/maxflowmincut.pdf Max Flow - Min Cut via Linear Programming Duality]</ins></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q4 ===</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=== Q4 ===</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l80">Line 80:</td>
<td colspan="2" class="diff-lineno">Line 81:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://www.ampl.com/FAQ/ AMPL FAQ]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://www.ampl.com/FAQ/ AMPL FAQ]</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>=== Min-Cut Max-<del style="font-weight: bold; text-decoration: none;">Floe </del>===</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>=== Min-Cut Max-<ins style="font-weight: bold; text-decoration: none;">Flow </ins>===</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*Dan Bienstock, [http://www.jstor.org/view/0364765x/ap060062/06a00070/0 "Some Generalized Max-Flow Min-Cut Problems in the Plane"] Mathematics of Operations Research, Vol. 16, No. 2. (May, 1991), pp. 310-333.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*Dan Bienstock, [http://www.jstor.org/view/0364765x/ap060062/06a00070/0 "Some Generalized Max-Flow Min-Cut Problems in the Plane"] Mathematics of Operations Research, Vol. 16, No. 2. (May, 1991), pp. 310-333.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://legacy.orie.cornell.edu/~shmoys/or630/notes-06/lec03.pdf Linear Programming and set covering problems] (based on notes from Tardos)</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*[http://legacy.orie.cornell.edu/~shmoys/or630/notes-06/lec03.pdf Linear Programming and set covering problems] (based on notes from Tardos)</div></td></tr>
</table>
Baker
https://www.esoterum.org/mw/index.php?title=CSE550_Combinatorial_Algorithms/Intractability&diff=1319&oldid=prev
Baker at 19:45, 4 December 2007
2007-12-04T19:45:17Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 13:45, 4 December 2007</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l67">Line 67:</td>
<td colspan="2" class="diff-lineno">Line 67:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>:-Bidirected formulation for the Steiner tree problem (Rajagopalan-Vazirani).</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>:-Bidirected formulation for the Steiner tree problem (Rajagopalan-Vazirani).</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>:-Asymmetric TSP (Charikar, Goemans, Karloff).</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>:-Asymmetric TSP (Charikar, Goemans, Karloff).</div></td></tr>
<tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">::Moses Charikar, Michel X. Goemans, Howard Karloff, [http://ieeexplore.ieee.org/iel5/9430/29918/01366229.pdf "On the Integrality Ratio for Asymmetric TSP"], Annual IEEE Symposium on Foundations of Computer Science, 2004</ins></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>:-Matching-based LP relaxation of edge-coloring gap should be an additive 1! There is a paper by Jeff Kahn, but it is somewhat difficult.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>:-Matching-based LP relaxation of edge-coloring gap should be an additive 1! There is a paper by Jeff Kahn, but it is somewhat difficult.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr>
</table>
Baker