Seminář z aproximačních a online algoritmů
Seminar on Approximation and Online Algorithms

Andreas Emil Feldmann, Petr Kolman, Jiří Sgall

Doba a místo konání [Time and place]

Seminář se koná v pondělí od 14:00 v S6. [Seminar takes place on Monday 14:00 in S16]

Oznámení o seminářích se distribuuje pomocí mailing listu, do kterého se můžete zapsat na adrese https://kam.mff.cuni.cz/mailman/listinfo/algo-seminar-l.
You can subscribe to the mailing list with the seminar anouncement at https://kam.mff.cuni.cz/mailman/listinfo/algo-seminar-l.

Kontakt

https://sites.google.com/site/aefeldmann/, tel. 951 554 372;
http://kam.mff.cuni.cz/~kolman/, tel. 951 554 155;
http://iuuk.mff.cuni.cz/~sgall/, tel. 951 554 293.

Nejbližší program semináře [Next program]

May 20, 2019 (pondělí [Monday], 14:00, MFF UK Malá Strana S6)

Martin Koutecký: Near-linear time algorithm for 2-stage stochastic IPs
(joint work with Fritz Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klien, Asaf Levin, and Shmuel Onn)

Abstract: 2-stage stochastic integer programs model optimization problems in which the revelation of data and subsequent response happen in two stages, and the goal is to optimize the expected cost. In 2001, Hemmecke and Schultz have shown that 2-stage stochastic IPs with small blocks and small coefficients are fixed-parameter tractable in cubic time. We bring the polynomial dependency to almost linear by a combination of a novel proximity-scaling algorithm, bounds on equivalent objectives, and other techniques.


Předběžný další program [Preliminary future program]

Další články pro LS 2019 [More papers proposed for this semester]

Eli Fox-Epstein, Philip N. Klein, Aaron Schild: Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Effcient Approximation Schemes for Metric Problems. SODA 2019.

Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk: On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs. https://arxiv.org/abs/1707.02190

Sándor Kisfaludi-Bak, Jesper Nederlof, Erik Jan van Leeuwen: Nearly ETH-Tight Algorithms for Planar Steiner Tree with Terminals on Few Faces. https://arxiv.org/abs/1811.06871

Julia Chuzhoy, Sanjeev Khanna: Polynomial flow-cut gaps and hardness of directed cut problems. J. ACM 56(2), Article No. 6, 2009.

C.J. Argue, Sébastien Bubeck, Michael B. Cohen, Anupam Gupta, Yin Tat Lee: A Nearly-Linear Bound for Chasing Nested Convex Bodies. SODA 2019. Also
https://arxiv.org/abs/1806.08865

Rico Zenklusen: A 1.5-Approximation for Path TSP. SODA 2019. Also https://arxiv.org/abs/1805.04131

Samozřejmě, jako vždy, jsou vítany jsou i další náměty, zejména pak prezentace vlastních výsledků účastníků semináře.

Další články, o kterých jsme uvažovali, zbylé z minulého semestru atd.
[Additional proposed papers, leftovers from the last semester]

Andreas Wiese: A (1+eps)-approximation for Unsplittable Flow on a Path in fixed-parameter running time. ICALP 2017.
(presented by Lukáš Folwarczný)

Hans-Joachim Bockenhauer, Juraj Hromkovic, Joachim Kneis, Joachim Kupke: The Parameterized Approximability of TSP with Deadlines. Theory of Computing Systems 41:431–444, 2007.
(presented by Petr Vincena)

Sanjeev Arora: Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and Other Geometric ProblemsJACM 45:753–782, 1998.

Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan: From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. https://arxiv.org/abs/1708.04218.

Anupam Gupta, Euiwoong Lee, Jason Li: An FPT Algorithm Beating 2-Approximation for k-Cut. https://arxiv.org/abs/1710.08488.

Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan: From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. FOCS 2017. Also https://arxiv.org/abs/1708.04218.

Michael Lampis: Parameterized Approximation Schemes using Graph Widths. ICALP 2014. Also https://arxiv.org/abs/1311.2466.

Alice Paul, Daniel Freund, Aaron Ferber, David Shmoys and David Williamson: Prize-Collecting TSP with a Budget Constraint. ESA 2017.

Klaus Jansen and Lars Rohwedder: On the Configuration-LP of the Restricted Assignment Problem. SODA 2017: 2670-2678, also https://arxiv.org/abs/1611.01934.

Alantha Newman, Heiko Röglin, and Johanna Seif: The Alternating Stock Size Problem and the Gasoline Puzzle. ESA 2016. Also https://arxiv.org/abs/1511.09259.

János Balogh, József Békési, György Dósa, Leah Epstein, Asaf Levin: Online bin packing with cardinality constraints resolved. At https://arxiv.org/abs/1608.06415.

Harald Räcke: Optimal hierarchical decompositions for congestion minimization in networks. STOC 2008:255-264. Also here.

Jittat Fakcheroenphol, Kunal Talwar and Satish Rao: A tight bound on approximating arbitrary metrics by tree metrics. STOC 2003, J. Comput. Syst. Sci. 69(3): 485-497 (2004).


Předchozí program semináře [Past program]