Program

Workshop on Frontiers of Combinatorial Optimization & Geometric Computing
at Hotel Royal Chiaohsi

 

               Sunday, December 16, 2018
09:00 – 09:30 Registration
09:30 – 10:30 Kurt Mehlhorn (Max Planck, Germany)
Reflections on the Interplay of Theory and Practice
10:30 – 11:00 Coffee/Tea Break
11:00 – 12:00 Tetsuo Asano (JAIST, Japan)
Three unsolved problems
12:00 – 14:00 Lunch
14:00 – 15:00 Robert E. Tarjan (Princeton University, USA)
Concurrent Connected Components
15:00 – 15:30 Coffee/Tea Break
15:30 – 16:30 J. Ian Munro (University of Waterloo, Canada)
Fast Stable Sorting, Adapting to Existing Runs
16:30 – 17:30 Panel Discussion
Chair: D.T. Lee (Academia Sinica, Taiwan)
18:00 – 20:00 Welcome Reception of ISAAC 2018

 

The 29th International Symposium on Algorithms and Computation (ISAAC 2018)
at Hotel Royal Chiaohsi

 

               Monday, December 17, 2018

08:30 – 09:00 Registration
09:00 – 10:00 Keynote Speech: Shang-Hua Teng (University of Southern California)
Going Beyond Traditional Characterizations in the Age of Big Data and Network Sciences
10:00 – 10:20 Coffee/Tea Break
10:20 – 12:00 Session 1A | Session 1B
12:00 – 13:30 Lunch
13:30 – 15:10 Session 2A | Session 2B
15:10 – 15:40 Coffee/Tea Break
15:40 – 17:20 Session 3A | Session 3B
 
               Tuesday, December 18, 2018
08:30 - 09:00 Registration
09:00 - 10:00 Keynote Speech: Clifford Stein (Columbia University)
Approximate Matchings in Massive Graphs via Local Structure
10:00 - 10:20 Coffee/Tea Break
10:20 - 12:00 Session 4A | Session 4B
12:00 - 13:30 Lunch
13:30 - 15:10 Session 5A | Session 5B
15:10 - 15:40 Coffee/Tea Break
15:40 - 16:55 Session 6A | Session 6B
17:00 - 18:00 The Open Problem Session
Co-Chairs: Sándor Fekete and Luca Trevisan
18:30 - 21:00 Conference Banquet
 
               Wednesday, December 19, 2018
08:30 - 09:00 Registration
09:00 - 09:30 Best Paper Award Presentation
09:30 - 10:00 Best Student Paper Award Presentation
10:00 - 10:20 Coffee/Tea Break
10:20 - 12:00 Session 7A | Session 7B
12:00 - 13:30 Lunch
13:30 - 15:10 Session 8A | Session 8B
15:10 - 15:40 Coffee/Tea Break
15:40 - 17:20 Session 9A | Session 9B
17:20 - 17:30 Closing
 
Session 1A [Graph Algorithms]
  • Tereza Klimošová, Josef Malík, Tomáš Masařík, Jana Novotná, Daniël Paulusma, and Veronika Slívová. Colouring (P_r + P_s )-Free Graphs
  • Guillaume Ducoffe and Alexandru Popa. The use of a pruned modular decomposition for Maximum Matching algorithms on some graph classes
  • Davide Bilò and Kleitos Papadopoulos. A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners
  • Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura and Takeaki Uno. Efficient Enumeration of Dominating Sets for Sparse Graphs
Session 1B [Complexity]
  • Md Lutfar Rahman and Thomas Watson. Complexity of Unordered CNF Games
  • Kenneth Hoover, Russell Impagliazzo, Ivan Mikhailin, and Alexander Smal. Half-duplex communication complexity
  • Takashi Ishizuka and Naoyuki Kamiyama. On the Complexity of Stable Fractional Hypergraph Matching
  • Matthew P. Johnson. Deciding the Closure of Inconsistent Rooted Triples is NP-Complete
Session 2A [Graph Algorithms]
  • Johanna E. Preißer and Jens M. Schmidt. Computing Vertex-Disjoint Paths in Large Graphs using MAOs
  • Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, and Naoki Katoh. An $O(n^2\log^2 n)$ Time Algorithm for Minmax Regret Minsum Sink on Path Networks
  • Delia Garijo, Alberto Marquez, Natalia Rodríguez, and Rodrigo Silveira. Computing optimal shortcuts for networks
  • Georgia Avarikioti, Yuyi Wang, and Roger Wattenhofer. Algorithmic Channel Design
