Conference Program

All the events will be held at the QiongLin Hall on the 3rd floor, Bldg.8 of the City Hotel Xiamen. All papers of COCOA2019 can be downloaded here.



December 12, 2019

Session Time Titles of Talks / Speakers and Authors
Registration 9:00 - 20:00
-

December 13, 2019

-
Session Time Titles of Talks / Speakers and Authors
Registration 08:00 – 17:30
Opening Ceremony 08:45 – 09:00
Keynote1 09:00 - 10:00 Sublinear-Time Paradigm --- How to Challenge Big Data
Prof. Hiro Ito (The University of Electro-Communications, Japan)
Coffee Break 10:00 - 10:30
Session 1
Algorithm
(Session Chair: Dongjing Miao, Harbin Institute of Technology, China)
10:30 - 10:50 Cake Cutting with Single-Peaked Valuations
Chenhao Wang and Xiaoying Wu (Chinese Academy of Sciences, China)
10:50 - 11:10 Exact Algorithms for the Bounded Repetition Longest Common Subsequence Problem
Yuichi Asahiro (Kyushu Sangyo University, Japan); Jesper Jansson (The Hong Kong Polytechnic University, Hong kong); Guohui Lin (University of Alberta, Canada); Eiji Miyano (Kyushu Institute of Technology, Japan); Hirotaka Ono (Nagoya University, Japan) and Tadatoshi Utashima (Kyushu Institute of Technology, Japan)
11:10 - 11:30 Approximation Algorithm and Incentive Ratio of the Selling with Preference
Pan Li and Qiang Hua (Hebei University, China); Zhijun Hu (Guizhou University, China); Hingfung Ting (The University of Hong Kong, Hong Kong) and Yong Zhang (Chinese Academy of Sciences, China)
11:30 - 11:50 New Results on a Family of Geometric Hitting Set Problems in the Plane
Joseph Mitchell (Stony Brook University, USA) and Supantha Pandit (Dhirubhai Ambani Institute of Information and Communication Technology, India)
11:50 - 12:10 TNT: An Effective Method for Finding Correlations Between Two Continuous Variables
Dayuan Zheng, Zhaogong Zhang and Yuting Zhang (Heilongjiang University, China)
Lunch 12:10-13:40
-
Session 2
Computational Geometry
(Session Chair: Zaobo He, Miami University, USA)
13:40 - 14:00 A True O(n\log{n}) Algorithm for the All-k-Nearest-Neighbors Problem
Hengzhao Ma and Jianzhong Li (Harbin Institute of Technology, China)
14:00 - 14:20 Approximation Algorithms for Some Minimum Postmen Cover Problems
Yuying Mao, Wei Yu, Zhaohui Liu and Jiafeng Xiong (East China University of Science and Technology, China)
14:20 - 14:40 The k-Delivery Traveling Salesman Problem: Revisited
Jinxiang Gan and Guochuan Zhang (Zhejiang University, China)
14:40 - 15:00 A Novel Virtual Traffic Light Algorithm Based on V2V for Single Intersection in Vehicular Networks
Longjiang Guo (Shaanxi Normal University, China); De Wang (Heilongjiang University, China); Peng Li, Lichen Zhang, Meirui Ren, Hong Liu and Ana Wang (Shaanxi Normal University, China)
15:00 - 15:20 Algorithmic Pricing for the Partial Assignment
Guichen Gao (Chinese Academy of Sciences, China); Hing-Fung Ting (The University of Hong Kong, Hong Kong); Yong Zhang (Chinese Academy of Sciences, China); Yifei Zou (The University of Hong Kong, Hong Kong) and Li Ning (Chinese Academy of Sciences, China)
Coffee Break 15:20 - 15:50
-
Session 3 Combinatorial Optimization (Session Chair: Wei Yu, East China University of Science and Technology, China) 15:50 - 16:10 Critical Rows of Almost-Factorable Matrices
Peter Ballen (University of Pennsylvania, USA)
16:10 - 16:30 Approximating Bounded Job Start Scheduling with Application in Royal Mail Deliveries under Uncertainty
Jeremy T. Bradley (Royal Mail, UK); Dimitrios Letsios, Ruth Misener and Natasha Page (Imperial College London, UK)
16:30 - 16:50 Minimum-Width Drawings of Phylogenetic Trees
Juan Jose Besa, Michael T. Goodrich, Timothy Johnson and Martha C. Osegueda (University of California, Irvine, USA)
16:50 - 17:10 On the Hardness of Some Geometric Optimization Problems with Rectangles
Supantha Pandit (Dhirubhai Ambani Institute of Information and Communication Technology, India)
17:10 - 17:30 Sequence Submodular Maximization Meets Streaming
Ruiqi Yang and Dachuan Xu (Beijing University of Technology, China), Longkun Guo (Fuzhou University, China) and Dongmei Zhang (Shandong Jianzhu University, China)
Banquet Dinner 18:00 - 21:00
-

