MA/STA 515 — LINEAR AND COMBINATORIAL OPTIMIZATIONMWF 11:00–11:50 — CB345COURSE WEBPAGE: www.ms.uky.edu/~lee/ma515fa05/ma515fa05.htmlINSTRUCTOR: Carl Lee, 967 POT, 257-1405, [email protected], www.ms.uky.edu/~leeOFFICE HOURS: MWF 10:00–10:50 and by appointment, since I realize that some ofyou will be unable to come at these times. Also, I will need to schedule some additionalformal times for the class to meet, since there are some class days when I will be out of town.TEXT: Jon Lee, A First Course in Combinatorial Optimization, Cambridge, 2004. I willalso prepare some course notes.TOPICS:1. Chapter 0: Polytopes and Linear Programming2. Chapter 1: Matroids and the Greedy Algorithm3. Chapter 2: Minimum-Weight Dipaths4. Chapter 3: Matroid Intersection5. Chapter 4: Matching6. Chapter 5: Flows and Cuts7. Various miscellaneous topics as time permitsGRADING:Homework: 50%Exams: 30%Final: 20%HOMEWORK: Usually collected weekly, but some problems may be collected more fre-quently. From time to time I will give additional homework assignments for the graduatestudents enrolled in the course that will not be required of the undergraduate students.Problems are assigned to be solved. Searching the textbooks or the library for solutions isnot permitted. On regular assignments you may discuss the problems w ith other currentclass members and w ith me. However, when it comes time for you to write up the solutions,I expect you to do this on your own. If you receive assistance from someone else, include awritten acknowledgment. Such an acknowledgment is a professional courtesy and will notaffect your grade.EXAMS: There will be two or three exams (tentative dates: September 16, October 10,and November 18) and a final exam (December 14).IMPORTANT DATES:Wednesday, August 24, First day of classesTuesday, August 30, Last day to add a classMonday, September 5, Labor Day holiday—no classWednesday, September 14, Last day to drop a class without a gradeFriday, October 7, October break—no classSaturday–Sunday, October 8–9, Tentative math graduate “cease-fire” weekendFriday, October 21, Last day to withdraw from a classThursday–Friday, November 24–25, Thanksgiving holiday—no classFriday, December 9, Last day of classesWednesday, December 14, 10:30 a.m., Final exam.CHEATING AND PLAGIARISM: The minimum University penalty for cheatingand/or plagiarism is a grade of E for the entire course. It’s not worth it and it is dam-aging to your self-integrity, so don’t do