COCOA 2021 
 Conference Photos 
 Call for Papers 
 Organizing Committee 
 Program Committee 
 Keynote Speakers 
 Author Instructions 
 Accepted Papers 
 Final Paper Submission 
 Conference Program 
 Contact Us 

Online Conference Participation and Presentation Instruction

To join conference: We will use Tencent Meeting as the online conferencing tool. If you are not in the mainland of China, you need download the international version, that is, Voov. Windows system and Mac OS are preffred for Tencent/Voov Meeting. Please install Tencnet Meeting/ Voov in your laptop. Just simply copy the conference room number into theTencent Meeting/Voov, and enter the correct password, then you are in. The conference room number and the password will be sent to the corresponding author of of each successfully registered paper through email. For the authors who have not yet registered, please complete your registration as soon as possible.



To make presentation: Your presentation is limited in 20 minutes with Q&A included. Please make your powerpionts ready before your presentation. When you make presentation, click the "Share" button, and choose to share the whole screen (recommended). We will be able to see your powerpoints. Then just go ahead to do the presentaiton as regular times! We highly recommend you to do live presentations so that we can have better communication, pre-recorded video should be the last choice when it is necessary.


You can click here to see detailed step-by-step instruction for Voov.



Session Schedule

Note: The following schedule follows China Standard Time (GMT+8)

December   18th, 2021

8:20 -- 8:30


8:30 -- 9:30

Keynote Speech #1   Prof. Xiaoming Sun 

(Institute of   Computing Technology, Chinese Academy of Sciences)

Session Chair: Prof.   Donglei Du

9:30 -- 9:40


9:40 -- 10:00



10:00 -- 10:20



10:20 -- 10:40



10:40 -- 11:00



11:00 -- 11:20



11:20 -- 11:40



11:40 -- 14:00


14:00 -- 14:20



14:20 -- 14:40



14:40 -- 15:00



15:00 -- 15:20



15:20 -- 15:40



15:40 -- 16:00



16:00 -- 16:10


16:10 -- 16:30



16:30 -- 18:50



16:50 -- 17:10



17:10 -- 17:30



17:30 -- 17:50



17:50 -- 18:10



December   19th, 2021

8:20 -- 8:30

Announcement for   COCOA 2022 next year

8:30 -- 9:30

Keynote Speech #2   Prof. Zhiyi Huang 

(University of Hong   Kong)

Session Chair: Prof.   Yong Zhang

9:30 -- 9:40


9:40 -- 10:00



10:00 -- 10:20



10:20 -- 10:40



10:40 -- 11:00



11:00 -- 11:20



11:20 -- 14:00


14:00 -- 14:20



14:20 -- 14:40



14:40 -- 15:00



15:00 -- 15:20



15:20 -- 15:40



15:40 -- 16:00

 Closing   Remarks





Session Details

Session A1 Algorithms and Hardness

Session Chair: Vincent Chau

A1-1 Power Domination for Bipartite Graphs and Chordal Graph, Pooja Goyal, B.S. Panda

A1-2 Finding All Leftmost Separators of Size $\leq k, Mahdi Belbasi, Martin Fürer

A1-3 Which Option is a Better Way to Improve Transfer Learning Performance? Honghui Xu, Zhipeng Cai, Wei Li

A1-4 The Fractional k-Truncated Metric Dimension of Graphs, Eunjeong Yi

A1-5 Routing among Convex Polygonal Obstacles in the Plane, R Inkulu, Pawan Kumar,

A1-6 On Structural Parameterizations of the Offensive Alliance Problem, Ajinkya Gaikwad, Soumen Maity


Session A2 Game Theory 

Session Chair: Yicheng Xu 

A2-1 Backgammon is Hard, R. Teal Witter

A2-2 Computing the One-Visibility Cop-Win Strategies for Trees, Boting Yang

A2-3 Evolutionary Equilibrium Analysis for Decision on Block Size in Blockchain Systems, Jinmian Chen, Yukun Cheng, Zhiqi Xu, Yan Cao

A2-4 The Price of Anarchy of Generic Valid Utility Systems, Yin Yang, Qingqin Nong, Suning Gong, Jingwen Du, Yumei Liang

A2-5 On Various Open-end Bin Packing Game, Ling Gai, Weiwei Zhang, Wenchang Luo, Yukun Cheng

A2-6 Two-Facility Location Games with a Minimum Distance Requirement on a Circle, Xiaoyu Wu, Lili Mei, Guochuan Zhang



Session B1 Scheduling

Session Chair: An Zhang

B1-1 Single Machine Scheduling with Rejection and Generalised Parameters, Xue Yu, Lingfa Lu, Liqi Zhang

B1-2 Optimal due Date Assignment without Restriction and Resource Allocation in Group Technology Scheduling, Ying Chen, Yongxi Cheng

B1-3 Efficient Algorithms for Scheduling Parallel Jobs with Interval Constraints in Clouds, Xuanming Xu, Longkun Guo

B1-4 Approximation Algorithms for Two Parallel Dedicated Machine Scheduling with Conflict Constraints, An Zhang, Liang Zhang, Yong Chen, Guangting Chen, Xing Wang

B1-5 Open shop scheduling problem with a non-resumable flexible maintenance period, Yuan Yuan, Xin Han,  Xinbo Liu, Yan Lan

B1-6 Routing and Scheduling Problems with Two Agents on a Line-Shaped Network, Hao Yan, Xiwen Lu


Session B2 Submodular Optimization

Session Chair: Bin Liu

B2-1 A Multi-Pass Streaming Algorithm for Regularized Submodular Maximization, Qinqin Gong, Gao Sui-xiang, Fengmin Wang, Ruiqi Yang

B2-2 Streaming Submodular Maximization under Differential Privacy Noise, Di Xiao, Longkun Guo, Kewen Liao, Pei Yao

B2-3 Maximization of Monotone Non-Submodular Functions with a Knapsack Constraint over the Integer Lattice, Jingjing Tan, Fengmin Wang, Xiaoqing Zhang, Yang Zhou

B2-4 Two-Stage Submodular Maximization under Curvature, Yanzhi Li, Zhicheng Liu, Chuchu Xu, Ping Li, Hong Chang, Xiaoyan Zhang,

B2-5 A Linear-Time Streaming Algorithm for Cardinality-Constrained Maximizing Monotone Non-submodular Set Functions, Min Cui, Donglei Du, Ling Gai, Ruiqi Yang

B2-6 On Maximizing the Difference Between an Approximately Submodular Function and a Linear Function subject to a Matroid Constraint, Yijing Wang, Yicheng Xu, Xiaoguang Yang


Session C1 Combinatorial Optimization 

Session Chair: Xiaoyan Zhang

C1-1 Parallel Algorithm For Minimum Partial Dominating Set In Unit Disk Graph, Weizhi Hong, Zhao Zhang, Yingli Ran,

C1-2 New Approximation Algorithms for the Rooted Budgeted Cycle Cover Problem, Jiangkun Li, Peng Zhang

C1-3 Target Coverage with Minimized Number of Camera Sensors, Pei Yao, Longkun Guo, Shuangjuan Li, Huihong Peng

C1-4 Approximation Algorithms for Some Min-Max and Minimum Stacker Crane Cover Problems, Yuhui Sun, Wei Yu, Zhaohui Liu

C1-5 A Novel Algorithm for Max Sat Calling MOCE to Order, Daniel Berend, Shahar Golan, Yochai Twitto

C1-6 Parameterized Complexity Classes Defined by Threshold Circuits: Using Sorting Networks to Show Collapses with W-Hierarchy Classes, Raffael Paranhos, Janio Carlos Nascimento Silva, Ueverton Souza, Luiz Satoru Ochi,


Session C2 Complexity 

Session Chair: Nip Kameng

C2-1 The Complexity of Finding Optimal Subgraphs to Represent Spatial Correlation, Jessica Enright, Duncan Lee, Kitty Meeks, William Pettersson, John Sylvester

C2-2 Complexity and Approximation Results on the Shared Transportation Problem, Tom Davot, Rodolphe Giroudeau, Jean-Claude König

C2-3 Directed Width Parameters on Semicomplete Digraphs, Frank Gurski, Dominique Komander, Carolin Rehs, Sebastian Wiederrecht

C2-4 Succinct Data Structures for SP, Block-Cactus and 3-Leaf Power Graphs, Sankardeep Chakraborty, Seungbum Jo, Kunihiko Sadakane, Srinivasa Rao Satti

C2-5 Approximation Algorithm and Hardness Results for Defensive Domination in Graphs, Michael A Henning, Arti Pandey, Vikash Tripathi

C2-6 On the k-colored Rainbow Sets in Fixed Dimensions, Vahideh Keikha, Hamidreza Keikha, Ali Mohades



Session D1 Graph Optimization 

Session Chair: Longkun Guo

D1-1 Cycle-Connected Mixed Graphs and Related Problems, Junran Lichen

D1-2 Capacitated Partial Inverse Maximum Spanning Tree under the Weighted $l_{\infty}$-Norm, Xianyue Li, Ruowang Yang, Heping Zhang, Zhao Zhang

D1-3 The Smallest Number of Vertices in a 2-Arc-Strong Digraph without Pair of Arc-Disjoint In- and Out-branchings, Ran Gu, Gregory Gutin, Shasha Li, Yongtang Shi, Zhenyu Taoqiu

D1-4 On the Feedback Number of 3-Uniform Linear Extremal Hypergraph, Zhongzheng Tang, Yucong Tang, Zhuo Diao

D1-5 An Improved Physical ZKP for Nonogram, Suthee Ruangwises


Session D2 Algorithms 

Session Chair: Deshi Ye

D2-1 Sublinear-time Reductions for Big Data Computing, Xiangyu Gao, Jianzhong Li, Dongjing Miao

D2-2 Parameterized Algorithms for Linear Layouts of Graphs with Respect to the Vertex Cover Number, Yunlong Liu, Yixuan Li, Jingui Huang,

D2-3 Two-Stage Stochastic Max-Weight Independent Set Problems, Min Li, Qian Liu, Yang Zhou

D2-4 Improved Parameterized Approximation for Balanced k-Median, Zhen Zhang, Qilong Feng

D2-5 Approximation Algorithm for Min-Max Correlation Clustering Problem with Outliers, Sai Ji, Min Li, Mei Liang, Zhenning Zhang


Session E1 Networks and Applications

Session Chair: Qiufen Ni 

E1-1 Maximize the Probability of Union-Influenced in Social Networks, Guoyao Rao, Yongcai Wang, Wenping Chen, Deying Li, Weili Wu

E1-2 Generalized Self-Profit Maximization in Attribute Networks, Liman Du, Wenguo Yang, Suixiang Gao

E1-3 Online Bottleneck Semi-Matching, Xiao Man, Shu Zhao, Weidong Li, Jinhua Yang,

E1-4 Constrained Stable Marriage with Free edges or Few Blocking Pairs, Yinghui Wen, Jiong Guo

E1-5 The Selection of COVID-19 Epidemic Prevention and Control Programs Based on Group Decision Making, Chunsheng Cui, Baiqiu Li, Liu Wang


Session E2 Approximation Algorithms 

Session Chair: Lu Han

E2-1 A LP-based approximation algorithm for generalized traveling salesperson path problem, Jian Sun, Gregory Gutin, Xiaoyan Zhang

E2-2 Delay-Constrained Minimum Shortest Path Trees and Related Problems, Junran Lichen, Lijian Cai, Jianping Li, Suding Liu, Pengxiang Pan, Wencheng Wang

E2-3 An Improved Approximation Algorithm for Capacitated Correlation Clustering Problem, Sai Ji, Yukun Cheng, Jingjing Tan, Zhongrui Zhao

E2-4 An Improved Approximation Algorithm for Squared Metric k-Facility Location, Zhen Zhang, Qilong Feng