Proceedings      Day 1   Day 2   Day 3   Day 4    Day 5All in Hong Kong time (UTC+8)  

December 14 (Monday)

15:50–16:00 Opening(Chair: Siu-Wing Cheng)

16:00–17:00 INVITED TALK 1 (Chair: Yixin Cao)

Sang-il Oum
How to decompose a graph into a tree-like structure

17:00–17:10 BREAK

17:10–18:10 SESSION 1 (Chair: Sang-il Oum)

Joachim Gudmundsson, Yuan Sha, and Sampson Wong
Approximating the packedness of polygonal curves

Marc van Kreveld, Tillmann Miltzow, Tim Ophelders, Willem Sonke, and Jordi L. Vermeulen
Between Shapes, Using the Hausdorff Distance

Boris Aronov and Jean Cardinal
Geometric Pattern Matching Reduces to k-SUM

18:10–19:40 BREAK

19:40–20:50 SESSION 2 (Chair: Minming Li)

Wolfgang Mulzer and Max Willert
Compact Routing in Unit Disk Graphs

Maciej Dulęba, Paweł Gawrychowski, and Wojciech Janczewski
Efficient Labeling for Reachability in Directed Acyclic Graphs

Bartlomiej Dudek and Pawel Gawrychowski
Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs (Best paper, 30 mins)

20:50–21:00 BREAK

21:00–22:00 SESSION 3 (Chair: Jesper Jansson)

Anadi Agrawal and Paweł Gawrychowski
A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem

Anthony Labarre
Sorting by Prefix Block-Interchanges

Philip Bille and Inge Li Gørtz
Random Access in Persistent Strings

December 15 (Tuesday)

8:00–9:20 SESSION 4 (Chair: Kyle Fox)

Peter Bradshaw, Tomáš Masařík, and Ladislav Stacho
Flexible List Colorings in Graphs with Special Degeneracy Conditions

Adrian Dumitrescu, Anirban Ghosh, and Csaba D. Tóth
Sparse Hop Spanners for Unit Disk Graphs

Haozhou Pang and Mohammad R. Salavatipour
Approximation Algorithms for Generalized Path Scheduling

Dylan Hyatt-Denesik, Mirmahdi Rahgoshay, and Mohammad R. Salavatipour
Approximations for Throughput Maximization

9:20–9:40 BREAK

9:40–11:00 SESSION 5 (Chair: Richard Peng)

Eunjin Oh
Shortest-Path Queries in Geometric Networks

Takao Asano and Hiroyuki Umeda
Cake Cutting: An Envy-free and Truthful Mechanism with a Small Number of Cuts

Jungho Ahn, Eun Jung Kim, and Euiwoong Lee
Towards constant-factor approximation for chordal / distance-hereditary vertex deletion

Kristóf Bérczi, Naonori Kakimura, and Yusuke Kobayashi
Market Pricing for Matroid Rank Valuations

16:00–17:00 INVITED TALK 2(Chair: Siu-Wing Cheng)

Ke Yi
Worst-case optimal join algorithms

17:00–17:10 BREAK

17:10–18:10 SESSION 6 (Chair: Ke Yi)

Kentaro Sumigawa, Sankardeep Chakraborty, Kunihiko Sadakane, and Srinivasa Rao Satti
Enumerating Range Modes

Guido Brückner and Ignaz Rutter
An SPQR-Tree-Like Embedding Representation for Level Planarity

Stefan Funke and Felix Weitbrecht
Efficiently Computing all Delaunay Triangles Occurring over all Contiguous Subsequences

18:10–19:40 BREAK

19:40–20:50 SESSION 7 (Chair: Minming Li)

Richard Santiago and Yuichi Yoshida
Weakly Submodular Function Maximization Using Local Submodularity Ratio

Umang Bhaskar and Gunjan Kumar
Partial Function Extension with Applications to Learning and Property Testing

Joep Hamersma, Marc van Kreveld, Yushi Uno, and Tom C. van der Zanden
Gourds: a sliding-block puzzle with turning (Best paper, 30 mins)

20:50–21:00 BREAK

21:00–22:00 SESSION 8 (Chair: Ryuhei Uehara)

Nicolas Bousquet, Alice Joffard, and Paul Ouvrard
Linear transformations between dominating sets in the TAR-model

Till Fluschnik, Rolf Niedermeier, Carsten Schubert, and Philipp Zschoche
Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs

Matthias Bentert, Klaus Heeger, and Dušan Knop
Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters

December 16 (Wednesday)

8:00–9:20 SESSION 9 (Chair: Guochuan Zhang)

Josh Brunner, Erik D. Demaine, Dylan Hendrickson, and Julian Wellman
Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard

Erik D. Demaine, Justin Kopinsky, and Jayson Lynch
Recursed is not Recursive: A Jarring Result

Leo Alcock, Sualeh Asif, Jeffrey Bosboom, Josh Brunner, Charlotte Chen, Erik D. Demaine, Rogers Epstein, Adam Hesterberg, Lior Hirschfeld, William Hu, Jayson Lynch, Sarah Scheffler, and Lillian Zhang
Arithmetic Expression Construction

