Conference Program Detailed Booklet

COCOA 2017 Registration Day (December 15th, 2017)
14:00 - 18:00 Registration (Lobby, 1F)
COCOA 2017 Conference Day 1 (December 16th, 2017)
8:30 - 18:00 Registration (Lobby, 1F)
8:45 - 09:00 Opening Ceremony
Prof. Minyi Guo, Prof. Guihai Chen
9:00 - 09:30 Photo
9:30 - 10:30 Keynote Speech: Narrowing (Already) Small Complexity Gaps
Speaker: Dr. Kazuo Iwama (Kyoto University, Japan)
Chair: Xiwen Lu
10:30 - 10:50 Coffee Break
10:50 - 12:30 Session 1: Game Theory
Chair: Thomas Erlebach
12:30 - 13:40 Lunch
13:40 - 15:20 Session 2: Graph Theory
Chair: Xiao Zhou
Session 3: Combinatorial Optimization
Chair: Guochuan Zhang
(PEONY, 牡丹厅, 4F)
15:20 - 15:50 Coffee Break
15:50 - 17:50 Session 4: Approximation Algorithm
Chair: Michael Khachay
Session 5: Combinatorial Optimization
Chair: Viet Hung Nguyen
(PEONY, 牡丹厅, 4F)
18:20 Banquet
COCOA 2017 Conference Day 2 (December 17th, 2017)
9:00 - 10:00 Keynote Speech: Maximization of Multi-Factor Influence
Speaker: Dr. Ding-Zhu Du (University of Texas at Dallas, USA)
Chair: Dachuan Xu
10:00 - 10:20 Coffee Break
10:20 - 11:20 Keynote Speech: A Non-Asymptotic Approach to Analyze Kidney Exchange Graphs
Speaker: Dr. Simai He (Shanghai University of Finance and Economics, China)
Chair: Xianmin Liu
11:20 - 12:30 Lunch
12:30 - 14:10 Session 6: Combinatorial Optimization
Chair: Alireza Zarei
Session 7: Application
Chair: Ugo Vaccaro
(PEONY, 牡丹厅, 4F)
14:10 - 14:30 Coffee Break
14:30 - 16:30 Session 8: Network
Chair: Neeraj Mittal
Session 9: Graph Theory
Chair: Qianping Gu
(PEONY, 牡丹厅, 4F)
17:00 - Cruise Buffet (Huangpu River)
(Assemble in Jianguo Hotel Lobby at 17:00)
Sponsor: Cardinal Operations
COCOA 2017 Conference Day 3 (December 18th, 2017)
09:00 - 10:40 Session 10: Combinatorial Optimization
Chair: Yannis Manoussakis
Session 11: Application
Chair: Francis Y.L. Chin
(PEONY, 牡丹厅, 4F)
10:40 - 11:00 Coffee Break
11:00 - 12:20 Session 12: Demo and Application (Fast Track)
Chair: Xiaofei Liu
Session 13: Demo and Application (Fast Track)
Chair: Boting Yang
(PEONY, 牡丹厅, 4F)
12:20 - 14:00 Lunch
14:00 - 18:00 Workshop: Network Computing and its Application
Chair: Yuan Luo
(PEONY, 牡丹厅, 4F)
Session 1 Game Theory, Chair: Thomas Erlebach (100 Minutes 5 Papers)
  1. An Improved Mechanism for Selfish Bin Packing
    Xin Chen, Qingqin Nong and Qizhi Fang
  2. Cost-Sharing Mechanisms for Selfish Bin Packing
    Chenhao Zhang and Guochuan Zhang
  3. The Eigen-Distribution of Weighted Game Trees
    Shohei Okisaka, Weiguang Peng, Wenjuan Li and Kazuyuki Tanaka
  4. The Price of Anarchy in Two-Stage Scheduling Games
    Deshi Ye, Lin Chen and Guochuan Zhang
  5. Selfish Jobs with Favorite Machines: Price of Anarchy vs Strong Price of Anarchy
    Cong Chen, Paolo Penna and Yinfeng Xu