December 14, 2019

Session Time Titles of Talks / Speakers and Authors
Registration 08:00 – 17:30
-
Keynote2 09:00 - 10:00 Complexity Theory and Highly Efficient Algorithms for Big Data Computation with Limited Computing Resources
Professor Jianzhong Li (Harbin Institute of Technology, China)
Coffee Break 10:00 - 10:30
-
Session 4
Computational Theory
(Session Chair: Michel Habib, IRIF, CNRS and Paris University, France)
10:30 - 10:50 Improved stretch factor of Delaunay triangulations of points in convex position
Xuehou Tan and Charatsanyakul Sakthip (Tokai University, Japan); Bo Jiang (Dalian Maritime University, China)
10:50 - 11:10 Parametrized Runtimes for Label Tournaments
Stefan Funke (University of Stuttgart, Germany) and Sabine Storandt (University of Konstanz, Germany)
11:10 - 11:30 A Fast Exact Algorithm for Airplane Refueling Problem
Jianshu Li, Xiaoyin Hu, Junjie Luo and Jinchuan Cui (Chinese Academy of Sciences, China)
11:30 - 11:50 Two-machine Flow Shop Scheduling Problem under Linear Constraints
Kameng Nip (Sun Yat-sen University, China)and Zhenbo Wang (Tsinghua University, China)
11:50 - 12:10 Card-based Secure Ranking Computations
Ken Takashima, Yuta Abe, Tatsuya Sasaki and Daiki Miyahara (Tohoku University, Japan); Kazumasa Shinagawa (Tokyo Institute of Technology, Japan); Takaaki Mizuki and Hideaki Sone (Tohoku University, Japan)
Lunch 12:10 - 13:40
-
Session 5
Data Structure & Game Theory
(Session Chair: Yong Zhang, Chinese Academy of Sciences, China)
13:40 - 14:00 Recognizing the Tractability in Big Data Computing
Xiangyu Gao, Jianzhong Li, Dongjing Miao and Xianmin Liu (Harbin Institute of Technology, China)
14:00 - 14:20 Tracking Histogram of Attributes over Private Social Data in Data Markets
Zaobo He (Miami University, USA) and Yan Huang (Kennesaw State University, USA)
14:20 - 14:40 Improved Bounds for Two Query Adaptive Bitprobe Schemes Storing Five Elements
Mirza Galib Anwarul Husain Baig and Deepanjan Kesh (Indian Institute of Technology Guwahati, India)
14:40 - 15:00 The Price of Anarchy for the Load Balancing Game with a Randomizing Scheduler
Xujin Chen, Xiaodong Hu and Xiaoying Wu (Chinese Academy of Sciences, China)
15:00 - 15:20 Scheduling Game with Machine Modification in the Random Setting
Chaoyu He and Zhiyi Tan (Zhejiang University, China)
Coffee Break 15:20 - 15:50
-
Session 6
Approximation Algorithm & Graph Theory
(Session Chair: Jiaming Nie, Sun Yat-sen University, China)
15:50 - 16:10 Approximation algorithms for maximally balanced connected graph partition
Yong Chen (Hangzhou Dianzi University, China), Zhi-Zhong Chen (Tokyo Denki University, Japan), Guohui Lin (University of Alberta, Canada), Yao Xu (Kettering University, USA) and An Zhang (Hangzhou Dianzi University, China)
16:10 - 16:30 The Balanced Connected Subgraph problem: Complexity results in bounded-degree and bounded-diameter graphs
Valentin Pollet (Université de Montpellier/LIRMM, France); Benoit Darties and Rodolphe Giroudeau (LIRMM, France); Konig Jean-Claude (Université de Montpellier, France)
16:30 - 16:50 Fast Diameter Computation within Split Graphs
Guillaume Ducoffe (National Institute of Research and Development in Informatics, Romania), Michel Habib (IRIF, CNRS and Paris University, France) and Laurent Viennot (INRIA, France)
16:50 - 17:10 Improved Approximation Algorithm for Minimum Weight k-Subgraph Cover Problem
Pengcheng Liu, Xiaohui Huang and Zhao Zhang (Zhejiang Normal University, China)
17:10 - 17:30 A randomized approximation algorithm for metric triangle packing
Yong Chen (Hangzhou Dianzi University, China), Zhi-Zhong Chen (Tokyo Denki University, Japan), Guohui Lin (University of Alberta, Canada), Lusheng Wang (City University of Hong Kong, Hong Kong) and An Zhang (Hangzhou Dianzi University, China)

December 15, 2019

