Combinatorial Optimization and Applications: 14th International Conference, COCOA 2020, Dallas, TX, USA, December 11–13, 2020, Proceedings

Front Matter ....Pages i-xiii
Front Matter ....Pages 1-1
 Approximate Ridesharing of Personal Vehicles Problem  (Qian-Ping Gu, Jiajian Leo Liang, Guochuan Zhang)....Pages 3-18
 A Sub-linear Time Algorithm for Approximating k-Nearest-Neighbor with Full Quality Guarantee  (Hengzhao Ma, Jianzhong Li)....Pages 19-31
 Sampling-Based Approximate Skyline Calculation on Big Data  (Xingxing Xiao, Jianzhong Li)....Pages 32-46
 Approximating k-Orthogonal Line Center  (Barunabha Chakraborty, Arun Kumar Das, Sandip Das, Joydeep Mukherjee)....Pages 47-60
 Selecting Sources for Query Approximation with Bounded Resources  (Hongjie Guo, Jianzhong Li, Hong Gao)....Pages 61-75
 Parameterized Complexity of Satisfactory Partition Problem  (Ajinkya Gaikwad, Soumen Maity, Shuvam Kant Tripathi)....Pages 76-90
 An Approximation of the Zero Error Capacity by a Greedy Algorithm  (Marcin Jurkiewicz)....Pages 91-104
Front Matter ....Pages 105-105
 On the Complexity of a Periodic Scheduling Problem with Precedence Relations  (Richard Hladík, Anna Minaeva, Zdeněk Hanzálek)....Pages 107-124
 Energy-Constrained Drone Delivery Scheduling  (Rafael Papa, Ionut Cardei, Mihaela Cardei)....Pages 125-139
 Scheduling Jobs with Precedence Constraints to Minimize Peak Demand  (Elliott Pryor, Brendan Mumey, Sean Yaw)....Pages 140-150
 Reachability Games for Optimal Multi-agent Scheduling of Tasks with Variable Durations  (Dhananjay Raju, Niklas Lauffer, Ufuk Topcu)....Pages 151-167
 Improved Scheduling with a Shared Resource via Structural Insights  (Christoph Damerius, Peter Kling, Minming Li, Florian Schneider, Ruilong Zhang)....Pages 168-182
Front Matter ....Pages 183-183
 Two-Stage Pricing Strategy with Price Discount in Online Social Networks  (He Yuan, Ziwei Liang, Hongwei Du)....Pages 185-197
 Almost Linear Time Algorithms for Minsum k-Sink Problems on Dynamic Flow Path Networks  (Yuya Higashikawa, Naoki Katoh, Junichi Teruyama, Koji Watase)....Pages 198-213
 Matched Participants Maximization Based on Social Spread  (Guoyao Rao, Yongcai Wang, Wenping Chen, Deying Li, Weili Wu)....Pages 214-229
 Mixed-Case Community Detection Problem in Social Networks  (Yapu Zhang, Jianxiong Guo, Wenguo Yang)....Pages 230-241
 How to Get a Degree-Anonymous Graph Using Minimum Number of Edge Rotations  (Cristina Bazgan, Pierre Cazals, Janka Chlebíková)....Pages 242-256
 The Small Set Vertex Expansion Problem  (Soumen Maity)....Pages 257-269
Front Matter ....Pages 271-271
 On Unit Read-Once Resolutions and Copy Complexity  (P. Wojciechowski, K. Subramani)....Pages 273-288
 Propositional Projection Temporal Logic Specification Mining  (Nan Zhang, Xiaoshuai Yuan, Zhenhua Duan)....Pages 289-303
 An Improved Exact Algorithm for the Exact Satisfiability Problem  (Gordon Hoi)....Pages 304-319
 Transforming Multi-matching Nested Traceable Automata to Multi-matching Nested Expressions  (Jin Liu, Zhenhua Duan, Cong Tian)....Pages 320-333
 On the Complexity of Some Facet-Defining Inequalities of the QAP-Polytope  (Pawan Aurora, Hans Raj Tiwary)....Pages 334-349
 Hardness of Segment Cover, Contiguous SAT and Visibility with Uncertain Obstacles  (Sharareh Alipour, Salman Parsa)....Pages 350-363
 On the Complexity of Minimum Maximal Uniquely Restricted Matching  (Juhi Chaudhary, B. S. Panda)....Pages 364-376