Session 2 Graph Theory, Chair: Xiao Zhou (100 Minutes 5 Papers)
  1. Complexity and Online Algorithms for Minimum Skyline Coloring of Intervals
    Thomas Erlebach, Fu-Hong Liu, Hsiang-Hsuan Liu, Mordechai Shalom, Prudence W.H. Wong and Shmuel Zaks
  2. Listing Acyclic Subgraphs and Subgraphs of Bounded Girth in Directed Graphs
    Alessio Conte, Kurita Kazuhiro, Kunihiro Wasa and Takeaki Uno
  3. The Cop Number of the One-Cop-Moves Game on Planar Graphs
    Ziyuan Gao and Boting Yang
  4. The Spectral Radius and Domination Number of Uniform Hypergraphs
    Liying Kang, Wei Zhang and Erfang Shan
  5. The 2-Median Problem on Cactus Graphs with Positive and Negative Weights
    Bai Chunsong and Kang Liying
Session 3 Combinatorial Optimization, Chair: Guochuan Zhang (100 Minutes 5 Papers)
  1. Generalized pyramidal tours for the Generalized Traveling Salesman Problem
    Michael Khachay and Katherine Neznakhina
  2. Improved Branching Algorithm for \((n,3)\)-MaxSAT Based on Refined Observations
    Wenjun Li, Jianxin Wang, Chao Xu and Yongjie Yang
  3. New Insights for Power Edge Set Problem
    Benoit Darties, Annie Chateau, Rodolphe Giroudeau and Mathias Weller
  4. On the Complexity of Detecting \(k\)-Length Negative Cost Cycles
    Longkun Guo and Peng Li
  5. An Efficient Primal-Dual Algorithm for Fair Combinatorial Optimization Problems
    Viet Hung Nguyen and Paul Weng
Session 4 Approximation Algorithm, Chair: Michael Khachay (120 Minutes 6 Papers)
  1. Approximation Algorithms for Maximum Coverage with Group Budget Constraints
    Longkun Guo, Min Li and Dachuan Xu
  2. A Spectral Partitioning Algorithm for Maximum Directed Cut Problem
    Zhenning Zhang, Donglei Du, Chenchen Wu, Dachuan Xu and Dongmei Zhang
  3. Approximating \(k\)-Forest with Resource Augmentation: A Primal-Dual Approach
    Eric Angel, Kim Thang Nguyen and Shikha Singh
  4. Better Approximation Ratios for the Single-Vehicle Scheduling Problems on Tree/Cycle Networks
    Yuanxiao Wu and Xiwen Lu
  5. Parameterized Approximation Algorithms for Some Location Problems in Graphs
    Arne Leitert and Feodor Dragan
  6. Efficient Algorithms for Ridesharing of Personal Vehicles
    Qianping Gu, Leo Jiajian Liang and Guochuan Zhang
Session 5 Combinatorial Optimization, Chair: Viet Hung Nguyen (120 Minutes 6 Papers)
  1. A New Graph Parameter to Measure Linearity
    Pierre Charbit, Michel Habib, Lalla Mouatadid and Reza Naserasr
  2. Faster and Enhanced Inclusion-Minimal Cograph Completion
    Christophe Crespelle, Daniel Lokshtanov, Thi Ha Duong Phan and Eric Thierry
  3. Graph Editing to a Given Neighbourhood Degree List is Fixed-Parameter Tractable
    Naomi Nishimura and Vijay Subramanya
  4. Lexico-Minimum Replica Placement in Multitrees
    K. Alex Mills, R. Chandrasekaran and Neeraj Mittal
  5. Structure of Towers and a New Proof of the Tight Cut Lemma
    Nanao Kita
  6. Price Fluctuation in Online Leasing
    Christine Markarian, Bjorn Feldkord and Friedhelm Meyer Auf der Heide
