Combinatorial Optimization and Applications: 13th International Conference, COCOA 2019, Xiamen, China, December 13–15, 2019, Proceedings

Front Matter ....Pages i-x
 Exact Algorithms for the Bounded Repetition Longest Common Subsequence Problem  (Yuichi Asahiro, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, Tadatoshi Utashima)....Pages 1-12
 Improved Bounds for Two Query Adaptive Bitprobe Schemes Storing Five Elements  (Mirza Galib Anwarul Husain Baig, Deepanjan Kesh)....Pages 13-25
 Critical Rows of Almost-Factorable Matrices  (Peter Ballen)....Pages 26-38
 Minimum-Width Drawings of Phylogenetic Trees  (Juan Jose Besa, Michael T. Goodrich, Timothy Johnson, Martha C. Osegueda)....Pages 39-55
 Balanced Connected Subgraph Problem in Geometric Intersection Graphs  (Sujoy Bhore, Satyabrata Jana, Supantha Pandit, Sasanka Roy)....Pages 56-68
 Approximating Bounded Job Start Scheduling with Application in Royal Mail Deliveries Under Uncertainty  (Jeremy T. Bradley, Dimitrios Letsios, Ruth Misener, Natasha Page)....Pages 69-81
 Contact Representations of Directed Planar Graphs in 2D and 3D  (Chun-Hsiang Chan, Hsu-Chun Yen)....Pages 82-93
 Identifying Structural Hole Spanners in Social Networks via Graph Embedding  (Sijie Chen, Ziwei Quan, Yong Liu)....Pages 94-106
 The Price of Anarchy for the Load Balancing Game with a Randomizing Scheduler  (Xujin Chen, Xiaodong Hu, Xiaoying Wu)....Pages 107-118
 A Randomized Approximation Algorithm for Metric Triangle Packing  (Yong Chen, Zhi-Zhong Chen, Guohui Lin, Lusheng Wang, An Zhang)....Pages 119-129
 Approximation Algorithms for Maximally Balanced Connected Graph Partition  (Yong Chen, Zhi-Zhong Chen, Guohui Lin, Yao Xu, An Zhang)....Pages 130-141
 Edge Exploration of a Graph by Mobile Agent  (Amit Kumar Dhar, Barun Gorain, Kaushik Mondal, Shaswati Patra, Rishi Ranjan Singh)....Pages 142-154
 Fast Diameter Computation Within Split Graphs  (Guillaume Ducoffe, Michel Habib, Laurent Viennot)....Pages 155-167
 Approximate Shortest Paths in Polygons with Violations  (Binayak Dutta, Sasanka Roy)....Pages 168-180
 Parametrized Runtimes for Label Tournaments  (Stefan Funke, Sabine Storandt)....Pages 181-196
 The k-Delivery Traveling Salesman Problem: Revisited  (Jinxiang Gan, Guochuan Zhang)....Pages 197-209
 Algorithmic Pricing for the Partial Assignment  (Guichen Gao, Li Ning, Hing-Fung Ting, Yong Zhang, Yifei Zou)....Pages 210-222
 Recognizing the Tractability in Big Data Computing  (Xiangyu Gao, Jianzhong Li, Dongjing Miao, Xianmin Liu)....Pages 223-234
 A Novel Virtual Traffic Light Algorithm Based on V2V for Single Intersection in Vehicular Networks  (Longjiang Guo, De Wang, Peng Li, Lichen Zhang, Meirei Ren, Hong Liu et al.)....Pages 235-251
 Characterizations for Special Directed Co-graphs  (Frank Gurski, Dominique Komander, Carolin Rehs)....Pages 252-264
 Scheduling Game with Machine Modification in the Random Setting  (Chaoyu He, Zhiyi Tan)....Pages 265-276
 Tracking Histogram of Attributes over Private Social Data in Data Markets  (Zaobo He, Yan Huang)....Pages 277-288
 Feature Selection Based on Graph Structure  (Zhiwei Hu, Zhaogong Zhang, Zongchao Huang, Dayuan Zheng, Ziliang Zhang)....Pages 289-302
 Algorithms and Hardness Results for the Maximum Balanced Connected Subgraph Problem  (Yasuaki Kobayashi, Kensuke Kojima, Norihide Matsubara, Taiga Sone, Akihiro Yamamoto)....Pages 303-315
 A Fast Exact Algorithm for Airplane Refueling Problem  (Jianshu Li, Xiaoyin Hu, Junjie Luo, Jinchuan Cui)....Pages 316-327
 Approximation Algorithm and Incentive Ratio of the Selling with Preference  (Pan Li, Qiang Hua, Zhijun Hu, Hing-Fung Ting, Yong Zhang)....Pages 328-339
 Car-Sharing Problem: Online Scheduling with Flexible Advance Bookings  (Haodong Liu, Kelin Luo, Yinfeng Xu, Huili Zhang)....Pages 340-351
 Improved Approximation Algorithm for Minimum Weight k-Subgraph Cover Problem  (Pengcheng Liu, Xiaohui Huang, Zhao Zhang)....Pages 352-361
 A True \\(O(n\\log {n})\\) Algorithm for the All-k-Nearest-Neighbors Problem  (Hengzhao Ma, Jianzhong Li)....Pages 362-374
 Approximation Algorithms for Some Minimum Postmen Cover Problems  (Yuying Mao, Wei Yu, Zhaohui Liu, Jiafeng Xiong)....Pages 375-386
 New Results on a Family of Geometric Hitting Set Problems in the Plane  (Joseph S. B. Mitchell, Supantha Pandit)....Pages 387-399
 Two-Machine Flow Shop Scheduling Problem Under Linear Constraints  (Kameng Nip, Zhenbo Wang)....Pages 400-411
 Some Graph Optimization Problems with Weights Satisfying Linear Constraints  (Kameng Nip, Zhenbo Wang, Tianning Shi)....Pages 412-424
 On the Hardness of Some Geometric Optimization Problems with Rectangles  (Supantha Pandit)....Pages 425-436
 On Vertex-Edge and Independent Vertex-Edge Domination  (Subhabrata Paul, Keshav Ranjan)....Pages 437-448
 The Balanced Connected Subgraph Problem: Complexity Results in Bounded-Degree and Bounded-Diameter Graphs  (Benoit Darties, Rodolphe Giroudeau, König Jean-Claude, Valentin Pollet)....Pages 449-460
 Card-Based Secure Ranking Computations  (Ken Takashima, Yuta Abe, Tatsuya Sasaki, Daiki Miyahara, Kazumasa Shinagawa, Takaaki Mizuki et al.)....Pages 461-472
 Improved Stretch Factor of Delaunay Triangulations of Points in Convex Position  (Xuehou Tan, Charatsanyakul Sakthip, Bo Jiang)....Pages 473-484
 Solving \\((k-1)\\)-Stable Instances of k-terminal cut with Isolating Cuts  (Mark Velednitsky)....Pages 485-495
 A Task Assignment Approach with Maximizing User Type Diversity in Mobile Crowdsensing  (Ana Wang, Lichen Zhang, Longjiang Guo, Meirui Ren, Peng Li, Bin Yan)....Pages 496-506
 Cake Cutting with Single-Peaked Valuations  (Chenhao Wang, Xiaoying Wu)....Pages 507-516
 The One-Cop-Moves Game on Graphs of Small Treewidth  (Lusheng Wang, Boting Yang)....Pages 517-528
 Bounded Degree Graphs Computed for Traveling Salesman Problem Based on Frequency Quadrilaterals  (Yong Wang)....Pages 529-540
 Prediction Based Reverse Auction Incentive Mechanism for Mobile Crowdsensing System  (Zhen Wang, Jinghua Zhu, Doudou Li)....Pages 541-552
 PATRON: A Unified Pioneer-Assisted Task RecommendatiON Framework in Realistic Crowdsourcing System  (Yuchen Xia, Zhitian Xu, Xiaofeng Gao, Mo Chi, Guihai Chen)....Pages 553-564
 Sequence Submodular Maximization Meets Streaming  (Ruiqi Yang, Dachuan Xu, Longkun Guo, Dongmei Zhang)....Pages 565-575
 Graph Simplification for Infrastructure Network Design  (Sean Yaw, Richard S. Middleton, Brendan Hoover)....Pages 576-589
 TNT: An Effective Method for Finding Correlations Between Two Continuous Variables  (Dayuan Zheng, Zhaogong Zhang, Yuting Zhang)....Pages 590-600
 On Conflict-Free Chromatic Guarding of Simple Polygons  (Onur Çağırıcı, Subir Kumar Ghosh, Petr Hliněný, Bodhayan Roy)....Pages 601-612
Back Matter ....Pages 613-614