Difference between revisions of "CSE550 Combinatorial Algorithms/Intractability"

From esoterum.org
Jump to: navigation, search
 
(65 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
*[http://www.sce.carleton.ca/faculty/chinneck/po/Chapter2.pdf Linear Programming Introduction]
+
== Resources ==
 +
*> [http://www.sce.carleton.ca/faculty/chinneck/po/Chapter2.pdf Linear Programming Introduction]
 +
:-Unimodularity ensures that the solution to an LP will always be integer if all of the costs and constraints are also integer
 
*[http://optlab-server.sce.carleton.ca/POAnimations2007/SimplexTableau.html Linear Programming animation] (simplex method)
 
*[http://optlab-server.sce.carleton.ca/POAnimations2007/SimplexTableau.html Linear Programming animation] (simplex method)
 
*[http://www.sce.carleton.ca/faculty/chinneck/StudentOR.html List of LP solvers] (including NEOS)
 
*[http://www.sce.carleton.ca/faculty/chinneck/StudentOR.html List of LP solvers] (including NEOS)
 
*[http://mat.gsia.cmu.edu/orclass/integer/integer.html Integer Linear Programming Tutorial]
 
*[http://mat.gsia.cmu.edu/orclass/integer/integer.html Integer Linear Programming Tutorial]
 
*[http://wpweb2.tepper.cmu.edu/fmargot/introILP.html Interger Linear Programming Tutorial] (CMU)
 
*[http://wpweb2.tepper.cmu.edu/fmargot/introILP.html Interger Linear Programming Tutorial] (CMU)
 +
*[http://elib.zib.de/pub/Packages/mathprog/ Opensource Algorithm Code], Zuse Institute
 +
*[http://ad.informatik.uni-freiburg.de/lehre/ss01/paa/vorlesung-uebungen/download/index.htm Lectures from the University of Freiburg]
 +
*> [http://www.ensta.fr/~diam/ro/online/viggo_wwwcompendium/node276.html List of NP-Hard problems]
 +
*> [http://www2.toki.or.id/book/AlgDesignManual/INDEX.HTM ''The Algorithm Design Manual''], Steven S. Skiena, Department of Computer Science State University of New York (Online)
 +
*[http://www.cs.princeton.edu/introcs/77intractability/ Good article on intractability from Princeton]
 +
*David S. Johnson, [http://www.research.att.com/~dsj/columns/col10.pdf "The NP-Completeness Column: An Ongoing Guide"], J. Algorithms 5, 147-160 (1984)
 +
*> 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
 +
*> [ftp://ftp.nada.kth.se/Theory/Viggo-Kann/compendium.ps A Compendium of NP-Complete Problems]
 +
 +
== HW 6 ==
 +
:1. [http://www.soe.ucsc.edu/classes/cmps132/Winter05/hw/hw8sols.pdf 2-SAT is in NP]
 +
:2. A sub-optimal solution to TSP is a Hamiltonian Cycle.
 +
:3. [http://www.cit.gu.edu.au/teaching/3130CIT/lectures/complexity.pdf 3SAT reduction to NAESAT]
 +
:4. Finding disjoint paths with different path-costs: Complexity and algorithms
 +
:*Randeep Bhatia · Murali Kodialam · T. V. Lakshman, [http://www.springerlink.com.ezproxy1.lib.asu.edu/content/x24w933w7vgu262x/fulltext.pdf "Finding disjoint paths with related path costs"], Springer Science+Business Media, LLC 2006
 +
 +
== HW 7 ==
 +
:1.
 +
:*[http://books.google.com/books?id=PP7uQQI-rDgC&pg=RA3-PA366&lpg=RA3-PA366&dq=%22metric+traveling+salesman+problem%22&source=web&ots=6lfNyeObBu&sig=H_mH4sMpl8s-Dv3DrCvYX5AtTko#PRA3-PA367,M1 Optimization Theory By Hubertus Th. Jongen, Klaus Meer, Eberhard Triesch], partial search result on Google book search
 +
:*[http://www.cs.toronto.edu/~pmccabe/csc363-2005S/notes22.pdf Solution to part (a),(b)]
 +
:*[http://www.diku.dk/undervisning/2005v/404/tspappr.pdf Solution to part (a),(b)]
 +
:*[http://209.85.173.104/search?q=cache:qgZ0E6cTD20J:www.cs.uu.nl/docs/vakken/amc/lecture03-2.ps+%22asymmetric+metric+TSP%22&hl=en&ct=clnk&cd=1&gl=us Additional infor (a),(b), possible references for (c)]
 +
::-Theorem 1.2 (Kumar and Li, 2002) Any asymmetric TSP on n locations can be reducedto a symmetric TSP on 2n locations
 +
:*[http://www.sciencedirect.com.ezproxy1.lib.asu.edu/science?_ob=ArticleListURL&_method=list&_ArticleListID=654442605&_sort=d&view=c&_acct=C000059542&_version=1&_urlVersion=0&_userid=56861&md5=7c0e2798e0ed6ae5bd0b5865eea21691 Science Direct "Problems"]
 +
 +
== Midterm ==
 +
=== Q1 ===
 +
*Bin Zhang, Julie Ward, Qi Feng, [http://www.hpl.hp.com/techreports/2005/HPL-2005-121.pdf "Simultaneous Parametric Maximum Flow Algorithm with Vertex Balancing"], HP Laboratories Palo Alto, June 28, 2005
 +
*J. M. W. Rhys, [http://www.jstor.org.ezproxy1.lib.asu.edu/cgi-bin/jstor/printpage/00251909/di012665/01p0039r/0.pdf?backcontext=results&dowhat=Acrobat&config=&userID=81dbf4d5@asu.edu/01c0545010c0e9115c6b1c33c&0.pdf "A Selection Problem of Shared Fixed Costs and Network Flows"], Management Science, Vol. 17, No. 3, Theory Series (Nov., 1970), pp. 200-207
 +
 +
=== Q4 ===
 +
*[http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/new04.pdf LP Primal Dual Tutorial] ?
 +
 +
== Final ==
 +
=== Q2 ===
 +
*[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 ===
 +
*[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.cs.brown.edu/courses/cs157/maxflowmincut.pdf Max Flow - Min Cut via Linear Programming Duality]
 +
 +
=== 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)
 +
*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, "Edge­Coloring Bipartite Multigraphs in 0(E log D) Time", April 18, 2000
 +
 +
=== Q5 ===
 +
*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
 +
*David Muradian, [http://www.sciencedirect.com.ezproxy1.lib.asu.edu/science?_ob=MImg&_imagekey=B6V1G-48GFSHM-6-1&_cdi=5674&_user=56861&_orig=search&_coverDate=10%2F14%2F2003&_sk=996929996&view=c&wchp=dGLzVzz-zSkzk&md5=5809648ff08491822375b595ea376e9a&ie=/sdarticle.pdf "The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete"], Theoretical Computer Science 307, 2003
 +
 +
== Project ==
 +
2. Linear program formulation and solving. You can examine one or more linear programming
 +
formulations for a speci�c problem. This should be done by using a free
 +
solver, such as GLPK and a modeling language such as AMPL or the subset of AMPL
 +
that comes with GLPK. (If you have access to CPLEX and/or real AMPL, that is
 +
also perfectly fine with me.) Your goal in this might be to examine and compare the
 +
solution times for several formulations of a problem (as in the mincut example), or to
 +
study the tightness of a relaxation (as in the case of Steiner trees and edge coloring).
 +
Some suggestions for this type of project:
 +
:-Comparing minimum cut formulations (standard cut covering, polynomial-size directed flow formulation, compact formulation by Carr et al.).
 +
:-Bidirected formulation for the Steiner tree problem (Rajagopalan-Vazirani).
 +
:-Asymmetric TSP (Charikar, Goemans, Karloff).
 +
::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
 +
:-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.
 +
 +
=== GLPsol and LP ===
 +
*[http://www-128.ibm.com/developerworks/linux/library/l-glpk1/ GNU Linear Programming Kit guide from IBM]
 +
*[http://www.engr.pitt.edu/hunsaker/1081/glpsol_tutorial.pdf GLPsol Tutorial]
 +
*[http://www.sce.carleton.ca/faculty/chinneck/po.html Practical Optimization: A Gentle Introduction]
 +
:-[http://www.sce.carleton.ca/faculty/chinneck/po/Chapter7.pdf Chapter 7. LP in Practice]
 +
:-> [http://www.sce.carleton.ca/faculty/chinneck/po/Chapter10.pdf Chapter 10. Network Flow Programming]
 +
*Robert Fourer, [http://www.ampl.com/REFS/amplmod.pdf AMPL: "A Mathematical Programming Language"]
 +
*[http://center.uvt.nl/staff/haemers/reader05ico.pdf LP formulations] (covering, packing, partition) (non-linear information)
 +
*[http://www.ampl.com/FAQ/ AMPL FAQ]
 +
 +
=== Min-Cut Max-Flow ===
 +
*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.
 +
*[http://legacy.orie.cornell.edu/~shmoys/or630/notes-06/lec03.pdf Linear Programming and set covering problems] (based on notes from Tardos)
 +
 +
=== TSP ===
 +
*[http://www.unc.edu/~pataki/papers/teachtsp.pdf Teaching Integer Programming Using the TSP]
 +
*A.J. Orman, H.P. Williams, [http://www.lse.ac.uk/collections/operationalResearch/pdf/WP67%20A%20Survey%20of%20Different%20Formulations%20of%20the%20TSP%20July%2020051.pdf "A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem"], July 2005

Latest revision as of 23:37, 7 December 2007

Resources

-Unimodularity ensures that the solution to an LP will always be integer if all of the costs and constraints are also integer

HW 6

1. 2-SAT is in NP
2. A sub-optimal solution to TSP is a Hamiltonian Cycle.
3. 3SAT reduction to NAESAT
4. Finding disjoint paths with different path-costs: Complexity and algorithms

HW 7

1.
-Theorem 1.2 (Kumar and Li, 2002) Any asymmetric TSP on n locations can be reducedto a symmetric TSP on 2n locations

Midterm

Q1

Q4

Final

Q2

Q3

Q4

Q5

Project

2. Linear program formulation and solving. You can examine one or more linear programming formulations for a speci�c problem. This should be done by using a free solver, such as GLPK and a modeling language such as AMPL or the subset of AMPL that comes with GLPK. (If you have access to CPLEX and/or real AMPL, that is also perfectly fine with me.) Your goal in this might be to examine and compare the solution times for several formulations of a problem (as in the mincut example), or to study the tightness of a relaxation (as in the case of Steiner trees and edge coloring). Some suggestions for this type of project:

-Comparing minimum cut formulations (standard cut covering, polynomial-size directed flow formulation, compact formulation by Carr et al.).
-Bidirected formulation for the Steiner tree problem (Rajagopalan-Vazirani).
-Asymmetric TSP (Charikar, Goemans, Karloff).
Moses Charikar, Michel X. Goemans, Howard Karloff, "On the Integrality Ratio for Asymmetric TSP", Annual IEEE Symposium on Foundations of Computer Science, 2004
-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.

GLPsol and LP

-Chapter 7. LP in Practice
-> Chapter 10. Network Flow Programming

Min-Cut Max-Flow

TSP

Retrieved from "https://www.esoterum.org/mw/index.php?title=CSE550_Combinatorial_Algorithms/Intractability&oldid=1332"