ISAAC 2016: The 27th International Symposium on Algorithm and Computation

December 12-14 2016, Darling Harbour, Sydney, Australia

Program

Detailed programs: PDF

Day 0 (11 December 2016)
6:00-7:00 pm Reception/Registration (Barkers Restaurant)
Day 1 (12 December 2016)
8:30-9:00 Registration
9:00-10:00 Invited Talk 1 (Chair: Seokhee Hong) Blackwattle 2 & 3
Compressed and Searchable Indexes for Highly Similar Strings / Kunsoo Park
10:00-10:30 Morning Tea
10:30-11:45 Session 1A: Computational Geometry 1 (Chair: Takeshi Tokuyama) Blackwattle 2 Session 1B: Approximation Algorithm 1 (Chair: Takehiro Ito) Blackwattle 3
Assigning Weights to Minimize the Covering Radius in the Plane / Eunjin Oh and Hee-Kap Ahn The Densest Subgraph Problem with a Convex/Concave Size Function / Yasushi Kawase and Atsushi Miyauchi
On r-Guarding Thin Orthogonal Polygons / Therese Biedl and Saeed Mehrabi Approximate Shortest Distances Among Smooth Obstacles in 3D / Christian Scheffer and Jan Vahrenhold
Search on a Line by Byzantine Robots / Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny and Sunil Shende Additive Approximation Algorithms for Modularity Maximization / Yasushi Kawase, Tomomi Matsui and Atsushi Miyauchi
11:50-1:30 Lunch (Barkers Restaurant)
1:30-3:10 Session 2A: Combinatorial Optimisation (Chair: Osamu Watanabe) Blackwattle 2 Session 2B: Data Structure 1 (Chair: Bernard Mans) Blackwattle 3
Surrogate optimization for $p$-norms / Yasushi Kawase and Kazuhisa Makino All-Pairs Shortest Paths in Unit Disk Graphs in Slightly Subquadratic Time / Timothy Chan and Dimitrios Skrepetos
The Subset Assignment Problem for Data Placement in Caches / Shahram Ghandeharizadeh, Sandy Irani and Jenny Lam Hierarchical Time-Dependent Oracles / Spyros Kontogiannis, Dorothea Wagner and Christos Zaroliagis
Shortest Disjoint ${\cal S}$-paths via Weighted Linear Matroid Parity / Yutaro Yamaguchi Biconnectivity, chain decomposition and st-numbering using O(n) bits / Sankardeep Chakraborty, Venkatesh Raman and Srinivasa Rao Satti
Scaling and Proximity Properties of Integrally Convex Functions / Satoko Moriguchi, Kazuo Murota, Akihisa Tamura and Fabio Tardella Streaming Verification of Graph Properties / Amirali Abdullah, Samira Daruki, Chitradeep Dutta Roy and Suresh Venkatasubramanian
3:10-3:40 Afternoon Tea
3:40-4:55 Session 3A: Graph Algorithm 1 (Chair: Bernard Mans) Blackwattle 2 Session 3B: Approximation Algorithm 2 (Chair: Siu-Wing Cheng) Blackwattle 3
Finding $k$ Simple Shortest Paths and Cycles / Udit Agarwal and Vijaya Ramachandran An Efficient Algorithm for Placing Electric Vehicle Charging Stations / Pankaj Agarwal, Jiangwei Pan and Will Victor
A Sidetrack-Based Algorithm for Finding the k Shortest Simple Paths in a Directed Graph / Denis Kurz and Petra Mutzel Approximating Smallest Containers for Packing Three-dimensional Convex Objects / Helmut Alt and Nadja Scharf
A Linear-time Algorithm for Integral Multiterminal Flows in Trees / Mingyu Xiao and Hiroshi Nagamochi O(f) Bi-approximation for Capacitated Covering with Hard Capacities / Mong-Jen Kao, Hai-Lun Tu and D.T. Lee
Day 2 (13 December 2016)
9:00-10:00 Invited Talk 2 (Chair: Peter Eades) Blackwattle 2 & 3
Towards Processing of Big Graphs: from Theory, Algorithm to System / Xuemin Lin
10:00-10:30 Morning Tea
10:30-11:45 Session 4A: Computational Geometry 2 (Chair: Siu-Wing Cheng) Blackwattle 2 Session 4B: Approximation Algorithm 3 (Chair: Yushi Uno) Blackwattle 3
Packing Short Plane Spanning Trees in Complete Geometric Graphs / Oswin Aichholzer, Thomas Hackl, Matias Korman, Alexander Pilz, Günter Rote, André van Renssen, Marcel Roeloffzen and Birgit Vogtenhuber On (1,\epsilon)-Restricted Max-Min Fair Allocation Problem / T-H. Hubert Chan, Zhihao Gavin Tang and Xiaowei Wu
A Refined Definition for Groups of Moving Entities and its Computation / Marc Van Kreveld, Maarten Löffler, Lionov Wiratma and Frank Staals Approximation Algorithms for Capacitated $k$-Travelling Repairmen Problems / Christopher Martin and Mohammad Salavatipour
Space-Efficient Plane-Sweep Algorithms / Amr Elmasry and Frank Kammer Fast Approximation Algorithms for the Generalized Survivable Network Design Problem / Andreas Emil Feldmann, Jochen Koenemann, Kanstantsin Pashkovich and Laura Sanita
11:50-1:30 Lunch (Barkers Restaurant)
1:30-3:10 Session 5A: FPT Algorithm (Chair: Serge Gaspers) Blackwattle 2 Session 5B: Graph Algorithm 2 (Chair: Hsu-Chun Yen) Blackwattle 3
Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity / Hans L. Bodlaender, Hirotaka Ono and Yota Otachi Clustered Planarity with Pipes / Patrizio Angelini and Giordano Da Lozzo
Kernels for Deletion to Classes of Acyclic Digraphs / Akanksha Agrawal, Saket Saurabh, Roohani Sharma and Meirav Zehavi Sliding tokens on a cactus / Duc Hoang and Ryuhei Uehara
Linear Kernels and Linear-Time Algorithms for Finding Large Cuts / Michael Etscheid and Matthias Mnich A Near-Optimal Algorithm for Finding an Optimal Shortcut of a Tree / Eunjin Oh and Hee-Kap Ahn
Simultaneous Feedback Edge Set: A Parameterized Perspective / Akanksha Agrawal, Fahad Panolan, Saket Saurabh and Meirav Zehavi Sink Evacuation on Trees with Dynamic Confluent Flows / Di Chen and Mordecai Golin
3:10-3:40 Afternoon Tea
3:40-4:55 Session 6A: Computational Geometry 3 (Chair: Takeshi Tokuyama) Blackwattle 2 Session 6B: Data Structure 2 (Chair: Rudolf Fleischer) Blackwattle 3
Towards Plane Spanners of Degree 3 / Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, Anil Maheshwari and Michiel Smid On the Optimality of Tape Merge of Two Lists with Similar Size / Qian Li, Xiaoming Sun and Jialin Zhang
Dispersing Points on Intervals / Shimin Li and Haitao Wang Raising Permutations to Powers In Place / Hicham El-Zein, Ian Munro and Matthew Robertson
$L_1$ Geodesic Farthest Neighbors in a Simple Polygon and Related Problems / Sang Won Bae Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap / Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat and Riva Shalom
6:00-9:00 Conference Dinner: Dockside, Cockle Bay Wharf, Balcony level (Darling Rooms 1 & 2, Quay Rooms 1)
Day 3 (14 December 2016)
9:00-10:00 Best Paper Award / ISAAC 2017 Presentation (Chair: Seokhee Hong) Blackwattle 2 & 3
Optimal Composition Ordering Problems for Piecewise Linear Functions / Yasushi Kawase, Kazuhisa Makino and Kento Seimi
Adaptivity vs Postselection, and Hardness Amplification in Polynomial Approximation / Lijie Chen
ISAAC 2017 Presentation / Takeshi Tokuyama
10:00-10:30 Morning Tea
10:30-11:45 Session 7A: Computational Geometry 4 (Chair: Rudolf FLeischer) Blackwattle 2 Session 7B: Graph Algorithm 3 (Chair: Takehiro Ito) Blackwattle 3
The (1|1)-Centroid Problem on the Plane Concerning Distance Constraints / Hung-I Yu, Tien-Ching Lin and D. T. Lee On the Classes of Interval Graphs of Limited Nesting and Count of Lengths / Pavel Klavík, Yota Otachi and Jiri Sejnoha
Universal Guard Problems / Sándor Fekete, Qian Li, Joseph Mitchell and Christian Scheffer Bipartite Matching with Linear Edge Weights / Nevzat Onur Domanic, Chi-Kit Lam and C. Gregory Plaxton
Reconstruction of Weakly Simple Polygons from their Edges/ Hugo Akitaya and Csaba Toth On the complexity of Matching Cut in graphs of fixed diameter / Hoang-Oanh Le and Van Bang Le
11:50-1:30 Lunch (Barkers Restaurant)
1:30-3:10 Session 8A: Computational Complexity (Chair: Serge Gaspers) Blackwattle 2 Session 8B: Pattern Matching/String Algorithm (Chair: Kunsoo Park) Blackwattle 3
A Gap Trichotomy for Boolean constraint problems: extending Schaefer's Theorem / Lucy Ham Pattern Matching and Consensus Problems on Weighted Sequences and Profiles / • Tomasz Kociumaka, Solon Pissis and Jakub Radoszewski
Complexity of distributions and average-case hardness / Dmitry Itsykson, Alexander Knop and Dmitry Sokolov Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation / Philip Bille, Patrick Hagge Cording, Inge Li Gørtz, Frederik Rye Skjoldjensen, Hjalte Wedel Vildhøj and Søren Vind
An Improved Tax Scheme for Selfish Routing / Te-Li Wang, Chih-Kuan Yeh and Ho-Lin Chen Space-Time Trade-offs for the Shortest Unique Substring Problem / Arnab Ganguly, Wing-Kai Hon, Rahul Shah and Sharma V. Thankachan
Hard Communication Channels for Steganography / Sebastian Berndt and Maciej Liskiewicz Computing the Pattern Waiting Time: A Revisit of the Intuitive Approach / Kai Jin
3:10-3:40 Afternoon Tea
3:40-4:55 Session 9A: Scheduling Algorithm (Chair: Kazuhisa Makino) Blackwattle 2 Session 9B: Approximation Algorithm 4 (Chair: Hsu-Chun Yen) Blackwattle 3
Optimal Nonpreemptive Scheduling in a Smart Grid Model / Fu-Hong Liu, Hsiang-Hsuan Liu and Prudence W.H. Wong Building Clusters with Lower-bounded Sizes / Faisal Abu-Khzam, Cristina Bazgan, Katrin Casel and Henning Fernau
Online Packet Scheduling with Bounded Delay and Lookahead / Martin Böhm, Marek Chrobak, Łukasz Jeż, Fei Li, Jiří Sgall and Pavel Veselý Approximate Clustering via Metric Partitioning / Sayan Bandyapadhyay and Kasturi Varadarajan
Single machine scheduling with jobdependent machine deterioration / Wenchang Luo, Yao Xu, Weitian Tong and Guohui Lin Distributed and Robust Support Vector Machine / Yangwei Liu, Hu Ding, Ziyun Huang and Jinhui Xu