Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
MCS 521: Combinatorial Optimization
Lectures: Monday-Wednesday-Friday 10:00 - 10:50 am in BSB 337
CRN number: 42786
FIRST TWO WEEKS online at:
https://uic.zoom.us/j/83147069190?pwd=Q091QjVISm5Nc083M2ZGWm5hTkVBZz09
We will meet in-person as soon as it is allowed by the university.
Instructor: Will Perkins
Email: [email protected]
Office hours: 626 SEO building, TBA
Course webpage: http://willperkins.org/MCS521-2022/
Course description Combinatorial optimization is the study of algorithms for finding the maximum or minimum value of a function over a discrete domain. Real-world examples of combinatorial optimization include airline scheduling, finding the fastest driving directions between two locations, matching hospitals and residents, supply-chain management, and many others. The most interesting discrete optimization problems involve very large domains so that an exhaustive search is impractical; thus we want to use insights from the combinatorial structure of the particular problem to design more efficient algorithms. Course prerequisites: Basic graph theory and linear algebra. Some basic knowledge of algorithms is useful.
Required textbook Combinatorial Optimization, Cook, Cunningham, Pulleyblank, Schrijver.
Supplementary textbook Combinatorial Optimization, Trevisan, http://theory.stanford. edu/~trevisan/books/cs261.pdf
Topics
• What is combinatorial optimization? Some themes of the course
• Minimum spanning trees
• Shortest paths
• Max flow problems
• Minimum cut problems
• Maximum matchings
• Traveling salesman problem
• Vertex cover
• Linear programming
• Approximation algorithms
• Randomized algorithms
• Cut trees
Grading
The course is assessed by a report on a research paper and a take-home final examination.
(1) Homework (30%): there will be 5-6 problem sheets.
(2) Paper report (20%): you will read (and understand!) a recent research paper related to combinatorial optimization, present a summary to the class, and answer questions about the paper from the instructor and your classmates.
(3) Hands-on combinatorial optimization (15%): you will find (or build) a data set related to an optimization problem and solve it using your choice of computer software (Matlab, Mathematica, Excel, R, . . . ). You will then write a 2-page report on the problem, the data set, your method, and your solution.
(4) Take-home final (25%): the take-home final exam will cover all the material from the course. It will be handed out on Monday April 25 and due Friday May 6.
(5) Class participation (10%): you will get full credit for class participation with good attendance and active participation in class.
Course Policies
Each student must turn in their own homework but you are encouraged to discuss the homework with other students and to read each others work. You must indicate clearly on your homework which students you worked with.
Class discussion, working in groups, and communicating with the instructor are all essential elements of the course. I expect all of us to treat each other with respect and courtesy in all of our interactions.
Late homework will not be accepted in general. Exceptions may be requested with good reason and advance notice.
Disability policy Students with disabilities who require accommodations for access and participation in this course must be registered with the Office of Disability Services (ODS). Please contact ODS at 312–413–2183 (voice) or 312–413–0123 (TTY). Academic deadlines Please see https://catalog.uic.edu/ucat/academic-calendar/ Religious holidays Students who wish to observe their religious holidays shall notify the faculty member by the tenth day of the semester of the date when they will be absent unless the religious holiday is observed on or before the tenth day of the semester. In such cases, the student shall notify the faculty member at least five days in advance of the date when he/she will be absent. The faculty member will make every reasonable effort to honor the request. https: //oae.uic.edu/religious-calendar/