Session 2B [Fixed Parameter Tractable algorithms]
  • Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Counting connected subgraphs with maximum-degree-aware sieving
  • Pavel Dvořák, Dušan Knop, and Tomáš Toufar. Target Set Selection in Dense Graph Classes
  • Andreas Björklund and Thore Husfeldt. Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm
  • Eun Jung Kim, Maria Serna, and Dimitrios Thilikos. Data-compression for Parametrized Counting Problems on Sparse graphs
Session 3A [Parallel and distributed algorithms]
  • Samir Datta, Raghav Kulkarni, Ashish Kumar, and Anish Mukherjee. Planar Maximum Matching: Towards a Parallel Algorithm
  • Andrzej Czygrinow, Wojciech Wawrzyniak, Marcin Witkowski, and Michal Hanckowiak. Distributed approximation algorithms for the Minimum Dominating Set in $K_h$-minor-free graphs
  • Cody Geary, Pierre-étienne Meunier, Nicolas Schabanel, and Shinnosuke Seki. Proving the Turing Universality of Oritatami Co-Transcriptional Folding
Session 3B [Fixed Parameter Tractable algorithms]
  • Jiehua Chen, Hendrik Molter, Manuel Sorge, and Ondrej Suchy. Cluster Editing in Multi-Layer and Temporal Graphs
  • Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, and Saket Saurabh. Parameterized Query Complexity of Hitting Set using Stability of Sunflowers
  • Pankaj Agarwal, Haim Kaplan, Geva Kipper, Wolfgang Mulzer, Günter Rote, Micha Sharir, and Allen Xiao. Approximate Minimum-Weight Partial Matching under Translation
  • Tatsuya Akutsu, Jesper Jansson, Ruiming Li, Atsuhiro Takasu, and Takeyuki Tamura. New and Improved Algorithms for Unordered Tree Inclusion
Session 4A [Graph theory]
  • Patrizio Angelini, Michael Bekos, Michael Kaufmann, Maximilian Pfister, and Torsten Ueckerdt. Beyond-Planarity: Turán-type Results for Non-Planar Bipartite Graphs
  • Yen-Ting Chen, Meng-Tsung Tsai, and Shi-Chun Tsai. A Dichotomy Result for Cyclic-Order Traversing Games
  • Guillaume Ducoffe and Alexandru Popa. The b-Matching problem in distance-hereditary graphs and beyond
  • Qilong Feng, Guanlan Tan, Senmin Zhu, Jianxin Wang, and Bin Fu. New Algorithms for Edge Induced K\"{o}nig-Egerv\'{a}ry Subgraph Based on Gallai-Edmonds Decomposition
Session 4B [Combinatorial Optimization]
  • Michael Matheny and Jeff Phillips. Computing Approximate Statistical Discrepancy
  • Alfonso Cevallos, Friedrich Eisenbrand, and Sarah Maria Morell. Diversity maximization in doubling metrics
  • Nader Bshouty and Waseem Makhoul. On Polynomial time Constructions of Minimum Height Decision Tree
  • Priyanka Mukhopadhyay and Divesh Aggarwal. Improved algorithms for the Shortest Vector Problem and the Closest Vector Problem in the infinity norm
Session 5A [Graph theory and Drawing]
  • Matthias Bentert, Alexander Dittmann, Leon Kellerhals, André Nichterlein, and Rolf Niedermeier. An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
  • Hiroki Osawa, Akira Suzuki, Takehiro Ito, and Xiao Zhou. Algorithms for Coloring Reconfiguration under Recolorability Constraints
  • On-Hei Solomon Lo and Jens M. Schmidt. A Cut Tree Representation for Pendant Pairs
  • Emilio Di Giacomo, Peter Eades, Giuseppe Liotta, Henk Meijer, and Fabrizio Montecchiani. Polyline Drawings with Topological Constraints
Session 5B [Approximation Algorithms]
  • Davide Bilò. Almost optimal algorithms for diameter-optimally augmenting trees
  • Giordano Da Lozzo and Ignaz Rutter. Approximation Algorithms for Facial Cycles in Planar Embeddings
  • Adam Kunysz. An Algorithm for the Maximum Weight Strongly Stable Matching Problem
  • Eunpyeong Hong and Mong-Jen Kao. Approximation Algorithm for Vertex Cover with Submodular-Type Covering Constraints
