VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.
Special Topics in Linear Programming
Last Updated: 2026-02-05 15:09:57
Abstract
Goal: Introduce the students to recent and powerful techniques to solve certain classes of convex optimization problems with special interest in efficient algorithms for large scale problem instances. This class is intended for diploma students interested in a deeper understanding of optimization algorithms and for graduate students interested in finding out new research topics.
Content
Nowadays the use of linear programming is almost pervasive across engineering disciplines. Part of the reason of its popularity has been the practical effectiveness of the half-a century old simplex method and the more recent interior point methods. However for many practical large scale instances these solution methods are not effective. In this class we will consider alternative approaches more adequate for solving large scale linear programming problems that are provably efficient. The success of these techniques relies on exploiting the structure of the linear program. For instance, sometimes it can be shown that the linear program can be transformed into a simple network flow problem, thus obtaining an efficient algorithm for it. In most cases, though, we have to settle with an approximate solution. We will consider two methods that consider Lagrangian formulations of the linear program. The first uses subgradient optimization and typically is very simple and relies on the underlying discrete structure of the problem. The second is provably faster and uses gradient optimization following recent breakthrough algorithms of Nesterov. No prior exposure to the subject is assumed and the methods will be described using particular examples that will cover some of the newest developments in the area.
Resources
Literature
* B. Awerbuch and T. Leighton. Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 487-495, 1994. * D. Bienstock. Potential Function Methods for Approximately Solving Linear Programming Problems: Theory and Practice. CORE Lecture Series, ISSN-0771 3894. U. Catholique de Louvain, Belgium, 2001. * D. Bienstock and G. Iyengar, Concurrent flows in O(1/epsilon) iterations. CORC Report 2003-03. * F. Chudak and V. Eleuterio. Improved approximation schemes for linear programming relaxations of combinatorial optimization problems. To appear in IPCO'05. * F. Chudak ,D. Hochbaum, M.X. Goemans and D.P. Williamson. A primal-dual in-terpretation of 2-approximation algorithms for the feedback vertex set problem in undirected graphs. In Operations Research Letters 22, 111-118, 1998. * N. Garg and J. Könemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In Proceedings of the 39th annual IEEE Symposium on Foundations of Computer Science, pages 300-309, 1998. * N. Garg and R. Khandekar. Fast approximation algorithms for fractional Steiner forest and related problems. In Proceedings of the 43rd annual IEEE Symposium on Foundations of Computer Science, 2002. * M.X. Goemans and D.P. Williamson. The primal-dual method for approximation algorithms and its application to network design problems. In Approximation algorithms for NP-hard problems, D. Hochbaum editor, Chapter 4, pages 144-189. PWS Publishing Company, 1997. * M. Luby and N. Nisan. A parallel approximation algorithm for positive linear programming. In Proceedings of the 25th Annual ACM Symposium on Theory of Com-puting, pages 448-457, 1993. * Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Book Series: APPLIED OPTIMIZATION, Vol. 87. Kluwer Academic Publishers. * Y. Nesterov, Smooth optimization of non-smooth functions. To appear in Mathematical Programming. * N. Young. Randomized rounding without solving the linear program. In Proceed-ings of the 6th ACM-SIAM Symposium on Discrete Algorithms, pages 170-178, 1995.
General Information
- Language
- English
- Frequency
- Yearly recurring
Examination
- Type
- session examination
- Mode
- oral 20 minutes
Course Components
| Type | Title | Time & Place | Hours |
|---|---|---|---|
| lecture | Special Topics in Linear Programming |
|
2 h weekly |
| exercise | Special Topics in Linear Programming |
|
2 h weekly |