Combinatorial Optimization, MATH 4320/5320.

Winter 2004

Dalhousie University,

Department of Mathematics and Statistics

Instructor: Jeannette Janssen

Syllabus (PDF)

To read for next class:

Appendix A, course text

Next assignment due: Second part of Assignment 2 due on Thursday, Jan. 29. Assignment 3 due on Tuesday, Feb. 3.

Assignment 3 has handwritten parts. If you lost your copy, you can pick one up at my office.
Assignment 2 (New version!)
Assignment 1

Projects:
Projects should be done in groups of up to three people. There will be a short presentation right after the break, and a long presentation in the exam week. Also, a written report will be required.

Topics:

Traveling Salesman Problem --- polyhedral methods
RNA and DNA sequencing
The polytope of doubly independent sets of matchings (research topic)
The polytope of matchings of bounded size (research topic)
Randomized rounding

You may suggest a different topic, and I will decide whether it is appropriate. All groups should meet with me before February 7 to discuss their project.

Links

Let me know if you find any other useful links, and I will add them to this list.

Overview papers by Aardal and van Hoesel (gzipped PS files): Theory and Applications and
Homepage of Lex Schrijver. Here you can find A course in Combinatorial Optimization, which is recommended background reading.
Short review of graph theory definitions
Puzzles (Integer Programming in recreational mathematics)