Front Matter ....Pages 377-377
 A Two-Layers Heuristic Search Algorithm for Milk Run with a New PDPTW Model  (Xuhong Cai, Li Jiang, Songhu Guo, Hejiao Huang, Hongwei Du)....Pages 379-392
 Optimal Deterministic Group Testing Algorithms to Estimate the Number of Defectives  (Nader H. Bshouty, Catherine A. Haddad-Zaknoon)....Pages 393-410
 Nearly Complete Characterization of 2-Agent Deterministic Strategyproof Mechanisms for Single Facility Location in \\(L_p\\) Space  (Jianan Lin)....Pages 411-425
 Packing and Covering Triangles in Dense Random Graphs  (Zhongzheng Tang, Zhuo Diao)....Pages 426-439
 Mechanism Design for Facility Location Games with Candidate Locations  (Zhongzheng Tang, Chenhao Wang, Mengqi Zhang, Yingchao Zhao)....Pages 440-452
Front Matter ....Pages 453-453
 Online Maximum k-Interval Coverage Problem  (Songhua Li, Minming Li, Lingjie Duan, Victor C. S. Lee)....Pages 455-470
 Vertex Fault-Tolerant Spanners for Weighted Points in Polygonal Domains  (R. Inkulu, Apurv Singh)....Pages 471-485
 Competitive Analysis for Two Variants of Online Metric Matching Problem  (Toshiya Itoh, Shuichi Miyazaki, Makoto Satake)....Pages 486-498
 Guarding Disjoint Orthogonal Polygons in the Plane  (Ovidiu Daescu, Hemant Malik)....Pages 499-514
 Optimal Strategies in Single Round Voronoi Game on Convex Polygons with Constraints  (Aritra Banik, Arun Kumar Das, Sandip Das, Anil Maheshwari, Swami Sarvottamananda)....Pages 515-529
 Cutting Stock with Rotation: Packing Square Items into Square Bins  (Shahin Kamali, Pooya Nikbakht)....Pages 530-544
Front Matter ....Pages 545-545
 Remotely Useful Greedy Algorithms  (Moritz Beck)....Pages 547-561
 Parameterized Algorithms for Fixed-Order Book Drawing with Bounded Number of Crossings per Edge  (Yunlong Liu, Jie Chen, Jingui Huang)....Pages 562-576
 Fractional Maker-Breaker Resolving Game  (Eunjeong Yi)....Pages 577-593
 Price of Fairness in Budget Division for Egalitarian Social Welfare  (Zhongzheng Tang, Chenhao Wang, Mengqi Zhang)....Pages 594-607
 Inspection Strategy for On-board Fuel Sampling Within Emission Control Areas  (Lingyue Li, Suixiang Gao, Wenguo Yang)....Pages 608-623
 Novel Algorithms for Maximum DS Decomposition  (Shengminjie Chen, Wenguo Yang, Suixiang Gao, Rong Jin)....Pages 624-638
 Reading Articles Online  (Andreas Karrenbauer, Elizaveta Kovalevskaya)....Pages 639-654
Front Matter ....Pages 655-655
 An Efficient Mechanism for Resource Allocation in Mobile Edge Computing  (Guotai Zeng, Chen Zhang, Hongwei Du)....Pages 657-668
 Data Sensing with Limited Mobile Sensors in Sweep Coverage  (Zixiong Nie, Chuang Liu, Hongwei Du)....Pages 669-680
 Trip-Vehicle Assignment Algorithms for Ride-Sharing  (Songhua Li, Minming Li, Victor C. S. Lee)....Pages 681-696
 Minimum Wireless Charger Placement with Individual Energy Requirement  (Xingjian Ding, Jianxiong Guo, Deying Li, Ding-Zhu Du)....Pages 697-710
 An Efficient Algorithm for Routing and Recharging of Electric Vehicles  (Tayebeh Bahreini, Nathan Fisher, Daniel Grosu)....Pages 711-726
 The Optimization of Self-interference in Wideband Full-Duplex Phased Array with Joint Transmit and Receive Beamforming  (XiaoXin Wang, Zhipeng Jiang, Wenguo Yang, Suixiang Gao)....Pages 727-740
Front Matter ....Pages 741-741
 Oriented Coloring of msp-Digraphs and Oriented Co-graphs (Extended Abstract)  (Frank Gurski, Dominique Komander, Marvin Lindemann)....Pages 743-758
 Star-Critical Ramsey Number of Large Cycle and Book  (Yan Li, Yusheng Li, Ye Wang)....Pages 759-765
 Computing Imbalance-Minimal Orderings for Bipartite Permutation Graphs and Threshold Graphs  (Jan Gorzny)....Pages 766-779
 Inductive Graph Invariants and Algorithmic Applications  (C. R. Subramanian)....Pages 780-801
 Constructing Order Type Graphs Using an Axiomatic Approach  (Sergey Bereg, Mohammadreza Haghpanah)....Pages 802-816
 FISSION: A Practical Algorithm for Computing Minimum Balanced Node Separators  (Johannes Blum, Ruoying Li, Sabine Storandt)....Pages 817-832
Back Matter ....Pages 833-834