Ke Chen and Adrian Dumitrescu
Multiparty Selection

9:20–9:40 BREAK

9:40–11:00 SESSION 10 (Chair: Qilong Feng)

Kei Uchizawa
Size, Depth and Energy of Threshold Circuits Computing Parity Function

Yoshifumi Sakai and Shunsuke Inenaga
A reduction of the dynamic time warping distance to the longest increasing subsequence length

Yuma Tamura, Takehiro Ito, and Xiao Zhou
Minimization and Parameterized Variants of Vertex Partition Problems on Graphs

Sanjana Dey, Florent Foucaud, Subhas C. Nandy, and Arunabha Sen
Discriminating Codes in Geometric Setups

16:00–17:00 SESSION 11 (Chair: Sungjin Im)

Predrag Krnetić, Darya Melnyk, Yuyi Wang, and Roger Wattenhofer
The k-Server Problem with Delays on the Uniform Metric Space

Mark de Berg, Aleksandar Markovic, and Seeun William Umboh
The Online Broadcast Range-Assignment Problem

Nguyễn Kim Thắng
Online Primal-Dual Algorithms with Configuration Linear Programs

17:00–19:40 BREAK

19:40–20:40 SESSION 12 (Chair: László Végh)

Loukas Georgiadis and Evangelos Kosinas
Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems

Kishen N. Gowda, Aditya Lonkar, Fahad Panolan, Vraj Patel, and Saket Saurabh
Improved FPT Algorithms for Deletion to Forest-like Structures

Tomohiro Koana, Christian Komusiewicz, and Frank Sommer
Computing Dense and Sparse Subgraphs of Weakly Closed Graphs

20:40–21:00 BREAK

21:00–22:00 SESSION 13 (Chair: Prudence Wong)

Taku Onodera and Tetsuo Shibuya
Wear Leveling Revisited

Trung Thanh Nguyen and Jörg Rothe
Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs

Martin Koutecký and Johannes Zink
Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines

December 17 (Thursday)

8:00–9:20 SESSION 14 (Chair: Kirk Pruhs)

Pedro Montealegre, Diego Ramírez-Romero, and Ivan Rapaport
Shared vs Private Randomness in Distributed Interactive Proofs

Xuangui Huang
Space Hardness of Solving Structured Linear Systems

Angel A. Cantu, Austin Luchsinger, Robert Schweller, and Tim Wylie
Signal Passing Self-Assembly Simulates Tile Automata

Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, and Chunhao Wang
Quantum-inspired algorithms for solving low-rank linear equation systems with logarithmic dependence on the dimension

9:20–10:00 BREAK

10:00–10:40 SESSION 15 (Chair: Yoshio Okamoto)

Kangsan Kim, Yongho Shin, and Hyung-Chan An
Constant-Factor Approximation Algorithms for the Parity-Constrained Facility Location Problem

Qilong Feng, Zhen Zhang, Ziyun Huang, Jinhui Xu, and Jianxin Wang
A Unified Framework of FPT Approximation Algorithms for Clustering Problems

10:40–19:40 BREAK

19:40–20:40 SESSION 16 (Chair: Magnus Wahlström)

Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, and Amer E. Mouawad
On girth and the parameterized complexity of token sliding and token jumping

Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse, and Paweł Rzążewski
Sparsification Lower Bounds for List H-Coloring

Fabian Frei, Edith Hemaspaandra, and Jörg Rothe
Complexity of Stability

20:40–21:00 BREAK

21:00–22:00 SESSION 17 (Chair: Michał Pilipczuk)

Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, and Philipp Zschoche
Finding Temporal Paths under Waiting Time Constraints

Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, and Manuel Sorge
The Complexity of Connectivity Problems in Forbidden-Transition Graphs and Edge-Colored Graphs

Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, and Nikolaos Melissinos
(In)approximability of Maximum Minimal FVS

December 18 (Friday)

15:00–16:20 SESSION 18 (Chair: Wing-Kai Hon)

William L. Holland, Anthony Wirth, and Justin Zobel
Recency queries with succinct representation

Meng He, J. Ian Munro, Yakov Nekrich, Sebastian Wild, and Kaiyu Wu
Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees

Amihood Amir and Itai Boneh
Update Query Time Trade-off for Dynamic Suffix Arrays

Sung-Hwan Kim and Hwan-Gue Cho
Indexing Isodirectional Pointer Sequences

16:20–16:40 BREAK

16:40–18:00 SESSION 19 (Chair: O-Joung Kwon)

Walter Kern and Daniël Paulusma
Contracting to a Longest Path in H-Free Graphs

Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, and Danil Sagunov
Diverse Pairs of Matchings

Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou, and Bodhayan Roy
Algorithms and complexity for geodetic sets on planar and chordal graphs

Nikhil Kumar
Multicommodity Flows in Planar Graphs with Demands on Faces