Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
teaching:para1920 [2020/05/15 09:46] – Andreas E. Feldmann | teaching:para1920 [2022/05/09 20:33] (aktuální) – [Parameterized Approximations for Steiner Trees] Martin Koutecky |
---|
First we mentioned an [[https://lara.epfl.ch/w/_media/papadimitriou81complexityintegerprogramming.pdf|old algorithm of Papadimitriou]] with a dependence of roughly $(m \Delta)^{O(m^3)}$, where $m$ is the number of rows and $\Delta$ is the largest coefficient of $A$ in absolute value. Then, we studied a [[https://dl.acm.org/doi/10.1145/3340322|new algorithm of Eisenbrand and Weismantel]] ([[https://arxiv.org/abs/1707.00481|arxiv]]) which improves the runtime to roughly $(m \Delta)^{O(m)}$; also see an [[https://drops.dagstuhl.de/opus/volltexte/2018/10136/pdf/LIPIcs-ITCS-2019-43.pdf|algorithm of Jansen and Rohwedder]] which improves the constants in the exponent. Finally, we talked about using this algorithm to get an algorithm for the scheduling problem $P||C_{\max}$ which runs in time roughly $p_{\max}^{O(p_{\max})}$ instead of the $p_{\max}^{O(p_{\max}^2)}$ time implied by [[https://link.springer.com/article/10.1007%2Fs10951-017-0550-0|Knop and Koutecký]] ([[https://arxiv.org/abs/1603.02611|arxiv]]). | First we mentioned an [[https://lara.epfl.ch/w/_media/papadimitriou81complexityintegerprogramming.pdf|old algorithm of Papadimitriou]] with a dependence of roughly $(m \Delta)^{O(m^3)}$, where $m$ is the number of rows and $\Delta$ is the largest coefficient of $A$ in absolute value. Then, we studied a [[https://dl.acm.org/doi/10.1145/3340322|new algorithm of Eisenbrand and Weismantel]] ([[https://arxiv.org/abs/1707.00481|arxiv]]) which improves the runtime to roughly $(m \Delta)^{O(m)}$; also see an [[https://drops.dagstuhl.de/opus/volltexte/2018/10136/pdf/LIPIcs-ITCS-2019-43.pdf|algorithm of Jansen and Rohwedder]] which improves the constants in the exponent. Finally, we talked about using this algorithm to get an algorithm for the scheduling problem $P||C_{\max}$ which runs in time roughly $p_{\max}^{O(p_{\max})}$ instead of the $p_{\max}^{O(p_{\max}^2)}$ time implied by [[https://link.springer.com/article/10.1007%2Fs10951-017-0550-0|Knop and Koutecký]] ([[https://arxiv.org/abs/1603.02611|arxiv]]). |
| |
| **Second & Third lecture:** We talked about Huge $n$-fold Integer Programming, solving its Configuration LP and that a solution derived from it satisfies stronger proximity bounds than the solution of a normal relaxation. This is based on [[https://arxiv.org/abs/1909.07326|MIMO]], Section 3. I did not go into the full detail and you are not required to understand all of the proofs, but please try to understand the main concepts and statements, which are: |
| |
| * 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://arxiv.org/abs/2003.02187|kernels for scheduling problems.]] |
| |
| **Fourth lecture:** We talked about Mixed Integer Linear Programs, [[https://cunicz-my.sharepoint.com/:o:/g/personal/63735541_cuni_cz/EgHZ50r_8PVJmdyiKhlSnsoBr1koI1loAthyZ2kTeyjsRQ?e=ZF5QCa|notes are here]]. In particular note we discussed a neat trick of Hochbaum-Shantikumar on how to get a Separable Convex IP algorithm from a Linear IP algorithm. |
===== Parameterized Approximations for Steiner Trees ===== | ===== Parameterized Approximations for Steiner Trees ===== |
| |
- Proof of Borchers and Du Theorem: sections 1 and 3 of [[https://epubs.siam.org/doi/pdf/10.1137/S0097539795281086|Borchers and Du]] | - Proof of Borchers and Du Theorem: sections 1 and 3 of [[https://epubs.siam.org/doi/pdf/10.1137/S0097539795281086|Borchers and Du]] |
- Directed Steiner Tree parameterized by nr of Steiner vertices: sections 1, 4, and 5 of [[https://arxiv.org/pdf/1710.00668.pdf|Dovřak et al.]] | - Directed Steiner Tree parameterized by nr of Steiner vertices: sections 1, 4, and 5 of [[https://arxiv.org/pdf/1710.00668.pdf|Dovřak et al.]] |
- Undirected Steiner Tree (and Steiner Forest) parameterized by nr of Steiner vertices (and number of connected components): sections 1 and 3 of [[https://arxiv.org/pdf/1710.00668.pdf|Dovřak et al.]] | - Undirected Steiner Tree (and Steiner Forest) parameterized by nr of Steiner vertices (and nr of connected components): sections 1 and 3 of [[https://arxiv.org/pdf/1710.00668.pdf|Dvořak et al.]] |
| |