Session 6A [Combinatorial Optimization]
  • David Gleich, Nate Veldt, and Anthony Wirth. Correlation Clustering Generalized
  • Annette Ficker, Thomas Erlebach, Matus Mihalak, and Frits Spieksma. Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm
  • Johannes Blömer, Sascha Brauer, and Kathrin Bujna. Coresets for Fuzzy K-Means with Applications
Session 6B [Online Algorithms]
  • Martin Farach-Colton, Meng Li, and Meng-Tsung Tsai. Streaming Algorithms for Planar Convex Hulls
  • Sébastien Bouchard, Yoann Dieudonne, Andrzej Pelc, and Franck Petit. Deterministic Treasure Hunt in the Plane with Angular Hints
  • Quirijn Bouts, Thom Castermans, Arthur van Goethem, Marc van Kreveld, and Wouter Meulemans. Competitive Searching for a Line on a Line Arrangement
Best Paper Award
  • Andreas Björklund. Exploiting Sparseness for Bipartite Hamiltonicity
Best Student Paper Award
  • Ahad N. Zehmakan. Opinion Forming in Erdős–Rényi Random Graph and Expanders
Session 7A [Computational Geometry]
  • Sariel Har-Peled, Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir, and Max Willert. Stabbing Pairwise Intersecting Disks by Five Points
  • Eunjin Oh. Point Location in Incremental Planar Subdivisions
  • Vahideh Keikha, Mees van de Kerkhof, Marc Van Kreveld, Irina Kostitsyna, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen, and Lionov Wiratma. Convex partial transversals of planar regions
  • Patrick Schnider and Alexander Pilz. Extending the centerpoint theorem to multiple points
Session 7B [Data Structures]
  • Ran Ben Basat, Seungbum Jo, Srinivasa Rao Satti, and Shubham Ugare. Approximate Query Processing over Static Sets and Sliding Windows
  • Parinya Chalermsook, Mayank Goswami, Laszlo Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. Multi-finger binary search trees
  • Ivona Bezakova and Andrew Searns. On Counting Oracles for Path Problems
  • Hiroshi Hirai and Yuni Iwamasa. Reconstructing phylogenetic tree from multipartite quartet system
Session 8A [Computational Geometry]
  • Elena Arseneva, Man Kwun Chiu, Matias Korman, Aleksandar Markovic, Yoshio Okamoto, Aurélien Ooms, André van Renssen, and Marcel Roeloffzen. Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain
  • Eunjin Oh. Minimizing Distance-to-Sight in Polygonal Domains
  • Franz Aurenhammer, Michael Steinkogler, and Rolf Klein. Partially Walking a Polygon
  • Timothy Chan, Thomas C. Van Dijk, Krzysztof Fleszar, Joachim Spoerhase, and Alexander Wolff. Stabbing Rectangles by Line Segments – How Decomposition Reduces the Shallow-Cell Complexity
Session 8B [Online Algorithms]
  • Xingwu Liu, Zhida Pan, Yuyi Wang, and Roger Wattenhofer. Impatient Online Matching
  • Siu-Wing Cheng and Lie Yan. Extensions of Self-Improving Sorters
  • Kelin Luo, Thomas Erlebach, and Yinfeng Xu. Online Scheduling of Car-Sharing Requests between Two Locations with Many Cars and Flexible Advance Bookings
  • Martin Hoefer and Lisa Wilhelmi. Packing Returning Secretaries
Session 9A [Data Structures]
  • Frank Kammer and Andrej Sajenko. A Space-Optimal c-Color Choice Dictionary
  • Ian Munro and Kaiyu Wu. Succinct Data Structures for Chordal Graphs
  • Travis Gagie, Meng He, and Gonzalo Navarro. Tree Path Majority Data Structures
  • Seungbum Jo and Srinivasa Rao Satti. Encoding two-dimensional range top-k queries revisited
Session 9B [Approximation Algorithms]
  • Tomasz Kociumaka, Ritu Kundu, Manal Mohamed, and Solon Pissis. Longest Unbordered Factor in Quasilinear Time
  • Jian-Jia Chen, Nikhil Bansal, Samarjit Chakraborty, and Georg von der Brüggen. Packing Sporadic Real-Time Tasks on Identical Multiprocessor Systems
  • Galia Shabtai, Dan Raz, and Yuval Shavitt. A relaxed FPTAS for Chance-Constrained Knapsack
  • Dimitris Fotakis, Laurent Gourves, Claire Mathieu, and Abhinav Srivastav. Covering Clients with Types and Budgets