Od akademického roku 2020/21 se seminář slučuje a pokračuje jako Seminář z teoretické informatiky - NTIN102 - společně s prof. Michalem Kouckým a dalšími kolegy, začíná 13. 10.
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.
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.
Ken-Ichi Kawarabayashi, Bingkai Lin: A nearly
5/3-approximation FPT Algorithm for Min-k-Cut. SODA
2020, pp. 990-999.
Mitali Bafna, Chi-Ning, Chou Zhao Song: An Exposition of Dinur-Khot-Kindler-Minzer-Safra's Proof for the 2-to-2 Games Conjecture.
Sami Davies, Thomas Rothvoss, and Yihao Zhang: A Tale of
Santa Claus, Hypergraphs and Matroids. SODA 2020, pp.
2748-2757.
Yair Bartal, Nova Fandina, and Seeun William Umboh: Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds. SODA 2020, pp. 1538-1557.
Yossi Azar, Amit Jacob Fanani: Deterministic Min-Cost Matching with Delays. WAOA 2018: 21-35.
Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar,
Ofir Geri, Haim Kaplan, Rahul M. Makhijani, Yuyi Wang, Roger
Wattenhofer: Min-Cost
Bipartite Perfect Matching with Delays. APPROX-RANDOM
2017:
1:1-1:20.
Vincent Cohen-Addad, Marcin Pilipczuk, Michał Pilipczuk: A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs. FOCS 2019. Also https://arxiv.org/abs/1904.10680
Eli Fox-Epstein, Philip N. Klein, Aaron Schild: Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems. SODA 2019.
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.
Robert Krauthgamer, James R. Lee, Havana Rika: Flow-Cut Gaps and Face Covers in Planar Graphs. SODA 2019. Also https://arxiv.org/abs/1811.02685
Fabrizio Grandoni, Bundit Laekhanukit, Shi Li: O(log^2 k / loglog k) -Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm. STOC 2019. Also https://arxiv.org/abs/1811.03020
Chandra Chekuri, Kent Quanrud and Chao Xu: LP Relaxation and Tree Packings for Minimum k-Cut. SOSA 2019.
Deeparnab Chakrabarty and Chaitanya Swamy: Simpler and Better
Algorithms for Minimum-Norm Load Balancing. ESA 2019. Also
https://arxiv.org/abs/1905.00044
Anupam Gupta, Euiwoong Lee, Jason Li: The Number of Minimum k-Cuts: Improving the Karger-Stein Bound. STOC 2019. Also https://arxiv.org/abs/1906.00417
Nikhil Bansal: On a generalization of iterated and randomized rounding. STOC 2019. Also https://arxiv.org/abs/1811.01597Dá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
Andreas Wiese: A
(1+eps)-approximation for Unsplittable Flow on a Path in
fixed-parameter running time. ICALP 2017.
Hans-Joachim Bockenhauer, Juraj Hromkovic, Joachim Kneis,
Joachim Kupke: The
Parameterized
Approximability of TSP with Deadlines. Theory of
Computing Systems 41:431–444, 2007.
Sanjeev Arora: Polynomial
Time
Approximation Schemes for Euclidean Traveling Salesman and
Other Geometric Problems. JACM 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]