teaching:para1920
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze | ||
teaching:para1920 [2020/02/18 15:29] – Andreas E. Feldmann | teaching:para1920 [2022/05/09 20:33] (aktuální) – [Parameterized Approximations for Steiner Trees] Martin Koutecky | ||
---|---|---|---|
Řádek 6: | Řádek 6: | ||
- Parameterized algorithms for integer programming and their applications in scheduling. // | - Parameterized algorithms for integer programming and their applications in scheduling. // | ||
- | - Hard graph problems (e.g., longest path, longest cycle) via algebraic methods; this will be an elementary exposition, so everyone is wellcome. // | + | - Hard graph problems (e.g., longest path, longest cycle) via algebraic methods; this will be an elementary exposition, so everyone is welcome. // |
- Parameterized approximation (i.e., how to deal with problems which are hard to approximate and do not admit fixed-parameter algorithms), | - Parameterized approximation (i.e., how to deal with problems which are hard to approximate and do not admit fixed-parameter algorithms), | ||
+ | |||
+ | ===== Parameterized algorithms for IP and applications ===== | ||
+ | |||
+ | **First lecture:** we talked about Integer Linear Programming with few constraints and without upper bounds, that is, the problem is $\min \mathbf{c} \mathbf{x}: \, A \mathbf{x} = \mathbf{b}, \, \mathbf{x} \geq \mathbf{0}, \, \mathbf{x} \in \mathbb{Z}^n$. | ||
+ | First we mentioned an [[https:// | ||
+ | |||
+ | **Second & Third lecture:** We talked about Huge $n$-fold Integer Programming, | ||
+ | |||
+ | * Definition of the Huge $n$-fold IP problem | ||
+ | * The Configuration LP of the Huge $n$-fold IP (equations (3)-(4)) | ||
+ | * How the Configuration LP is solved in FPT time by solving its Dual by the Ellipsoid method (separation oracle) (Lemma 12) | ||
+ | * The definition of a configurable cycle (pg. 14) and some of its properties: Lemmas 13-15 | ||
+ | * The proximity theorem (Thm 21) and how it is used to obtain an FPT algorithm for Huge $n$-fold IP (Proof of Thm 5) | ||
+ | |||
+ | It would be also great if you had an idea of how the proximity theorem is used to obtain [[https:// | ||
+ | |||
+ | **Fourth lecture:** We talked about Mixed Integer Linear Programs, [[https:// | ||
+ | ===== Parameterized Approximations for Steiner Trees ===== | ||
+ | |||
+ | Covered topics and references: | ||
+ | |||
+ | - Lossy kernels: sections 1 and 2 of [[https:// | ||
+ | - PSAKS for Steiner Tree parameterized by nr of terminals: section 6.2 of [[https:// | ||
+ | - Proof of Borchers and Du Theorem: sections 1 and 3 of [[https:// | ||
+ | - Directed Steiner Tree parameterized by nr of Steiner vertices: sections 1, 4, and 5 of [[https:// | ||
+ | - Undirected Steiner Tree (and Steiner Forest) parameterized by nr of Steiner vertices (and nr of connected components): | ||
+ |
teaching/para1920.1582036170.txt.gz · Poslední úprava: 2020/02/18 15:29 autor: Andreas E. Feldmann