December 6 (JST)Room A

Room B

Chair: Shuichi Hirahara

10:30--10:50

11:10--11:30

ESTPST

Chair: Yusuke Kobayashi

Online 1

Approximation 1

Streaming Algorithms for Graph k-Matching with Optimal or Near-

An Improved Approximation Algorithm for the Matching

Optimal Update Time

1:30

12/5

12/5

20:30

17:30

Augmentation Problem
Joseph Cheriyan, Robert Cummings, Jack Dippel, and Jasper

Jianer Chen, Qin Huang, Iyad Kanj, Qian Li, and Ge Xia

10:50--11:10

GMTOpening (Room A)

10:20--10:25

Zhu

Geometry 2

Approximation 2

Approximate Maximum Halfspace Discrepancy

Multimodal Transportation with Ridesharing of Personal Vehicles

Michael Matheny and Jeff M. Phillips

Qian-Ping Gu and JiaJian Leo Liang

Algorithm 1

Approximation 3

Exact and Approximation Algorithms for Many-To-Many Point
Matching in the Plane
Sayan Bandyapadhyay, Anil Maheshwari, and Michiel Smid

Algorithms for Normalized Multiple Sequence Alignments
Eloi Araujo, Luiz Rozante, Diego P Rubert and Fabio V Martinez

Chair: Yoshio Okamoto
Algorithm 2
13:00--13:20

4:00

Augmenting Graphs to Minimize the Radius

12/5

12/5

23:00

20:00

Joachim Gudmundsson, Yuan Sha, and Fan Yao
Algorithm 3
13:20--13:40

Linear-Time Approximation Scheme for k-Means Clustering ofAxis-Parallel Affine Subspaces
Kyungjin Cho and Eunjin OhAlgorithm 4

13:40--14:00

Feedback Vertex Set on Geometric Intersection Graphs
Shinwoo An and Eunjin Oh
Chair: Hee-Kap Ahn
Best Student Paper Presentation (Room A)

14:25--14:45

5:25

0:25

Interval Query Problem on Cube-free Median Graphs

12/5
21:25

Soh Kumabe
Chair: Yu Nakahata

14:50--15:10

Chair: Hironori Kiya

Graph 3

Game 1

Algorithms and Complexity on Indexing Elastic Founder GraphsComputing Shapley Values for Mean Width in 3-D

Massimo Equi, Tuukka Norri, Jarno Alanko, Bastien Cazaux,

Shuhao Tan

Alexandru I. Tomescu, and Veli Mäkinen

Game 2

Simple Envy-free and Truthful Mechanisms for Cake Cutting with

15:10--15:30

a Small Number of Cuts
Takao Asano
Chair: Hiro Ito

Chair: Hyung-Chan An

Graph 416:00--16:20

16:20--16:40

Geometry 1

Partitioning H-Free Graphs of Bounded Diameter

Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John

Paulusma, and Siani Smith

Iacono, and Micha Sharir

Graph 5

Approximation 5

Clique-Based Separators for Geometric Intersection Graphs

On the Extended TSP Problem

Leonidas Theocharous

12/5
23:00

Julián Mestre, Sergey Pupyrev, and Seeun William Umboh

Graph 6Approximation 6

Near-Optimal Distance Oracles for Vertex-Labeled Planar
16:40--17:00

2:00

Problems in the Algebraic Decision Tree Model

Christoph Brause, Petr Golovach, Barnaby Martin, DanielMark de Berg, Sándor Kisfaludi-Bak, Morteza Monemizadeh, and7:00

Subquadratic Algorithms for Some 3Sum-Hard GeometricGraphs

Probabilistic Analysis of Euclidean Capacitated Vehicle Routing

Jacob Evald, Viktor Fredslund-Hansen, and Christian WulffNilsen

Claire Mathieu and Hang Zhou

Chair: Kunihiko Sadakane
Invited Talk 1 (Room A)
17:30--18:30

Streaming Pattern Matching
Tatiana Starikovskaya (École normale supérieure, Paris)

8:30

3:30

0:30

December 7 (JST)Room A

Room B

GMT

EST

PST

Chair: Takeshi Tokuyama
Invited Talk 2 (Room A)

0:30

Spanning Properties of Variants of the Delaunay Graph

9:30--10:30

12/6

12/6

19:30

16:30

Prosenjit K. Bose (Carleton University)
Chair:Takeshi Tokuyama
Geometry 3
11:00--11:20

The VC-Dimension of Limited Visibility Terrains
Matt Gibson-Lopez and Zhongxiu Yang

11:20--11:40

FPT 1

2:00

Effective resistance and capacitance in simplicial complexes and12/6

12/6

21:00

18:00

a quantum algorithm
Mitchell Black and William Maxwell

Geometry 4

