Accepted papers at SODA’19

Eight papers co-authored by our colleagues at the Institute of Informatics of University of Warsaw have been accepted to SIAM Symposium on Discrete Algorithms (SODA 2019), to be held January 6-9, 2019 in San Diego, California, USA:

(1 + eps)-Approximate Incremental Matching in Constant Deterministic Amortized Time
Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski, Chris Schwiegelshohn and Shay Solomon

A PTAS for Euclidean TSP with Hyperplane Neighborhoods
Antonios Antoniadis, Krzysztof Fleszar, Ruben Hoeksma and Kevin Schewior

A Subquadratic Approximation Scheme for Partition
Marcin Mucha, Karol Węgrzycki, Michał Włodarczyk

Losing Treewidth by Separating Subsets
Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, Michał Włodarczyk

Polynomial bounds for centered colorings on proper minor-closed graph classes
Michał Pilipczuk, Sebastian Siebertz

Polynomial-time algorithm for Maximum Weight Independent Set on P_6 -free graphs
Andrzej Grzesik, Tereza Klimošová, Marcin Pilipczuk, Michał Pilipczuk

The streaming k-mismatch problem
Raphael Clifford, Tomasz Kociumaka, Ely Porat

Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
Wojciech Czerwiński, Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdziński, Ranko Lazić, Paweł Parys


Congratulations and see you at the conference!

Adam Karczmarz

Leave a Reply

Your email address will not be published. Required fields are marked *