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

Petr Kolman, Jiří Sgall

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

UMLUVENO: v LS 2017 se seminář koná v pondělí od 12:20 v S4

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

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]

24. 4. 2017 (pondělí [Monday], 12:20, MFF UK Malá Strana S4)

Morteza Monemizadeh: Testable Bounded Degree Graph Properties Are Random Order Streamable.
ICALP 2017.
(joint work with S. Muthukrishnan, Pan Peng, and Christian Sohler)
 
Abstract:
We study graph streaming problems. We  transform known property testing algorithms into streaming ones. In particular, our main result is that for bounded degree graphs, any property that is constant-query testable in the adjacency list model can be tested with constant space in single-pass random order model. Our results are obtained by estimating the distribution of local neighborhoods of the vertices on a random order graph stream using constant space. We also apply this approach to constant time approximation algorithms in the adjacency list model and get single-pass random order streaming algorithms for all of them. For example, we get constant-space single-pass random order streaming algorithms for approximating the size of a maximum matching with additive error $\epsilon n$ ($n$ is the number of nodes). Our results are among the first known constant space graph streaming algorithms, while $\Omega(n)$ space is needed for many graph streaming problems and previous results typically use the semi-streaming model of $O(n\cdot \poly\log n)$ space.


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

15. 5. 2017 (pondělí [Monday], 12:20, MFF UK Malá Strana S4)

Martin Skutella: A Note on the Ring Loading Problem. SIAM J. Discrete Math. 30: 327-342 (2016). Also https://arxiv.org/abs/1405.0789.
(referuje Lukáš Folwarzný)

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

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.

Martijn van Ee, Leo van Iersel, Teun Janssen, René Sitters: A priori TSP in the Scenario Model. WAOA 2016: 183-196.

Esther M. Arkin, Jie Gao, Adam Hesterberg, Joseph S. B. Mitchell, Jiemin Zeng: The Shortest Separating Cycle Problem. WAOA 2016: 1-13.

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]

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.

Haris Aziz, and Simon Mackenzie: A Discrete and Bounded Envy-free Cake Cutting Protocol for Four Agents. STOC 2016, also http://arxiv.org/abs/1508.05143.

Adam Kurpisz, Monaldo Mastrolilli, Claire Mathieu, Tobias Mömke, Victor Verdugo, Andreas Wiese: Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines. IPCO 2016.

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.

Guy Even, Moti Medina, and Adi Rosén: A Constant Approximation Algorithm for Scheduling Packets on Line Networks. ESA 2016. Also https://arxiv.org/abs/1602.06174.

Yossi Azar and Oren Gilon: Buffer Management for Packets with Processing Times. ESA 2015.

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]