Conference Program

Venue: LT-401, City University of Hong Kong.
Each talk in Session 1 to 7 will be given 12 minutes with 3 minutes Q and A.
Each talk in Session 8 will be given 10 minutes with 2 minutes Q and A.

[Reception & Lunch Venue]
City Top, Staff Lounge, 9th Floor Amenities Building, Lift No. 19 or 20 (L19 or L20)
City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR

[Banquet Venue]
Hung Kee Seafood Restaurant, Shop 6 & 9-10, G/F, Siu Yat Building, Sai Kung Hoi Pong Square, Sai Kung.

Day 1 (December 16, 2016)

Sessions/Chairs/TimeTitles of Talks / Speakers and Authors
Registration08:00 - 09:00
Opening 09:00 - 09:15
Keynote09:15 - 10:15Naoki Katoh (Kwansei Gakuin University)
Coffee Break10:15 - 10:30
Session 1 Graph Theory I (Chair: Boting Yang)10:30 - 10:45On the Capture Time of Cops and Robbers Game on a Planar Graph
Photchchara Pisantechakool, Xuehou Tan
10:45 - 11:00The Mixed Evacuation Problem
Yosuke Hanawa, Yuya Higashikawa, Naoyuki Kamiyama, Naoki Katoh, Atsushi Takizawa
11:00 - 11:15A Comprehensive Reachability Evaluation for Airline Networks with Multi-Constraints
Xiaotian You, Xiaofeng Gao, Yaru Dang, Guihai Chen
11:15 - 11:30Algorithmic Aspects of Disjunctive Total Domination in Graphs
Chin-Fu Lin, Sheng-Lung Peng
11:30 - 11:45On Strong Tree-Breadth
Arne Leitert, Feodor F. Dragan
11:45 - 12:00Computing a tree having a small vertex cover
Takuro Fukunaga, Takanori Maehara
Lunch12:00 - 13:30
Session 2 Geometric Optimization (Chair: Vincent Chau)13:30 - 13:45Performing Multicut on Walkable Environments
Arne Hillebrand, Marjan van den Akker, Roland Geraerts, Han Hoogeveen
13:45 - 14:00The Mixed Center Location Problem
Yi Xu, Jigen Peng, Yinfeng Xu
14:00 - 14:15Constrained Light Deployment for Reducing Energy Consumption in Buildings
Huamei Tian, Kui Wu, Sue Whitesides, Cuiying Feng
14:15 - 14:30On the 2-Center Problem Under Convex Polyhedral Distance Function
Sergey Bereg
14:30 - 14:45Algorithms for Colourful Simplicial Depth and Medians in the Plane
Olga Zasenko, Tamon Stephen
14:45 - 15:00 Minimum Eccentricity Shortest Path Problem: an Approximation Algorithm and Relation with the k-Laminarity Problem
Étienne Birmelé, Fabien de Montgolfier, Léo Planche
15:00 - 15:15A Quadratic Time Exact Algorithm for Continuous Connected 2-Facility Location Problem in Trees
Wei Ding, Ke Qiu
Group Photo15:15 - 15:30
Coffee Break15:30 - 15:45
Session 3 Graph Theory II (Chair: Qianping Gu)15:45 - 16:00Instance Guaranteed Ratio on Greedy Heuristic for Genome Scaffolding
Clément Dallard, Mathias Weller, Annie Chateau, Rodolphe Giroudeau
16:00 - 16:15Improved Precise Fault Diagnosis Algorithm for Hypercube-Like Graphs
Tai-Ling Ye, Dun-Wei Cheng, Sun-Yuan Hsieh
16:15 - 16:30An introduction to coding sequences of graphs
Shamik Ghosh, Raibatak Sen Gupta, M. K. Sen
16:30 - 16:45Total Dual Integrality of Triangle Covering
Xujin Chen, Zhuo Diao, Xiaodong Hu, Zhongzheng Tang
16:45 - 17:00Time-optimal broadcasting of multiple messages in 1-in port model
Petr Gregor, Riste Škrekovski, Vida Vukašinović
17:00 - 17:15Fast Searching on Complete k-partite Graphs
Yuan Xue, Boting Yang, Farong Zhong, Sandra Zilles
17:15 - 17:30Cliques in Regular Graphs and the Core-Periphery Problem in Social Networks
Ulrik Brandes, Eugenia Holm, Andreas Karrenbauer
17:30 - 17:45Constant Factor Approximation for the Weighted Partial Degree Bounded Edge Packing Problem
Pawan Aurora, Monalisa Jena, Rajiv Raman
17:45 - 17:57A Polynomial Time Solution for Permutation Scaffold Filling
Nan Liu, Peng Zou, Binhai Zhu

