Course Identification

Title:

Linear Programming and Combinatorial Optimization

Code:

20234091

Lecturers and Teaching Assistants

Lecturers:

Prof. Uriel Feige

TA's:

Vadim Grinberg

Course Schedule and Location

Year:

2023

Semester:

First Semester

When / Where:

Wednesday, 14:15 - 16:00, Jacob Ziskind Building, Rm 155

First Lecture:

09/11/2022

End date:

10/02/2023

Field of Study, Course Type and Credit Points

Mathematics and Computer Science: Lecture; Elective; Regular; 2.00 points
Life Sciences: Lecture; Elective; Regular; 2.00 points

Comments

N/A

Prerequisites

Basic undergraduate knowledge of algorithms, computational complexity, linear algebra and probability theory

Restrictions

Participants:

50

Language of Instruction

English

Attendance and participation

Expected and Recommended

Grade Type

Numerical (out of 100)

Grade Breakdown (in %)

Assignments:

50%

Final:

50%

Evaluation Type

Examination

Scheduled date 1

Date / due date

02/03/2023

Location

Ziskind, Rm 1

Time

1400-1700

Remarks

N/A

Scheduled date 2

Date / due date

29/03/2023

Location

Ziskind, Rm 1

Time

1400-1700

Remarks

N/A

Estimated Weekly Independent Workload (in hours)

4

Syllabus

Theory of linear programming (e.g., some polyhedral theory, basic feasible solutions, duality), algorithms for linear programming (e.g. (simplex, ellipsoid), rounding of linear programs and applications, extensions to convex optimization and semidefinite programming, direct combinatorial optimization algorithms without linear programming.

Learning Outcomes

Upon successful completion of this course students should be able to have a good understanding of the theory of linear programming, and of when and how to use linear programming and related techniques

Reading List

There will be lecture notes. There are many books on this subject, including J. Matousek and B. Gartner, Understanding and Using Linear Programming, Springer, 2006, which is freely available on the web

Website

N/A