Program & Venue

The conference will be held in the lecture theatres CPD-304 (Invited talks), CPD-328 (Session A) and CPD-329 (Session B) on the 3rd floor of the Jockey Club Tower in the main campus of the University of Hong Kong (http://www.maps.hku.hk). Registration will start at 7:50am on December 16 (Monday) outside the lecture theatres.

 

  Parallel Session A (Venue: CPD-328) Parallel Session B (Venue: CPD-329)
Day 1 (December 16)
9:00 - 10:00 Invited talk
Chair: Takeshi Tokuyama
Moni Naor, Cryptography and Data Structures: A Match Made in Heaven (Venue: CPD-304)
10:30 - 11:50 Session 1 Computational Geometry I
Chair: Hee-Kap Ahn
Pattern Matching
Chair: Kunihiko Sadakane
  Oswin Aichholzer, Thomas Hackl, Matias Korman, Alexander Pilz and Birgit Vogtenhuber. Geodesic-Preserving Polygon Simplification Amihood Amir and Benny Porat. Pattern Matching with non Overlapping Reversals - Approximation and On-line Algorithms
Jinhee Chun, Ricardo Gonzalo and Takeshi Tokuyama. Space-efficient and data-sensitive polygon reconstruction algorithms from visibility angle information Djamal Belazzougui, Adeline Pierrot, Mathieu Raffinot and Stéphane Vialette. Single and multiple consecutive permutation motif search
Sergey Bereg, Seok-Hee Hong, Naoki Katoh, Sheung-Hung Poon and Shin-Ichi Tanigawa. On the Edge Crossing Properties of Euclidean Minimum Weight Laman Graphs Pawel Gawrychowski and Damian Straszak. Beating O(nm) in approximate LZW-compressed pattern matching
Franz Aurenhammer and Gernot Walzl. Structure and computation of straight skeletons in 3-space Sharma V. Thankachan, J. Ian Munro, Venkatesh Raman and Moshe Lewenstein. Less Space: Indexing for Queries with Wildcards
14:00 - 15:00 Session 2 Computational Complexity I
Chair: Kazuhisa Makino
Internet & Soical Network Algorithms I
Chair: Hubert Chan
  Qi Cheng, Jincheng Zhuang and Jiyou Li. On Determing Deep Holes of Generalized Reed-Solomon Codes Matthew Johnson, Daniel Paulusma and Erik Jan van Leeuwen. Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs
Yota Otachi and Pascal Schweitzer. Isomorphism on subgraph-closed graph classes: a complexity dichotomy and intermediate graph classes Marc Lelarge and Hang Zhou. Sublinear-Time Algorithms for Monomer-Dimer Systems on Bounded Degree Graphs
Youming Qiao, Xiaoming Sun and Nengkun Yu. Determinantal complexities and field extensions Robert Bredereck, Sepp Hartung, André Nichterlein and Gerhard Woeginger. The complexity of finding a large subgraph under anonymity constraints
15:30 - 16:50 Session 3 Graph Theory & Algorithms I
Chair: Seokhee Hong
Scheduling Algorithms
Chair: Tak-Wah Lam
  Otfried Cheong, Sariel Har-Peled, Heuna Kim and Hyo-Sil Kim. On the Number of Edges of Fan-Crossing Free Graphs Michael Etscheid. Performance Guarantees for Scheduling Algorithms under Perturbed Machine Speeds
Tomáš Gavenčiak, Vít Jelínek, Pavel Klavík and Jan Kratochvíl. Cops and Robbers on Intersection Graphs Jun Kawahara, Koji M. Kobayashi and Shuichi Miyazaki. Better Bounds for Online $k$-Frame Throughput Maximization in Network Switches
Patrizio Angelini, William Evans, Fabrizio Frati and Joachim Gudmundsson. SEFE with No Mapping via Large Induced Outerplane Graphs in Plane Graphs Samuel Walker and Yakov Zinder. The Solvable Cases of a Scheduling Algorithm
Mourad Baiou, Laurent Beaudou, Zhentao Li and Vincent Limouzy. Hardness and algorithms for variants of line graphs of directed graphs  
     
Day 2 (December 17)
9:00 - 10:00 Invited talk
Chair: Francis Chin
S Muthukrishnan, Market Approach to Social Ads: The MyLikes Example and Related Problems (Venue: CPD-304)
10:30 - 11:50 Session 4 Computational Complexity II
Chair: Chung-Keung Poon
Computational Geometry II
Chair: Antoine Vigneron
  Martin Farach-Colton and Meng-Tsung Tsai. Exact Sublinear Binomial Sampling Kyle Klein and Subhash Suri. Pursuit Evasion on Polyhedral Surfaces
Dominik Scheder. Trivial, Tractable, Hard. A Not So Sudden Complexity Jump in Neighborhood Restricted CNF Formulas Wolfgang Mulzer and Yannik Stein. Algorithms for Tolerated Tverberg Partitions
Kevin Buchin and Dirk H.P. Gerrits. Dynamic point labeling is strongly PSPACE-complete Cecilia Bohler and Rolf Klein. Abstract Voronoi Diagrams with Disconnected Regions
Dominik Scheder. Unsatisfiable CNF Formulas Contain Many Conflicts Ferran Hurtado, Maarten Löffler, Ines Matos, Vera Sacristan, Maria Saumell, Rodrigo Silveira and Frank Staals. Terrain visibility with multiple viewpoints
14:00 - 15:00 Session 5 Graph Theory & Algorithms II
Chair: Prudence Wong
Fixed-Parameter Tractable Algorithms
Chair: Leizhen Cai
  Mingyu Xiao and Hiroshi Nagamochi. Exact Algorithms for Maximum Independent Set Jiehua Chen, Christian Komusiewicz, Rolf Niedermeier, Manuel Sorge, Ondrej Suchy and Mathias Weller. Effective and Efficient Data Reduction for the Minimum Topic-Connected Overlay Problem
Arnaud Mary, Mamadou Moustapha Kanté, Nourine Lhouari, Vincent Limouzy and Uno Takeaki. On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs René Van Bevern, Michael R. Fellows, Serge Gaspers and Frances A. Rosamond. Myhill-Nerode Methods for Hypergraphs
Patrizio Angelini, Thomas Bläsius and Ignaz Rutter. Testing Mutual Duality of Planar Graphs Fabrizio Frati, Serge Gaspers, Joachim Gudmundsson and Luke Mathieson. Augmenting Graphs to Minimize the Diameter
15:30 - 16:30 Session 6 Algorithms & Data Structures I
Chair: Kunihiko Sadakane
Internet & Soical Network Algorithms II
Chair: Hubert Chan
  Gonzalo Navarro and Sharma V. Thankachan. Top-k Document Retrieval in Compact Space and Near-Optimal Time Leo Speidel and Konstantinos Panagiotou. Asynchronous Rumor Spreading on Random Graphs
Timothy Chan, Ian Munro and Venkatesh Raman. Faster, space efficient selection algorithms in read-only memory for integers Yasushi Kawase, Xin Han and Kazuhisa Makino. Unit Cost Buyback Problem
Andreas Gemsa, Benjamin Niedermann and Martin Nöllenburg. Trajectory-Based Dynamic Map Labeling Konstantinos Panagiotou, Ali Pourmiri and Thomas Sauerwald. Faster Rumor Spreading with Multiple Calls
18:00 - 20:00 Conference banquet at the Victoria Harbour restaurant, the Westwood
     
Day 3 (December 18)
9:00 - 10:00 Session 7 Algorithmic Game Theory
Chair: Minming Li
Algorithms & Data Structures II
Chair: Wing-Kai Hon
  Akiyoshi Shioura, Kazuo Murota and Zaifu Yang. Computing a Walrasian Equilibrium in Iterative Auctions with Multiple Differentiated Items Lars Arge and Mikkel Thorup. RAM-Efficient External Memory Sorting
Søren Kristoffer Stiil Frederiksen and Peter Bro Miltersen. Approximating the value of a concurrent reachability game in the polynomial time hierarchy Moshe Lewenstein, Ian Munro and Venkatesh Raman. Succinct data structures for representing equivalence classes
Xiangzhong Xiang. New Results on the Online Pricing Problem Eylon Yogev and Moni Naor. Sliding Bloom Filters
10:30 - 11:50 Session 8 Graph Theory & Algorithms III
Chair: Ming-Yang Kao
Approximation Algorithms I
Chair: Lap-Chi Lau
  Greg Plaxton. Vertex-Weighted Matching in Two-Directional Orthogonal Ray Graphs Marek Karpinski, Michael Lampis and Richard Schmied. New Inapproximability Bounds for TSP
Martin Balko, Pavel Klavík and Yota Otachi. Bounded Representations of Interval and Proper Interval Graphs Bodo Manthey and Rianne Veenstra. Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise
Peter Floderus, Miroslaw Kowaluk, Andrzej Lingas and Eva-Marta Lundell. Detecting and Counting Small Pattern Graphs Chenglin Fan, Jun Luo and Binhai Zhu. Tight Approximation Bounds for Connectivity with a Color-Spanning Set
Min Chih Lin, Michel J. Mizrahi and Jayme L. Szwarcfiter. An O(1.1939n) time algorithm for minimum weighted dominating induced matching Jing Chen, Xin Han and Kazuo Iwama. The Train Delivery Problem Revisited
14:00 - 15:00 Session 9 Computational Geometry III
Chair: Antoine Vigneron
Approximation Algorithms II
Chair: Lap-Chi Lau
  Robert Fraser, Meng He, Akitoshi Kawamura, Alejandro Lopez-Ortiz, J. Ian Munro and Patrick K. Nicholson. The Distance 4-Sector of Two Points is Unique Pegah Kamousi and Subhash Suri. Euclidean Traveling Salesman Tours through Stochastic Neighborhoods
Takashi Horiyama and Wataru Shoji. The Number of Different Unfoldings of Polyhedra Pan Peng and Angsheng Li. Detecting and Characterizing Small Dense Bipartite-like Subgraphs by the Bipartiteness Ratio Measure
Payam Khanteimouri, Ali Mohades, Mohammad Ali Abam and Mohammad Reza Kazemi. Computing the Smallest Color-Spanning Axes-Parallel Square Sharathkumar R and Michael Kerber. Approximate \v{C}ech complexes in low and high dimensions
15:30 - 16:30 Session 10 Computational Complexity III
Chair: Siu-Wing Cheng
Network Algorithms
Chair: Hing-Fung Ting
  Friedrich Slivovsky and Stefan Szeider. Model Counting for Formulas of Bounded Boolean-Width Haitao Wang. Minmax Regret 1-Facility Location on Uncertain Path Networks
Yen-Wei Wu, Wei-Yin Lin, Hung-Lung Wang and Kun-Mao Chao. Computing Plurality Points and Condorcet Points in Euclidean Space Aparna Das, Krzysztof Fleszar, Stephen Kobourov, Joachim Spoerhase, Sankar Veeramoni and Alexander Wolff. Approximating the Generalized Minimum Manhattan Network Problem
Aleck Johnsen, Ming-Yang Kao and Shinnosuke Seki. Computing Minimum Tile Sets to Self-Assemble Colors Patterns Luc Devroye and Xing Shi Cai. A Probabilistic Analysis of Kademlia Networks