Spring 2021

Instructor: Dr. Swati Gupta,
Assistant Professor and Fouts Family Early Career Professor,
School of Industrial and Systems Engineering,
Affiliations: Center for Machine Learning, ACO Program, Algorithms and Randomness Center, Physical Internet Lab, Parker H. Petit Institute, Institute for Data Engineering and Science

Office: Groseclose Building 437
Contact: swatig@gatech.edu
Lecture: M, W 3:30-4:45 PM (synchronous)

Office Hours: By appointment.

Teaching Assistants: TBD

Remote Synchronous Teaching
All classes will be recorded and posted online on canvas. We plan to have synchronous lectures and students are required to attend the online lectures. You can review the material using recordings, notes and reference books. We will also hold a survey in the first week of classes to determine the learning needs of all students: workload, time zone, being quarantined, and other situations that impact their learning. Adjustments may be made to the syllabus based on the findings of this survey.

Description: We will study classical as well as recent results in combinatorial optimization including matchings, network flows, matroids and submodular function optimization. In addition to algorithmic questions, emphasis will be given to polyhedral characterization and combinatorial min-max relations.

Textbook: Combinatorial Optimization: Polyhedra and Efficiency by Alexander Schrijver, Springer 2003.

Recommended Reading:

Grading: Homeworks (40%), Midterm (25%), Final (35%). 

This is a TENTATIVE SYLLABUS, subject to change, as the pandemic situation develops during the semester and we know more about institute policies.

Tentative list of topics: Non-bipartite Matchings, Edmonds’ Blossom Algorithm, Edmonds-Gallai Decomposition and alternate proof using the Tutte-Berge theorem, Iterative rounding, Min-cost flows and circulations, Nowhere Zero Flows, Total Unimodularity, Total Dual Integrality and Matching Polytope, T-joins, Packing T-cuts, T-join Polytope, Gomory-Hu trees, Spanning tree polytope, Matroids, Representability of Matroids, Matroid Polytope and its TDI, Matroid Intersection, Matroid Union, Submodular Functions, Polymatroids Greedy Algorithm, Submodular function minimization, Lov\'{a}sz Extension, Polymatroid Intersection, Graph Orientation, General Submodularity, Submodular Flows, Perfect Graphs

Course Policies: 

  • The assignments have to be submitted online, with typed up solutions in LaTeX. 
  • Each assignment must include a statement signed by the student: “I commit to uphold the ideals of honor and integrity by refusing to betray the trust bestowed upon me as a member of the Georgia Tech community.”
    20% points will be taken off if this statement is missing. 
  • You are encouraged to discuss homework/assignments problems with your fellow students. But your final answers should be based on your own understanding unless it is a group assignment, which will be announced on Canvas. Copying others’ work is NOT acceptable and violates the honor code. Write the names of students you have discussed the assignments with. In case answers are found copied from another student, both the students (the one who allowed copying, and the one who copied) will both get a 0 and might also result in obtaining a D or F grade overall.  
  • Regrade requests will be accepted via email to the instructor within 5 days of the graded assignment/exam being returned. Requests must include (1) a PDF of the original submission and (2) a LaTeX-produced PDF detailing which problems were graded incorrectly and an argument that the submitted solution is indeed correct. Regrades may only be requested if it is believed that a correct answer was marked as incorrect, not because insufficient partial credit was given to an incorrect or partially correct solution. If you request a regrade, you accept that the entire assignment/exam will be regraded, not just the problem(s) believed to be graded incorrectly.
  • Late assignments: We will allow a grace period of 1 hour for every assignment. For every hour that the assignment is submitted late, the grade will be reduced by 10% (linearly interpolated), without exceptions. The only official extensions for late assignments will be granted with a letter from the Dean of Student’s Office to be received before the assignment is due.   
  • Exams: Exams will be conducted virtually. Details of the exams will be announced later, and will depend on the virtual test-taking software available. Missing an exam will be accommodated only in case of Institute approved absences with a letter from the Dean of Students. Alternative arrangements will be made on a case by case basis, but the instructor must be informed at least two weeks prior to the exam.
  • Academic Honor Code
    It is your responsibility to get familiar with the Georgia Tech Honor Code and you are bound by its requirements. For any questions any Academic Honor Code issues, please consult me, my teaching assistants, or www.honor.gatech.edu. (Links to an external site.)

Mutual Respect and Expectations
ISyE 7686 is an advanced graduate level course. You are expected to have an attitude to learn, instead of just getting a grade. To produce a positive teaching and learning environment, instructors and students must partner with one another in and out of the classroom. Mutual respect is at the heart of such a partnership and is characterized by respectful language and imagery, punctuality and care for others’ time, clear and thorough communication, access to resources, and an openness to dialogue and debate. As a Georgia Tech faculty member, I am committed to such respect and I invite you to join me in working towards the best possible learning environment, so that all can meet their highest ambitions. Further, we will not tolerate discrimination towards any group of students. For more information about faculty and student expectations, as recognized in Georgia Tech policy, please see the following web page: http://www.catalog.gatech.edu/rules/22.php (Links to an external site.)

Office of Disability Services
If you are a student with learning needs that require special accommodation, please contact the Office of Disability Services (http://disabilityservices.gatech.edu/) at (404)894-2563 as soon as possible to make an appointment to discuss your special needs and to obtain an accommodations letter. Please also e-mail me as soon as possible in order to set up a time to discuss your learning needs.