Session 6 Combinatorial Optimization, Chair: Alireza Zarei (100 Minutes 5 Papers)
  1. Algorithms for the Ring Star Problem
    Xujin Chen, Xiaodong Hu, Zhongzheng Tang, Chenhao Wang and Ying Zhang
  2. Floorplans with Columns
    Katsuhisa Yamanaka, Md. Saidur Rahman and Shin-Ichi Nakano
  3. On the Profit-Maximizing for Transaction Platforms in Crowd Sensing
    Xi Luo, Jialiang Lu, Guangshuo Chen, Linghe Kong and Minyou Wu
  4. An Efficient Algorithm for Judicious Partition of Hypergraphs
    Tunzi Tan, Jihong Gui, Sainan Wang, Suixiang Gao and Wenguo Yang
  5. A Refined Characteristic of Minimum Contingency Set for Conjunctive Query
    Dongjing Miao and Zhipeng Cai
Session 7 Application, Chair: Ugo Vaccaro (100 Minutes 5 Papers)
  1. Cloning Automata: Simulation and Analysis of Computer Bacteria
    Chu Chen, Zhenhua Duan and Cong Tian
  2. Modelling and Solving Anti-aircraft Mission Planning for Defensive Missile Battalions
    Trang Nguyen, Trung Bui, Bang Nguyen and Su Le
  3. Perspectives of Big Data Analysis in Urban Railway Planning: Shenzhen Metro Case Study
    Keke Peng, Caiwei Yuan and Wen Xu
  4. Repair Position Selection for Inconsistent Data
    Xianmin Liu, Yingshu Li and Jianzhong Li
  5. Unbounded One-Way Trading on Distributions with Monotone Hazard Rate
    Francis Chin, Francis Lau, Hing-Fung Ting, Haisheng Tan and Yong Zhang
Session 8 Network, Chair: Neeraj Mittal (120 Minutes 6 Papers)
  1. A Framework for Overall Storage Overflow Problem to Maximize the Lifetime in WSNs
    Guoliang Song, Chen Zhang, Chuang Liu and Yuna Chai
  2. A Parallel Construction of Vertex-disjoint Spanning Trees with Optimal Heights in Star Networks
    Shih-Shun Kao, Jou-Ming Chang, Kung-Jui Pai, Jinn-Shyong Yang, Shyue-Ming Tang and Ro-Yu Wu
  3. Filtering Undesirable Flows in Networks
    Gleb Polevoy, Stojan Trajanovski, Paola Grosso and Cees de Laat
  4. Protein Mover's Distance: A Geometric Approach for Solving Global Alignment of PPI Networks
    Manni Liu and Hu Ding
  5. On Interdependent Failure Resilient Multi-path Routing in Smart Grid Communication Network
    Zishen Yang, Donghyun Kim and Wei Wang
  6. Toward Energy-Efficient and Robust Clustering Algorithm on Mobile Ad Hoc Sensor Networks
    Huamei Qi, Tailong Xiao, Anfeng Liu and Su Jiang
Session 9 Graph Theory, Chair: Qianping Gu (120 Minutes 6 Papers)
  1. Conflict-Free Connection Numbers of Line Graphs
    Bo Deng, Wenjing Li, Xueliang Li, Yaping Mao and Haixing Zhao
  2. Hamiltonian Cycles in Covering Graphs of Trees
    Hiroshi Nishiyama, Lasislav Stacho and Pavol Hell
  3. Mixed Connectivity of Random Graphs
    Ran Gu, Yongtang Shi and Neng Fan
  4. On \(k\)-Strong Conflict-Free Multicoloring
    Luisa Gargano, Adele Rescigno and Ugo Vaccaro
  5. The Coloring Reconfiguration Problem on Specific Graph Classes
    Tatsuhiko Hatanaka, Takehiro Ito and Xiao Zhou
  6. Tropical Paths in Vertex-Colored Graphs
    Johanne Cohen, Giuseppe F. Italiano, Yannis Manoussakis, Kim Thang Nguyen and Hong Phong Pham
