Best ESA Paper
Beginning in 2007, EATCS sponsors an award for the best paper at ESA.
A brief history of the prize follows below.
 |
|
 |
|
- Track A: Karl Bringmann, Anita Dürr and Adam Polak: “Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing”
- Track B: Hideo Bannai, Mitsuru Funakoshi, Diptarama Hendrian, Myuji Matsuda and Simon Puglisi: "Height-bounded Lempel-Ziv encodings”
- Track S: Zhiyi Huang, Zahra Parsaeian and Zixuan Zhu: “Laminar Matroid Secretary: Greedy Strikes Back"
|
|
 |
|
 |
|
|
|
|
- Track A: Ursula Hebert-Johnson, Daniel Lokshtanov and Eric Vigoda: "Counting and Sampling Labeled Chordal Graphs in Polynomial Time"
- Track B: Xiangyun Ding, Xiaojun Dong, Yan Gu, Youzhe Liu and Yihan Sun: "Efficient Parallel Output-Sensitive Edit Distance"
- Track S: Oleg Verbitsky and Maksim Zhukovskii: "Canonization of a Random Graph by Two Matrix-Vector Multiplications"
|
|
|
|
|
|
|
|
|
- Track A: Stefan Walzer: "Insertion Time of Random Walk Cuckoo Hashing below the Peeling Threshold"
- Track B: Chris Schwiegelshohn and Omar Ali Sheikh-Omar: "An Empirical Evaluation of k-Means Coresets"
- Track S: Alejandro Flores-Velazco: "Improved Search of Relevant Points for Nearest-Neighbor Classification"
|
|
|
|
|
|
|
|
|
- Track A: Zhiyang He, Jason Li and Magnus Wahlström: "Near-linear-time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs"
- Track B: Simon D. Fink, Matthias Pfretzschner and Ignaz Rutter: "Experimental Comparison of PC-Trees and PQ-Trees"
|
|
|
|
|
|
|
|
|
2020 / Pisa, Italy (online virtual conference)
- Track A: Moritz Venzin and Friedrich Eisenbrand: "Approximate $CVP_{\infty}$ in time $2^{0.802 n}$"
- Track B: Georg Osang, Mael Rouxel-Labbé and Monique Teillaud: "Generalizing CGAL Periodic Delaunay Triangulations"
|
|
|
|
|
|
|
|
|
- Track A: Peyman Afshani, Rolf Fagerberg, David Hammer, Riko Jacob, Irina Kostitsyna, Ulrich Meyer, Manuel Penschuck and Nodari Sitchinava: "Fragile Complexity of Comparison-Based Algorithms"
- Track B: Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck and Christopher Weyand: "Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs"
|
|
|
|
|
|
|
|
|
- Track A: Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, Eva Rotenberg: "Decremental SPQR-trees for Planar Graphs"
- Track B: Daniel R. Schmidt, Bernd Zey, François Margot: "An exact algorithm for the Steiner forest problem"
|
|
|
|
|
|
|
|
|
- Track A: Marek Cygan, Lukasz Kowalik and Arkadiusz Socala: "Improving TSP tours using dynamic programming over tree decompositions"
- Track B: Hisao Tamaki: "Positive-instance driven dynamic programming for treewidth"
|
|
|
|
|
|
|
|
|
- Stefan Kratsch: "A randomized polynomial kernelization for Vertex Cover with a smaller parameter"
- Thomas Blaesius, Tobias Friedrich, Anton Krohmer and Soeren Laue: "Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane"
|
|
|
|
|
|
|
|
|
- Rajesh Chitnis, Laszlo Egri and Daniel Marx : "List H-Coloring a Graph by Removing Few Vertices''
- Sander P. A. Alewijnse, Quirijn W. Bouts, Alex P. ten Brink and Kevin Buchin : "Computing the Greedy Spanner in Linear Space''
|
|
|
|
|
|