Day 2 (December 17, 2016)

Sessions/Chairs/TimeTitles of Talks / Speakers and Authors
Keynote09:00 - 10:00Kirk Pruhs (University of Pittsburgh)
Coffee Break10:00 - 10:15
Session 4 Complexity and Data Structure (Chair: Yixin Cao)10:15 - 10:30On the (parameterized) complexity of recognizing well-covered (r,l)-graphs
Sancrey Alves, Konrad K. Dabrowski, Luerbio Faria, Sulamita Klein, Ignasi Sau, Ueverton Souza
10:30 - 10:45Algorithmic Analysis for Ridesharing of Personal Vehicles
Qianping Gu, Jiajian Liang, Guochuan Zhang
10:45 - 11:00On the Complexity of Bounded Deletion Propagation
Dongjing Miao, Yingshu Li, Xianmin Liu, Jianzhong Li
11:00 - 11:15On Residual Approximation in Solution Extension Problems
Mathias Weller, Annie Chateau, Rodolphe Giroudeau, Jean-Claude König, Valentin Pollet
11:15 - 11:30On the Parameterized Parallel Complexity and the Vertex Cover Problem
Faisal Abu-Khzam, Shouwei Li, Christine Markarian, Friedhelm Meyer auf der Heide, Pavel Podlipyan
11:30 - 11:45A Linear Potential Function for Pairing Heaps
John Iacono, Mark Yagnatinsky
11:45 - 12:00Amortized Efficiency of Ranking and Unranking Left-Child Sequences in Lexicographic Order
Kung-jui Pai, Ro-yu Wu, Jou-ming Chang, Shun-chieh Chang
Lunch12:00 - 13:30
Session 5 Graph Theory III (Chair: Xiaowei Wu)13:30 - 13:45Finding Disjoint Paths on Edge-Colored Graphs: A Multivariate Complexity Analysis
Riccardo Dondi, Florian Sikora
13:45 - 14:00Realizability of Graphs as Triangle Cover Contact Graphs
Shaheena Sultana, Md Saidur Rahman
14:00 - 14:15On the Complexity of Extracting Subtree with Keeping Distinguishability
Xianmin Liu, Zhipeng Cai, Dongjing Miao, Jianzhong Li
14:15 - 14:30Safe Sets in Graphs: Graph Classes and Structural Parameters
Raquel Águeda, Nathann Cohen, Shinya Fujita, Sylvain Legay, Yannis Manoussakis, Yasuko Matsui, Leandro Montero, Reza Naserasr, Yota Otachi, Tadashi Sakuma, Zsolt Tuza, Renyu Xu
14:30 - 14:45On local structures of cubicity 2 graphs
Sujoy Bhore, Dibyayan Chakraborty, Sandip Das, Sagnik Sen
14:45 - 15:00Approximability of the distance independent set problem on regular graphs and planar graphs
Hiroshi Eto, Takehiro Ito, Zhilong Liu, Eiji Miyano
15:00 - 15:15Approximation and Hardness Results for the Max k-Uncut Problem
Peng Zhang, Chenchen Wu, Dachuan Xu, Xinghe Zhang
15:15 - 15:30On the Approximability of Partial VC Dimension
Cristina Bazgan, Florent Foucaud, Florian Sikora
Coffee Break15:30 - 15:45
Session 6 Combinatorial Optimization (Chair: Sheung-Hung Poon)15:45 - 16:00Optimal Speed Scaling with a Solar Cell
Neal Barcelo, Peter Kling, Michael Nugent, Kirk Pruhs
16:00 - 16:15An approximation algorithm for the k-median problem with uniform penalties via pseudo-solution
Chenchen Wu, Donglei Du, Dachuan Xu
16:15 - 16:30On-line Pattern Matching on Uncertain Sequences & Applications
Carl Barton, Chang Liu, Solon Pissis
16:30 - 16:45Scheduling with Interjob Communication on Parallel Processors
Jürgen König, Alexander Mäcker, Friedhelm Meyer auf der Heide, Sören Riechers
16:45 - 17:00Cost-efficient Scheduling on Machines from the Cloud
Alexander Mäcker, Manuel Malatyali, Friedhelm Meyer auf der Heide, Sören Riechers
17:00 - 17:15Strategic Online Facility Location
Maximilian Drees, Björn Feldkord, Alexander Skopalik
17:15 - 17:30An Efficient PTAS for Parallel Machine Scheduling with Capacity Constraints
Lin Chen, Klaus Jansen, Guochuan Zhang, Wenchang Luo
17:30 - 17:45A Pseudo-Polynomial Time Algorithm for Solving the Knapsack Problem in Polynomial Space
Noriyuki Fujimoto
Coach Pickup at University Circle17:45 - 17:50
Banquet18:45 - 20:45