Session 10 Combinatorial Optimization, Chair: Yannis Manoussakis (100 Minutes 5 Papers)
  1. Faster Algorithms for 1-Mappability of A Sequence
    Mai Alzamel, Panagiotis Charalampopoulos, Costas S Iliopoulos, Solon P Pissis, Jakub Radoszewski and Wing-Kin Sung
  2. Improved Methods for Computing Distances between Unordered Trees Using Integer Programming
    Eunpyeong Hong, Yasuaki Kobayashi and Akihiro Yamamoto
  3. Minimizing Total Completion Time of Batch Scheduling with Nonidentical Job Sizes
    Rongqi Li, Zhiyi Tan and Qianyu Zhu
  4. Novel Scheduling for Energy Management in Microgrid
    Zaixin Lu, Jd Youngs, Zhi Chen and Miao Pan
  5. Touring Convex Polygons In Polygonal Domain Fences
    Amirhossein Mozafari, Alireza Zarei and Arash Ahadi
Session 11 Application, Chair: Francis Y.L. Chin (100 Minutes 5 Papers)
  1. A Simple Greedy Algorithm for the Profit-Aware Social Team Formation Problem
    Shengxin Liu and Chung Keung Poon
  2. Bounds for Static Black-Peg AB Mastermind
    Christian Glazik, Gerold Jager, Jan Schiemann and Anand Srivastav
  3. Classication Statistics in RFID Systems
    Zhenzao Wen, Jiapeng Huang, Linghe Kong, Min-You Wu and Guihai Chen
  4. Doctor Rostering in Compliance with the New UK Junior Doctor Contract
    Anna Lavygina, Kristopher Welsh and Alan Crispin
  5. Generalized Bidirectional Limited Magnitude Error Correcting Code for MLC Flash Memories
    Akram Hussain, Xinchun Yu and Yuan Luo
Session 12 Demo and Application (Fast Track), Chair: Xiaofei Liu (80 Minutes 8 Papers)
  1. A Local Search Approximation Algorithm for A Squared Metric \(k\)-Facility Location Problem
    Dongmei Zhang, Dachuan Xu, Yishui Wang, Peng Zhang and Zhenning Zhang
  2. A New Approximation Algorithm for the Maximum Stacking Base Pairs Problem from RNA Secondary Structures Prediction
    Aizhong Zhou, Haitao Jiang, Jiong Guo and Daming Zhu
  3. Approximation Algorithms for the Generalized Stacker Crane Problem
    Jianping Li, Xiaofei Liu, Weidong Li and Li Guan
  4. Combinatorial Approximation algorithms for Spectrum Assignment Problem in Chain and Ring Networks
    Guangting Chen, Lei Zhang, An Zhang and Yong Chen
  5. Fast Approximation Algorithms for Computing Constrained Minimum Spanning Tree
    Pei Yao and Longkun Guo
  6. Longest Previous non-overlapping Factors Table Computation
    Supaporn Chairungsee and Maxime Crochemore
  7. Online Algorithms for Non-preemptive Speed Scaling on Power-Heterogeneous Processors
    Aeshah Alsughayyir and Thomas Erlebach
  8. The Euclidean Vehicle Routing Problem with Multiple Depots and Time Windows
    Liang Song and Hejiao Huang
Session 13 Demo and Application (Fast Track), Chair: Boting Yang (80 Minutes 8 Papers)
  1. Research on Arrival Integration method for Point Merge System in Tactical Operation
    Yannan Qi, Xinglong Wang and Chen Chen
  2. A Memetic Algorithm for the Linear Ordering Problem with Cumulative Costs
    Taoqing Zhou, Zhipeng Lu, Tao Ye and Kan Zhou
  3. Modeling and Verifying Multi-Core Programs
    Nan Zhang and Zhenhua Duan
  4. On Adaptive Bitprobe Schemes for Storing Two Elements
    Deepanjan Kesh
  5. On the Linearization of Scaffolds sharing Repeated Contigs
    Mathias Weller, Annie Chateau and Rodolphe Giroudeau
  6. On Structural Parameterizations of the Matching Cut Problem
    N R Aravind, Subrahmanyam Kalyanasundaram and Anjeneya Swami Kare
  7. Optimal Topology Design of High Altitude Platform based Maritime Broadband Communication Networks
    Jianli Duan, Tiange Zhao and Bin Lin
  8. Planar Vertex-Disjoint Cycle Packing: New Structures and Improved Kernel
    Qilong Feng, Xiaolu Liao and Jianxin Wang