FPT 2

Clustering with Neighborhoods

Anonymity-Preserving Space Partitions

Hongyao Huang, Georgiy Klimenko, and Benjamin Raichel

11:40--12:00

Chair: Francois Le Gall

Ursula Hebert-Johnson, Chinmay Sonar, Subhash Suri, andVaishali Surianarayanan

Geometry 5

FPT 3

Approximating longest spanning tree with neighborhoods

Impatient PPSZ - a Faster algorithm for CSP

Ahmad Biniaz

Shibo Li and Dominik Scheder
4:00

13:00--13:20

12/6

12/6

23:00

20:00

13:20--13:40
Chair: Harumichi Nishimura
Quantum 1
13:40--14:00

14:30--14:50

Quantum Advantage with Shallow Circuits under Arbitrary
Corruption

Chair: Suguru Tamaki
FPT 5

Essentially Tight Kernels for (Weakly) Closed Graphs

Atsuya Hasegawa and Francois Le Gall

Tomohiro Koana, Christian Komusiewicz, and Frank Sommer

Chair: Yutaro Yamaguchi

Chair: Hirotaka Ono

OR 1

Distributed 1

A Faster Algorithm for Maximum Flow in Directed Planar Graphs

Group Evacuation on a Line by Agents with Different

with Vertex Capacities

5:30

0:30

12/6
21:30

Communication Abilities
Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis, Danny

Julian Enoch, Kyle Fox, Dor Mesica, and Shay Mozes

Krizanc, Lata Narayanan, Jaroslav Opatrny, Denis Pankratov, andSunil Shende

OR 2
14:50--15:10

Maximum-Weight Matching in Sliding Windows and Beyond
Leyla Biabani, Mark de Berg, and Morteza Monemizadeh
FPT 6

15:10--15:30

Filling Crosswords is Very Hard
Laurent Gourves, Ararat Harutyunyan, Michael Lampis, andNikolaos Melissinos
Chair: Yushi Uno

Distributed 2Lower Bounds for Induced Cycle Detection in Distributed
ComputingFrançois Le Gall and Masayuki Miyamoto
Distributed 3

Distributed approximations of f-matchings and b-matchings ingraphs of sub-logarithmic expansion
Andrzej Czygrinow, Michał Hanćkowiak, and Marcin Witkowski

Chair: Wing-Kai Hon

Graph 716:00--16:20

7:00

2:00

A Characterization of Individualization-Refinement Trees

12/6
23:00

Markus Anders, Jendrik Brachter, and Pascal Schweitzer

16:20--16:40

Graph 8Online 2Truly Subquadratic Exact Distance Oracles with Constant Query

Making Three Out of Two: Three-Way Online CorrelatedTime for Planar Graphs

Selection

Viktor Fredslund-Hansen, Shay Mozes, and Christian WulffNilsen
Graph 9Interval edge coloring of bipartite graphs with small vertex
16:40--17:00

degreesMichał Małafiejski, Anna Małafiejska, Krzysztof Ocetkiewicz andKrzysztof Pastuszak
Chair: Hee-Kap Ahn
Geometry 6

17:30--17:50

Self-Improving Voronoi Construction for a Hidden Mixture ofProduct Distributions
Siu-Wing Cheng and Man Ting Wong
Geometry 7

17:50--18:10

Connected Coordinated Motion Planning with Bounded Stretch
Sándor P. Fekete, Phillip Keldenich, Ramin Kosfeld, ChristianRieck, and Christian Scheffer

18:10--18:30

18:30--18:50

Yongho Shin and Hyung-Chan AnOnline 3

Tight Competitive Analyses of Online Car-sharing Problems
Ya-Chun Liang, Kuan-Yun Lai, Ho-Lin Chen, and Kazuo Iwama

Chair: Akitoshi Kawamura
FPT 4

Fine-grained Meta-Theorems for Vertex Integrity
Michael Lampis and Valia Mitsou
FPT 7

Grid Recognition: Classical and Parameterized Computational
Perspectives
Siddharth Gupta, Guy Sa'ar, and Meirav Zehavi

Geometry 8

Graph 12

Enclosing Depth and other Depth Measures

Selected Neighbor Degree Forest Realization

Patrick Schnider

Amotz Bar-Noy, David Peleg, Dror Rawitz and Elad Yehezkel

Geometry 9Graph 2Illuminating the x-axis by α-floodlights

Untangling Circular Drawings: Algorithms and Complexity

Bengt J. Nilsson, David Orden, Leonidas Palios, Carlos Seara, andSujoy Bhore, Guangping Li, Martin Nollenburg, Ignaz Rutter,Paweł Żylińskiand Hsiang-Yun Wu

8:30

3:30

0:30

December 8 (JST)Room A

Room BGMT

