CS675: Convex and Combinatorial Optimization (Fall 2026)

Basic information

Announcements

Schedule by Week

Course Description

Over the past half century or so, computer science and mathematical optimization have witnessed the development and maturity of two different paradigms for algorithm design. The first approach, most familiar to computer scientists, is combinatorial in nature. The tools of discrete mathematics are used to understand the structure of the problem, and algorithms effectively exploit this structure to search over a large yet finite set of possible solutions. The second approach, standard in much of the operations research and mathematical optimization communities, primarily employs the tools of continuous mathematics, high dimensional geometry, and convex analysis. Problems are posed as a search over a set of points in high-dimensional Euclidean space, which can be performed efficiently when the search space and objective function are ``convex.'' Whereas many optimization problems are best modeled either as a discrete or convex optimization problem, researchers have increasingly discovered that many problems are best tackled by a combination of combinatorial and continuous techniques. The ability to seamlessly transition between the two views has become an important skill to every researcher working in algorithm design and analysis. This course intends to instill this skill by presenting a unified treatment of both approaches, focusing on algorithm design tasks that employ techniques from both. The intended audience for this course are PhD students, Masters students, and advanced undergraduates interested in research questions in algorithm design, mathematical optimization, or related disciplines.

Prerequisites

Requirements and Grading

There will be two in-class quizzes worth 20%, and a final exam worth 30%. Everything is closed book and notes. The quizzes and exam will be designed to be close to the homework assignments.

Homework assignments will count for 7% of the grade. Peer grading will count for 3%. There will be bi-weekly homework assignments, which will be proof-based, and are intended to be challenging. Collaboration and discussion among students is allowed, even encouraged, though students must write up their solutions independently.

The remaining 20% of the grade will be allocated to a final project. Students will have to choose a related research topic, read several papers in that area, and either write survey of the area and/or articulate and investigate some novel research direction.

Late Homework Policy: Students will be allowed 6 late days for homework, to be used in integer amounts and distributed as the student sees fit. No additional late days are allowed.

Policy on AI use: You are prohibited from using AI for doing your homework assignments or peer grading. Homework counts little towards your grade, so it should be viewed as practice for the quizzes and exams. The quizzes and exams will be designed to be close to some homework problems, which hopefully will incentivize you to do the homework yourselves.

References

We will refer to two main texts: Convex Optimization by Boyd and Vandenberghe, available free online, and Combinatorial Optimization, Fifth edition by Korte and Vygen, available online through USC libraries. Additional references include Algorithms for Convex Optimization by Vishnoi, Combinatorial Optimization by Schrijver, Linear and Nonlinear Programming by Luenberger and Ye, Fourth edition, available online through usc libraries, as well as research papers and lecture notes from related courses elsewhere which will be linked on the course website.