Session Time Titles of Talks / Speakers and Authors
Registration
08:00 – 15:30
-
Session 7
Computational Geometry & Graph Theory
(Session Chair: Hsu-Chun Yen, National Taiwan University, Taiwan)
08:30 - 08:50 Bounded Degree Graphs Computed for Traveling Salesman Problem Based on Frequency Quadrilaterals
Yong Wang (North China Electric Power University, China)
08:50 - 09:10 Solving (k − 1)-Stable Instances of k-terminal cut with Isolating Cuts
Mark Velednitsky (University of California, Berkeley, USA)
09:10 - 09:30 Algorithms and Hardness Results for the Maximum Balanced Connected Subgraph Problem
Yasuaki Kobayashi, Kensuke Kojima, Norihide Matsubara, Taiga Sone and Akihiro Yamamoto (Kyoto University, Japan)
09:30 - 09:50 On Conflict-free Chromatic Guarding of Simple Polygons
Onur Çağırıcı and Petr Hlineny (Masaryk University, Czechia); Bodhayan Roy (Indian Institute of Technology Bombay, India); Subir Kumar Ghosh (Ramakrishna Mission Vivekananda University, India)
Coffee Break 09:50 - 10:20
-
Session 8 Graph Theory
(Session Chair: Sean Yaw, Montana State University, USA)
10:20 - 10:40 Some Graph Optimization Problems with Weights Satisfying Linear Constraints
Kameng Nip (Sun Yat-sen University, China), Zhenbo Wang and Tianning Shi (Tsinghua University, China)
10:40 - 11:00 Contact Representations of Directed Planar Graphs in 2D and 3D
Chun-Hsiang Chan and Hsu-Chun Yen (National Taiwan University, Taiwan)
11:00 - 11:20 Feature Selection Based On Graph Structure
Zhiwei Hu, Zhaogong Zhang, Zongchao Huang and Dayuan Zheng (Heilongjiang University, China); Ziliang Zhang (University of Alabama, USA)
11:20 - 11:40 Characterizations for special directed co-graphs
Frank Gurski, Dominique Komander and Carolin Rehs (University of Düsseldorf, Germany)
11:40 - 12:00 On vertex-edge and independent vertex-edge domination
Subhabrata Paul (IIT Patna, India) and Keshav Ranjan (IIT Madras, India)
Lunch 12:00 - 13:30
-
Session 9
Computational Geometry & Graph Theory
(Session Chair: Longjiang Guo, Shaanxi Normal University, China)
13:30 - 13:50 Approximate shortest paths in polygons with violations
Binayak Dutta (Tezpur University, India) and Sasanka Roy (Indian Statistical Institute, India)
13:50 - 14:10 Balanced Connected Subgraph Problem in Geometric Intersection Graphs
Sujoy Bhore (Vienna University of Technology, Austria), Satyabrata Jana (Indian Statistical Institute, India), Supantha Pandit (Dhirubhai Ambani Institute of Information and Communication Technology, India) and Sasanka Roy (Indian Statistical Institute, India)
14:10 - 14:30 The One-Cop-Moves Game on Graphs of Small Treewidth
Lusheng Wang (City University of Hong Kong, Hong Kong) and Boting Yang (University of Regina, Canada)
14:30 - 14:50 Edge Exploration of a Graph by Mobile Agent
Amit Kumar Dhar and Barun Gorain (Indian Institute of Technology Bhilai, India); Kaushik Mondal (Indian Institute of Information Technology Vadodara, India); Shaswati Patra and Rishi Ranjan Singh (Indian Institute of Technology Bhilai, India)
14:50 - 15:10 Identifying Structural Hole Spanners in Social Networks via Graph Embedding
Sijie Chen, Yong Liu and Ziwei Quan (Heilongjiang University, China)
Coffee Break 15:10 - 15:30
-
Session 10
Networking & Scheduling
(Session Chair: Longcheng Liu, Xiamen University, China)
15:30 - 15:50 PATRON: A Unified Pioneer-Assisted Task Recommendation Framework in Realistic Crowdsourcing System
Yuchen Xia, Zhitian Xu and Xiaofeng Gao (Shanghai Jiao Tong University, China); Mo Chi (Tencent Inc., China); Guihai Chen (Shanghai Jiao Tong University, China)
15:50 - 16:10 Prediction Based Reverse Auction Incentive Mechanism for Mobile Crowdsensing System
Zhen Wang, Jinghua Zhu and Doudou Li (Heilongjiang University, China)
16:10 - 16:30 A Task assignment Approach with Maximizing User Type Diversity in Mobile Crowdsensing
Ana Wang, Lichen Zhang, Longjiang Guo, Meirui Ren, Peng Li and Bin Yan (Shaanxi Normal University, China)
16:30 - 16:50 Car-Sharing problem: Online scheduling with Flexible Advance Bookings
Haodong Liu, Kelin Luo, Yinfeng Xu and Huili Zhang (Xi'an Jiaotong University, China)
16:50 - 17:10 Graph Simplification for Infrastructure Network Design
Sean Yaw (Montana State University, USA); Richard Middleton and Brendan Hoover (Los Alamos National Laboratory, USA)