ESTPST

Chair: Kunihiko Sadakane
Best Paper Presentation (Room A)
9:55--10:25

0:55

Shortest Beer Path Queries in Outerplanar Graphs

12/7

12/7

19:55

16:55

Joyce Bacic, Saeed Mehrabi, and Michiel Smid
Chair: Sang-il Oum

10:30--10:50

10:50--11:10

Chair: Takuya Mieno

Graph 10

Data structures 1

Efficiently Partitioning the Edges of a 1-Planar Graph into a

Inverse Suffix Array Queries for 2-Dimensional Pattern Matching

Planar Graph and a Forestin Near-Compact SpaceSam Barr and Therese Biedl

Dhrumil Patel and Rahul Shah

Graph 11

Data structures 2

On the kernel and related problems in interval digraphs

Dynamic Boolean Formula Evaluation

Mathew C. Francis, Pavol Hell, and Dalu Jacob

Rathish Das, Andrea Lincoln, Jayson Lynch, and Ian Munro

1:30

12/7

12/7

20:30

17:30

Approximation 4
11:10--11:30

Separated Red Blue Center Clustering
Marzieh Eskandari, Bhavika Khare, and Nirman Kumar
Chair: Naonori Kakimura
OR 3

13:00--13:20

4:00

Adaptive Regularized Submodular Maximization

12/7

12/7

23:00

20:00

Shaojie Tang and Jing Yuan
OR 4
13:20--13:40

Γ-graphic delta-matroids and their applications
Donggyu Kim, Duksang Lee, and Sang-il Oum
OR 5

13:40--14:00

An Approximation Algorithm for Maximum Stable Matching withTies and Constraints
Yu Yokoi
Chair: Chung-Shou Liao
Online 4

14:30--14:50

5:30

0:30

Skeletons and Minimum Energy Scheduling

12/7
21:30

Antonios Antoniadis, Gunjan Kumar, and Nikhil Kumar
Online 5
14:50--15:10

Machine Covering in the Random-Order Model
Susanne Albers, Waldo Gálvez, and Maximilian Janke
Online 6

15:10--15:30

Nearly-Tight Lower Bounds for Set Cover and Network Design
with Deadlines/Delay
Noam Touitou
Chair: Kazuhisa Makino

16:00--16:20

Random Graph 1

Cryptographic Hardness under Projections for Time-Bounded

MAX CUT in Weighted Random Intersection Graphs andKolmogorov Complexity
Eric Allender, John Gouwar, Shuichi Hirahara, and Caleb

16:20--16:40

Spirakis
Random Graph 2

Complexity 3

Unique-Neighbor-Like Expansion and Group-Independent
Cosystolic Expansion
Tali Kaufman and David Mass

Chair: Siu-Wing Cheng
Geometry 10
17:30--17:50

On geometric priority set cover problems
Aritra Banik, Rajiv Raman, and Saurabh Ray

17:50--18:10

Schelling Process
Thomas Bläsius, Tobias Friedrich, Martin S. Krejca, and Louise
Molitor
Random Graph 3

Piecewise-Linear Farthest-Site Voronoi DiagramsFranz Aurenhammer, Evanthia Papadopoulou, and MartinSuderland
Chair: Srinivasa Rao Satti
Data structures 4

Space-Efficient Algorithms for Reachability in Directed Geometric
GraphsSujoy Bhore and Rahul Jain

Geometry 11

Data structures 5

Repetition- and Linearity-Aware Rank/Select Dictionaries

Patrick Schnider

Paolo Ferragina, Giovanni Manzini, and Giorgio Vinciguerra

Geometry 12

Data structures 6

Dynamic Data Structures for k-Nearest Neighbor Queries

Pattern Masking for Dictionary Matching

Sarita de Berg and Frank Staals

Grigorios Loukides, Nadia Pisanti, Solon P. Pissis, and Jakub

Geometry 13

Data structures 7

Preference-based Trajectory Clustering - An Application ofResilient Level Ancestor, Bottleneck, and Lowest Common

Panagiotis Charalampopoulos, Huiping Chen, Peter Christen,Radoszewski

18:30--18:50

Geometric Hitting Sets
Florian Barth, Stefan Funke, and Claudius Proissl

12/7
23:00

The Impact of Geometry on Monochrome Regions in the Flip

The complexity of sharing a pizza

18:10--18:30

2:00

Discrepancy of Sparse Random Set Systems

RobelleIdentity testing under label mismatch

7:00

Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul

Complextiy 2Clément L. Canonne and Karl Wimmer

16:40--17:00

Chair: Kunihiko Sadakane

Complextiy 1

Ancestor Queries in Dynamic Trees
Luciano Gualà, Stefano Leucci, and Isabella Ziccardi

8:30

3:30

0:30