Frontiers in Algorithmics: 13th International Workshop, FAW 2019, Sanya, China, April 29 – May 3, 2019, Proceedings

Description

This book constitutes the proceedings of the 13th International Workshop on Frontiers in Algorithmics, FAW 2019, held in Sanya, China, in April/May 2019. The 15 full papers presented in this volume were carefully reviewed and selected from 21 submissions. The workshop provides a focused forum on current trends of research on algorithms, discrete structures, and their applications, and brings together international experts at the research frontiers in these areas to exchange ideas and to present significant new results. Front Matter ....Pages i-x A Polynomial Time Algorithm for Fair Resource Allocation in Resource Exchange (Xiang Yan, Wei Zhu)....Pages 1-13 A Local Search 4/3-approximation Algorithm for the Minimum 3-path Partition Problem (Yong Chen, Randy Goebel, Guohui Lin, Longcheng Liu, Bing Su, Weitian Tong et al.)....Pages 14-25 Efficient Guarding of Polygons and Terrains (Pradeesha Ashok, Meghana M. Reddy)....Pages 26-37 Graph Orientation with Edge Modifications (Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono, Sandhya T. P.)....Pages 38-50 Local Coloring: New Observations and New Reductions (Jie You, Yixin Cao, Jianxin Wang)....Pages 51-62 Secure Computation of Any Boolean Function Based on Any Deck of Cards (Kazumasa Shinagawa, Takaaki Mizuki)....Pages 63-75 A Novel Business Model for Electric Car Sharing (Yukun Cheng, Xiaotie Deng, Mengqian Zhang)....Pages 76-87 Constructing Three Completely Independent Spanning Trees in Locally Twisted Cubes (Kung-Jui Pai, Ruay-Shiung Chang, Jou-Ming Chang, Ro-Yu Wu)....Pages 88-99 Read-Once Resolutions in Horn Formulas (Hans Kleine Büning, P. Wojciechowski, K. Subramani)....Pages 100-110 Vertex-Critical (\(P_5\), banner)-Free Graphs (Qingqiong Cai, Shenwei Huang, Tao Li, Yongtang Shi)....Pages 111-120 An FPTAS for Stochastic Unbounded Min-Knapsack Problem (Zhihao Jiang, Haoyu Zhao)....Pages 121-132 The Inapproximability of k-DominatingSet for Parameterized \(\mathsf {{AC}^0}\) Circuits (Wenxing Lai)....Pages 133-143 Mutual Visibility by Robots with Persistent Memory (Subhash Bhagat, Krishnendu Mukhopadhyaya)....Pages 144-155 Pushing the Online Matrix-Vector Conjecture Off-Line and Identifying Its Easy Cases (Leszek Gąsieniec, Jesper Jansson, Christos Levcopoulos, Andrzej Lingas, Mia Persson)....Pages 156-169 An Improved Approximation Algorithm for the k-Means Problem with Penalties (Qilong Feng, Zhen Zhang, Feng Shi, Jianxin Wang)....Pages 170-181 Back Matter ....Pages 183-183