• COCOA 2019
• Call for Papers
• Organizing Committee
• Program Committee
• Keynote Speakers
• Author Instructions
• Accepted Papers
• Final Paper Submission
• Conference Program
• Registration
• Accommodation
• Local&Travel Information
• Contact Us

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)