|
|
| | *> Alexander Schrijver, [http://homepages.cwi.nl/~lex/files/histco.pdf "On the history of combinatorial optimization (till 1960)"] | | *> Alexander Schrijver, [http://homepages.cwi.nl/~lex/files/histco.pdf "On the history of combinatorial optimization (till 1960)"] |
| | *[http://ioe.engin.umich.edu/people/fac/books/murty/network_programming/ Network Programming (Internet Edition)], Katta G. Murty | | *[http://ioe.engin.umich.edu/people/fac/books/murty/network_programming/ Network Programming (Internet Edition)], Katta G. Murty |
| | + | *> [ftp://ftp.nada.kth.se/Theory/Viggo-Kann/compendium.ps A Compendium of NP-Complete Problems] |
| | | | |
| | == HW 6 == | | == HW 6 == |
|
|
| | === Q2 === | | === Q2 === |
| | *[http://people.brunel.ac.uk/~mastjjb/jeb/or/netflow.html Minimum Cost Flow (Linear Programming)] | | *[http://people.brunel.ac.uk/~mastjjb/jeb/or/netflow.html Minimum Cost Flow (Linear Programming)] |
| | + | *[http://www.engr.pitt.edu/hunsaker/2082/hw10_solutions.pdf Caterer Problem] (Network graph) |
| | + | *S. Vajda, "An Outline of Linear Programming", Journal of the Royal Statistical Society, 1955 |
| | | | |
| | === Q3 === | | === Q3 === |
| | *[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] | | *[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] |
| | *[http://www.econ.ucsd.edu/~jsobel/172aw02/notes6.pdf Duality and Complementary Slackness] | | *[http://www.econ.ucsd.edu/~jsobel/172aw02/notes6.pdf Duality and Complementary Slackness] |
| | + | *[http://www.cs.brown.edu/courses/cs157/maxflowmincut.pdf Max Flow - Min Cut via Linear Programming Duality] |
| | | | |
| | === Q4 === | | === Q4 === |
| | *[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) | | *[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) |
| − | | + | *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 |
| | + | *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 |
| | + | *Richard Cole, Kirstin Ost, Stefan Schirra, "EdgeColoring Bipartite Multigraphs in 0(E log D) Time", April 18, 2000 |
| | | | |
| | === Q5 === | | === Q5 === |
Exception encountered, of type "Error"