|
|
|
||
|
An introduction to mainly discrete optimisation is given. The lecture is centered around the theory of
linear programming.
Last update: LOEBL/MFF.CUNI.CZ (09.11.2010)
|
|
||
|
Cílem přednášky je, aby se studenti seznámili se základními metodami diskrétní optimalizace a naučili se v optimalizaci orientovat tak, aby byli schopni sami rozpoznat nové trendy. Last update: LOEBL/MFF.CUNI.CZ (09.11.2010)
|
|
||
|
Hans Raj Tiwary:
Students need to pass 50% of the homeworks and 50% of the quizzes to pass the tutorial. Due to the requirements, additional attempts to pass the tutorial are excluded. Passing the tutorials is required before taking the exam. Last update: Tiwary Hans Raj, doc., M.Sc., Ph.D. (16.02.2022)
|
|
||
|
A. Schrijver, Theory of linear and integer programming, John Wiley, 1986
W.J.Cook, W.H. Cunningham W.R.Pulleyblank, A. Schrijver, Combinatorial Optimization, John Wiley, 1997
J. Matoušek, B. Gärtner, Understanding and using linear programming, Springer, 2006.
J. Matoušek Introduction to Discrete Geometry. ITI Series 2003-150, MFF UK, 2003 Last update: Hladík Milan, prof. Mgr., Ph.D. (22.11.2012)
|
|
||
|
Hans Raj Tiwary:
For the main exam, the requirements correspond to the syllabus as covered by the lectures. Last update: Kynčl Jan, doc. Mgr., Ph.D. (23.05.2019)
|
|
||
|
Linear and integer programming problem, examples Combinatorial geometry, polytopes and their minimal description, Minkowski-Weyl's theorem Duality of linear programming, Farkas' lemma Simplex method, pivoting rules Polynomial algorithms for linear programming (overview) Unimodularity, König's lemma, network flows Weighted matchings in general graphs, Edmonds' algorithm Matching polytope Integer programming Approximation algorithms Matroids Last update: LOEBL/MFF.CUNI.CZ (09.11.2010)
|