Day 3 (December 18, 2016)

Sessions/Chairs/TimeTitles of Talks / Speakers and Authors
Session 7 Games
(Chair: Zhenhua Duan)
08:30 - 08:45An incentive mechanism for selfish bin covering
Weian Li, Qizhi Fang, Wenjing Liu
08:45 - 09:00Congestion Games with Mixed Objectives
Matthias Feldotto, Lennart Leder, Alexander Skopalik
09:00 - 09:15An Optimal Strategy for Static Black-Peg Mastermind With Two Pegs
Gerold Jäger
Coffee Break09:15 - 09:30
Session 8 Miscellaneous
(Chair: Hubert Chan)
09:30 - 09:42The Incentive Ratio in Exchange Economies
Ido Polak
09:42 - 09:54w-Centroids and least (w,l)-central subtrees
Erfang Shan, Liying Kang
09:54 - 10:06Solving Dynamic Vehicle Routing Problem with Soft Time Window by improved LNS and hybrid PSO
Xiaohan He, Xiaoli Zeng, Liang Song, Hejiao Huang, Hongwei Du
10:06 - 10:18Convex Independence in Permutation Graphs
Wing-Kai Hon, Ton Kloks, Fu-Hong Liu, Hsiang-Hsuan Liu
10:18 - 10:30The Connected $p$-Center Problem on Cactus Graphs
Chunsong Bai, Liying Kang, Erfang Shan
10:30 - 10:42Comparison of Quadratic Convex Reformulations to solve the Quadratic Assignment Problem
sourour elloumi, Amélie Lambert
10:42 - 10:54Using Unified Model Checking to Verify Heaps
Xu Lu, Zhenhua Duan, Cong Tian
10:54 - 11:06A Filtering Heuristic for the Computation of Minimum-Volume Enclosing Ellipsoids
Linus Källberg, Thomas Larsson
11:06 - 11:18Relaxations of discrete sets with semicontinuous variables
Gustavo Angulo
11:18 - 11:30Unfolding the Core Structure of the Reciprocal Graph of a Massive Online Social Network
Braulio Dumba, Zhi-Li Zhang
11:30 - 11:42Tackling Common Due Window Problem With a Two-layered Approach
Abhishek Awasthi, Jörg Lässig, Thomas Weise, Oliver Kramer
Closing11:42 - 11:48

Free access to the proceeding: