COCOON 2022 Program
(GMT+8:00, Beijing Time)
For the program, you can download it here COCOON 2022-Program.pdf!
| Date: Oct. 22 (Saturday) | ||
| Onsite: F1119, SIAT, CAS Online: Zoom ID: 822 7844 3336 Passcode: cocoon2022 |
||
| 9:00—9:20 | Opening Ceremony | |
| Chair: Yong Zhang |
9:20—10:20 | keynote 1:Pinyan Lu Title: First Price Auction is $1 - 1/e^2$ Efficient |
| 10:20—10:40 | Coffee Break | |
| Date: Oct. 22 (Saturday) | ||
| Onsite: F1119, SIAT, CAS Online: Zoom ID: 822 7844 3336 Passcode: cocoon2022 |
||
| Session 1 Chair: Xiaowei Wu | 10:40-11:00 | Approximation Algorithms for Capacitated Assignment with Budget Constraints and Applications in Transportation Systems Hongyi Jiang, Samitha Samaranayake |
| 11:00-11:20 | Facility Location Games with Group Externalities Houyu Zhou |
|
| 11:20-11:40 | Facility Location Games with Ordinal Preferences Hau Chan, Minming Li, Chenhao Wang, Yingchao Zhao |
|
| 11:40-12:00 | Fair Division with Minimal Withheld Information in Social Networks Ivan Bliznets, Anton Bukov, Danil Sagunov |
|
| Lunch | ||
| Session 2 Chair: Jialin Zhang | 14:00-14:20 | Hitting Geometric Objects Online via Points in~$\mathbb{Z}^d$ Minati De, Satyam Singh |
| 14:20-14:40 | Online one-sided smooth function maximization Hongxiang Zhang, Dachuan Xu, Ling Gai, Zhenning Zhang |
|
| 14:40-15:00 | Approximation Algorithms for the Min-Max Mixed Rural Postmen Cover Problem and Its Variants Liting Huang, Wei Yu, Zhaohui Liu |
|
| 15:00-15:20 | A 4-Space Bounded Approximation Algorithmfor Online Bin Packing Problem Sizhe Li, Jinghui Xue, Mingming Jin, Kai Wang, Kun He |
|
| 15:20-15:40 | Algorithms for hard-constraint point processes via discretization Tobias Friedrich, Andreas Göbel, Maximilian Katzmann, Martin S.Krejca, MarcusPappik |
|
| 15:40-16:00 | Coffee Break | |
| Chair: Dongjing Miao |
16:00-17:00 | keynote 2: Leslie Ann Goldberg Instability of backoff protocols with arbitrary arrival rates |
| Date: Oct. 22 (Saturday) | ||
| Onsite: F1018, SIAT, CAS Online: Zoom ID: 890 5932 5491 Passcode: cocoon2022 |
||
| Session 3 Chair: Peng Zhang | 10:40-11:00 | An $O(n^3)$-Time Algorithm for the Min-Gap Unit-Length Job Scheduling Problem Fei Li |
| 11:00-11:20 | Turing Machines with Two-level Memory: A Deep Look into the Input/Output Complexity Hengzhao Ma, Jianzhong Li, Xiangyu Gao, Tianpeng Gao |
|
| 11:20-11:40 | Single machine scheduling with rejection to minimize the k-th power of the makespan Liqi Zhang, Lingfa Lu |
|
| 11:40-12:00 | Two-Stage BP Maximization under p-matroid Constraint Hong Chang, Zhicheng Liu, Donglei Du, Xiaoyan Zhang |
|
| Lunch | ||
| Session 4 Chair: Longkun Guo | 14:00-14:20 | A stochastic non-monotone DR-submodular maximization problem over a convex set Yuefang Lian, Dachuan Xu, Donglei Du, Yang Zhou |
| 14:20-14:40 | Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-in Cascading Circuits (Extended Abstract) Tomoyuki Yamakami |
|
| 14:40-15:00 | Improved Deterministic Algorithms for Non-monotone Submodular Maximization Xiaoming Sun, Jialin Zhang, Shuo Zhang, Zhijie Zhang |
|
| 15:00-15:20 | Online non-monotone DR-submodular maximization: 1/4 approximation ratio and sublinear regret Junkai Feng, Ruiqi Yang, Haibin Zhang, Zhenning Zhang |
|
| 15:20-16:00 | Coffee Break | |
| Onsite: F1119, SIAT, CAS Online: Zoom ID: 822 7844 3336 Passcode: cocoon2022 |
||
| Chair: Dongjing Miao |
16:00-17:00 | keynote 2: Leslie Ann Goldberg Instability of backoff protocols with arbitrary arrival rates |
| Date: Oct. 23 (Sunday) | ||
| Onsite: F1119, SIAT, CAS Online: Zoom ID: 822 7844 3336 Passcode: cocoon2022 |
||
| Session 5 Chair: Shengxin Liu | 9:00-9:20 | Counting Cycles on Planar Graphs in Subexponential Time Jin-Yi Cai, Ashwin Maran |
| 9:20-9:40 | Semi-strict chordal digraphs Jing Huang, Ying Ying Ye |
|
| 9:40-10:00 | An evolving network model from clique extension Anthony Bonato, Ryan Cushman, Trent G. Marbach, Zhiyuan Zhang |
|
| 10:00-10:20 | The Hamiltonian Path Graph is Connected for Simple s, t Paths in Rectangular Grid Graphs Rahnuma Islam Nishat, Venkatesh Srinivasan, Sue Whitesides |
|
| 10:20-10:40 | Coffee Break | |
| Session 6 Chair: Hubert Chan | 10:40-11:00 | Fully Dynamic k-Center Clustering with Outliers T-H. Hubert Chan, Silvio Lattanzi, Mauro Sozio, Bo Wang |
| 11:00-11:20 | Improved Separated Red-Blue Center Clustering Yuan Sha |
|
| 11:20-11:40 | Online semi-matching problem with two heterogeneous sensors in a metric space Man Xiao, Weidong Li |
|
| 11:40-12:00 | Approximation Schemes for k-Facility Location Xiangyan Kong, Zhen Zhang |
|
| Lunch | ||
| Date: Oct. 23 (Sunday) | ||
| Onsite: F1018, SIAT, CAS Online: Zoom ID: 890 5932 5491 Passcode: cocoon2022 |
||
| Session 7 Chair: Weitian Tong | 9:00-9:20 | Revisiting Maximum Satisfiability and Related Problems in Data Streams Hoa T. Vu |
| 9:20-9:40 | Escape from the Room Kento Kimura, Kazuyuki Amano, Shin-ichi Nakano |
|
| 9:40-10:00 | A quantum version of Pollard’s Rho of which Shor’s Algorithm is a particular case Daniel Chicayban Bastos, Luis Antonio Kowada |
|
| 10:00-10:20 | Coffee Break |
|
| Session 8 Chair: Minming Li | 10:40-11:00 | Optimal Window Queries on Line Segments using the Trapezoidal Search DAG Milutin Brankovic, Martin P. Seybold |
| 11:00-11:20 | Rotation Distance for Rank Bounded Trees SKM Anoop, Jayalal Sarma |
|
| 11:20-11:40 | Proper colorability of segment intersection graphs Robert D. Barish, Tetsuo Shibuya |
|
| 11:40-12:00 | Generalized Sweeping Line Spanners Keenan Lee, André van Renssen |
|
| Lunch | ||
| Date: Oct. 23 (Sunday) | ||
| Onsite: F1119, SIAT, CAS Online: Zoom ID: 822 7844 3336 Passcode: cocoon2022 |
||
| Session 9 Chair: Shaofeng Jiang | 14:00-14:20 | Space Limited Graph Algorithms on Big Data Jianer Chen, Zirui Chu, Ying Guo, Wei Yang |
| 14:20-14:40 | Refined Computational Complexities of Hospitals/Residents Problem with Regional Caps Koki Hamada, Shuichi Miyazaki |
|
| 14:40-15:00 | Some New Results on Gallai Theorem and Perfect Matching for k-Uniform Hypergraphs Zhongzheng Tang, Zhuo Diao |
|
| 15:00-15:20 | Linear-Time Algorithm for Paired-Domination on Distance-Hereditary Graphs Ta-Yu Mu, Ching-Chi Lin |
|
| 15:20-15:40 | Capacitated Facility Location with Outliers/Penalties Rajni Dabas, Neelima Gupta |
|
| 15:40-16:00 | Coffee Break | |
| Session 10 Chair: Thomas Erlebach | 16:00-16:20 | A Probabilistic Model Revealing Shortcomings in Lua’s Hybrid Tables Conrado Martínez, Cyril Nicaud, Pablo Rotondo |
| 16:20-16:40 | LotterySampling: A Randomized Algorithm for the Heavy Hitters and Top-k Problems in Data Streams Conrado Martínez, Gonzalo Solera-Pardo |
|
| 16:40-17:00 | On the Complexity of Minimum Maximal Acyclic Matchings Juhi Chaudhary, Sounaka Mishra, B S Panda |
|
| 17:00-17:20 | Rooting Gene Trees via Phylogenetic Networks Jerzy Tiuryn, Natalia Rutecka, Paweł Górecki |
|
| Date: Oct. 23 (Sunday) | ||
| Onsite: F1018, SIAT, CAS Online: Zoom ID: 890 5932 5491 Passcode: cocoon2022 |
||
| Session 11 Chair: Biaoshuai Tao | 14:00-14:20 | The bound coverage problem by aligned disks in L1 metric Xiaofei Liu, Zhonghao Liu |
| 14:20-14:40 | Distributed Dominating Sets in Interval Graphs Barun Gorain, Kaushik Mondal, Supantha Pandit |
|
| 14:40-15:00 | Reallocation Problems with Minimum Completion Time Toshimasa Ishii, Jun Kawahara, Kazuhisa Makino, Hirotaka Ono |
|
| 15:00-15:20 | Flow shop scheduling problems with transportation constraints revisited Yuan Yuan, Xin Han, Yan Lan |
|
| 15:20-15:40 | Analysis of Approximate sorting in I/O model Tianpeng Gao, Jianzhong Li |
|
| 15:40-16:00 | Coffee Break | |
| Session 12 Chair: Yukun Cheng | 16:00-16:20 | Two Generalizations of Proper Coloring: Hardness and Approximability Ivan Bliznets, Danil Sagunov |
| 16:20-16:40 | Large k-gons in a 1.5D Terrain Vahideh Keikha |
|
| 16:40-17:00 | Customizable Hub Labeling: Properties and Algorithms Johannes Blum, Sabine Storandt |
|
| 17:00-17:20 | Bounding the Number of Eulerian Tours in Undirected Graphs Giulia Punzi |
|
| 17:20-17:40 | Refutation of Spectral Graph Theory Conjectures with Monte Carlo Search Milo Roucairol, Tristan Cazenavea |
|