Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I

Description

The two-volume set LNCS 10627 and 10628 constitutes the refereed proceedings of the 11th International Conference on Combinatorial Optimization and Applications, COCOA 2017, held in Shanghai, China, in December 2017. The 59 full papers and 19 short papers presented were carefully reviewed and selected from 145 submissions. The papers cover most aspects of theoretical computer science and combinatorics related to computing, including classic combinatorial optimization, geometric optimization, complexity and data structures, and graph theory. They are organized in topical sections on network, approximation algorithm and graph theory, combinatorial optimization, game theory, and applications. Front Matter ....Pages I-XVIII Front Matter ....Pages 1-1 Filtering Undesirable Flows in Networks (Gleb Polevoy, Stojan Trajanovski, Paola Grosso, Cees de Laat)....Pages 3-17 A Framework for Overall Storage Overflow Problem to Maximize the Lifetime in WSNs (Guoliang Song, Chen Zhang, Chuang Liu, Yuna Chai)....Pages 18-32 Floorplans with Columns (Katsuhisa Yamanaka, Md. Saidur Rahman, Shin-Ichi Nakano)....Pages 33-40 A Parallel Construction of Vertex-Disjoint Spanning Trees with Optimal Heights in Star Networks (Shih-Shun Kao, Jou-Ming Chang, Kung-Jui Pai, Jinn-Shyong Yang, Shyue-Ming Tang, Ro-Yu Wu)....Pages 41-55 Protein Mover’s Distance: A Geometric Framework for Solving Global Alignment of PPI Networks (Manni Liu, Hu Ding)....Pages 56-69 On the Profit-Maximizing for Transaction Platforms in Crowd Sensing (Xi Luo, Jialiang Lu, Guangshuo Chen, Linghe Kong, Min-You Wu)....Pages 70-84 A New Approximation Algorithm for the Maximum Stacking Base Pairs Problem from RNA Secondary Structures Prediction (Aizhong Zhou, Haitao Jiang, Jiong Guo, Daming Zhu)....Pages 85-92 Front Matter ....Pages 93-93 Approximation Algorithms for the Generalized Stacker Crane Problem (Jianping Li, Xiaofei Liu, Weidong Li, Li Guan, Junran Lichen)....Pages 95-102 Fast Approximation Algorithms for Computing Constrained Minimum Spanning Trees (Pei Yao, Longkun Guo)....Pages 103-110 Trajectory-Based Multi-hop Relay Deployment in Wireless Networks (Shilei Tian, Haotian Wang, Sha Li, Fan Wu, Guihai Chen)....Pages 111-118 A Local Search Approximation Algorithm for a Squared Metric k-Facility Location Problem (Dongmei Zhang, Dachuan Xu, Yishui Wang, Peng Zhang, Zhenning Zhang)....Pages 119-124 Combinatorial Approximation Algorithms for Spectrum Assignment Problem in Chain and Ring Networks (Guangting Chen, Lei Zhang, An Zhang, Yong Chen)....Pages 125-132 Mixed Connectivity of Random Graphs (Ran Gu, Yongtang Shi, Neng Fan)....Pages 133-140 Conflict-Free Connection Numbers of Line Graphs (Bo Deng, Wenjing Li, Xueliang Li, Yaping Mao, Haixing Zhao)....Pages 141-151 The Coloring Reconfiguration Problem on Specific Graph Classes (Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou)....Pages 152-162 Front Matter ....Pages 163-163 Minimizing Total Completion Time of Batch Scheduling with Nonidentical Job Sizes (Rongqi Li, Zhiyi Tan, Qianyu Zhu)....Pages 165-179 New Insights for Power Edge Set Problem (Benoit Darties, Annie Chateau, Rodolphe Giroudeau, Mathias Weller)....Pages 180-194 Extended Spanning Star Forest Problems (Kaveh Khoshkhah, Mehdi Khosravian Ghadikolaei, Jérôme Monnot, Dirk Oliver Theis)....Pages 195-209 Faster and Enhanced Inclusion-Minimal Cograph Completion (Christophe Crespelle, Daniel Lokshtanov, Thi Ha Duong Phan, Eric Thierry)....Pages 210-224 Structure of Towers and a New Proof of the Tight Cut Lemma (Nanao Kita)....Pages 225-239 On the Complexity of Detecting k-Length Negative Cost Cycles (Longkun Guo, Peng Li)....Pages 240-250 A Refined Characteristic of Minimum Contingency Set for Conjunctive Query (Dongjing Miao, Zhipeng Cai)....Pages 251-264 Generalized Pyramidal Tours for the Generalized Traveling Salesman Problem (Michael Khachay, Katherine Neznakhina)....Pages 265-277 The 2-Median Problem on Cactus Graphs with Positive and Negative Weights (Chunsong Bai, Liying Kang)....Pages 278-285 The Eigen-Distribution of Weighted Game Trees (Shohei Okisaka, Weiguang Peng, Wenjuan Li, Kazuyuki Tanaka)....Pages 286-297 A Spectral Partitioning Algorithm for Maximum Directed Cut Problem (Zhenning Zhang, Donglei Du, Chenchen Wu, Dachuan Xu, Dongmei Zhang)....Pages 298-312 Better Approximation Ratios for the Single-Vehicle Scheduling Problems on Tree/Cycle Networks (Yuanxiao Wu, Xiwen Lu)....Pages 313-323 An Efficient Primal-Dual Algorithm for Fair Combinatorial Optimization Problems (Viet Hung Nguyen, Paul Weng)....Pages 324-339 Efficient Algorithms for Ridesharing of Personal Vehicles (Qian-Ping Gu, Jiajian Leo Liang, Guochuan Zhang)....Pages 340-354 Cost-Sharing Mechanisms for Selfish Bin Packing (Chenhao Zhang, Guochuan Zhang)....Pages 355-368 Front Matter ....Pages 369-369 Modelling and Solving Anti-aircraft Mission Planning for Defensive Missile Battalions (Trang T. Nguyen, Trung Q. Bui, Bang Q. Nguyen, Su T. Le)....Pages 371-385 Perspectives of Big Data Analysis in Urban Railway Planning: Shenzhen Metro Case Study (Keke Peng, Caiwei Yuan, Wen Xu)....Pages 386-400 Cloning Automata: Simulation and Analysis of Computer Bacteria (Chu Chen, Zhenhua Duan, Cong Tian, Hongwei Du)....Pages 401-416 Research on Arrival Integration Method for Point Merge System in Tactical Operation (Yannan Qi, Xinglong Wang, Chen Chen)....Pages 417-425 Repair Position Selection for Inconsistent Data (Xianmin Liu, Yingshu Li, Jianzhong Li)....Pages 426-438 Unbounded One-Way Trading on Distributions with Monotone Hazard Rate (Francis Y. L. Chin, Francis C. M. Lau, Haisheng Tan, Hing-Fung Ting, Yong Zhang)....Pages 439-449 Generalized Bidirectional Limited Magnitude Error Correcting Code for MLC Flash Memories (Akram Hussain, Xinchun Yu, Yuan Luo)....Pages 450-461 Optimal Topology Design of High Altitude Platform Based Maritime Broadband Communication Networks (Jianli Duan, Tiange Zhao, Bin Lin)....Pages 462-470 On Adaptive Bitprobe Schemes for Storing Two Elements (Deepanjan Kesh)....Pages 471-479 Back Matter ....Pages 481-483