Combinatorial Optimization and Applications: 12th International Conference, COCOA 2018, Atlanta, GA, USA, December 15-17, 2018, Proceedings

Front Matter ....Pages I-XIII
Front Matter ....Pages 1-1
 Fast Approximation of Centrality and Distances in Hyperbolic Graphs  (V. Chepoi, F. F. Dragan, M. Habib, Y. Vaxès, H. Alrasheed)....Pages 3-18
 Rectilinear Shortest Paths Among Transient Obstacles  (Anil Maheshwari, Arash Nouri, Jörg-Rüdiger Sack)....Pages 19-34
 An Efficient Algorithm for Enumerating Induced Subgraphs with Bounded Degeneracy  (Kunihiro Wasa, Takeaki Uno)....Pages 35-45
 Tree t-Spanners of a Graph: Minimizing Maximum Distances Efficiently  (Fernanda Couto, Luís Felipe I. Cunha)....Pages 46-61
 On the Approximability of Time Disjoint Walks  (Alexandre Bayen, Jesse Goodman, Eugene Vinitsky)....Pages 62-78
 Directed Path-Width of Sequence Digraphs  (Frank Gurski, Carolin Rehs, Jochen Rethmann)....Pages 79-93
 New Results About the Linearization of Scaffolds Sharing Repeated Contigs  (Dorine Tabary, Tom Davot, Mathias Weller, Annie Chateau, Rodolphe Giroudeau)....Pages 94-107
 Relaxation and Matrix Randomized Rounding for the Maximum Spectral Subgraph Problem  (Cristina Bazgan, Paul Beaujean, Éric Gourdin)....Pages 108-122
 Bipartite Communities via Spectral Partitioning  (Kelly B. Yancey, Matthew P. Yancey)....Pages 123-137
 Generating Algebraic Expressions for Labeled Grid Graphs  (Mark Korenblit)....Pages 138-153
 Editing Graphs to Satisfy Diversity Requirements  (Huda Chuangpishit, Manuel Lafond, Lata Narayanan)....Pages 154-168
 Computing a Rectilinear Shortest Path amid Splinegons in Plane  (Tameem Choudhury, R. Inkulu)....Pages 169-182
 Graph Problems with Obligations  (Alexis Cornet, Christian Laforest)....Pages 183-197
 Bipartizing with a Matching  (Carlos V. G. C. Lima, Dieter Rautenbach, Uéverton S. Souza, Jayme L. Szwarcfiter)....Pages 198-213
Front Matter ....Pages 215-215
 Removing Undesirable Flows by Edge Deletion  (Gleb Polevoy, Stojan Trajanovski, Paola Grosso, Cees de Laat)....Pages 217-232
 Min-Max-Flow Based Algorithm for Evacuation Network Planning in Restricted Spaces  (Yi Hong, Jiandong Liu, Chuanwen Luo, Deying Li)....Pages 233-245
 Practical and Easy-to-Understand Card-Based Implementation of Yao’s Millionaire Protocol  (Daiki Miyahara, Yu-ichi Hayashi, Takaaki Mizuki, Hideaki Sone)....Pages 246-261
 Defend the Clique-based Attack for Data Privacy  (Meng Han, Dongjing Miao, Jinbao Wang, Liyuan Liu)....Pages 262-280
 Exact Computation of Strongly Connected Reliability by Binary Decision Diagrams  (Hirofumi Suzuki, Masakazu Ishihata, Shin-ichi Minato)....Pages 281-295
Front Matter ....Pages 297-297
 Upper and Lower Bounds for Different Parameterizations of (n,3)-MAXSAT  (Tatiana Belova, Ivan Bliznets)....Pages 299-313
 Related Machine Scheduling with Machine Speeds Satisfying Linear Constraints  (Siyun Zhang, Kameng Nip, Zhenbo Wang)....Pages 314-328
 Open-Shop Scheduling for Unit Jobs Under Precedence Constraints  (An Zhang, Yong Chen, Randy Goebel, Guohui Lin)....Pages 329-340
 Makespan Minimization on Unrelated Parallel Machines with Simple Job-Intersection Structure and Bounded Job Assignments  (Daniel R. Page, Roberto Solis-Oba, Marten Maack)....Pages 341-356
 Super-Stability in the Student-Project Allocation Problem with Ties  (Sofiat Olaosebikan, David Manlove)....Pages 357-371
 Primal Dual Algorithm for Partial Set Multi-cover  (Yingli Ran, Yishuo Shi, Zhao Zhang)....Pages 372-385
 Reducing Extension Edges of Concurrent Programs for Reachability Analysis  (Cong Tian, Jiaying Wang, Zhenhua Duan, Liang Zhao)....Pages 386-401
 Robustly Assigning Unstable Items  (Ananya Christman, Christine Chung, Nicholas Jaczko, Scott Westvold, David S. Yuen)....Pages 402-420
 Hardness Results and Approximation Schemes for Discrete Packing and Domination Problems  (Raghunath Reddy Madireddy, Apurva Mudgal, Supantha Pandit)....Pages 421-435
 Approximability of Covering Cells with Line Segments  (Paz Carmi, Anil Maheshwari, Saeed Mehrabi, Luís Fernando Schultz, Xavier da Silveira)....Pages 436-448
 Heuristics for the Score-Constrained Strip-Packing Problem  (Asyl L. Hawa, Rhyd Lewis, Jonathan M. Thompson)....Pages 449-462
Front Matter ....Pages 463-463
 An Algorithm for Reducing Approximate Nearest Neighbor to Approximate Near Neighbor with \\(O(\\log {n})\\) Query Time  (Hengzhao Ma, Jianzhong Li)....Pages 465-479
 Exact and Approximate Map-Reduce Algorithms for Convex Hull  (Anirban Ghosh, Samuel Schwartz)....Pages 480-494
 Transmitting Particles in a Polygonal Domain by Repulsion  (Amirhossein Mozafari, Thomas C. Shermer)....Pages 495-508
 Does a Robot Path Have Clearance C?  (Ovidiu Daescu, Hemant Malik)....Pages 509-521
 Star Routing: Between Vehicle Routing and Vertex Cover  (Diego Delle Donne, Guido Tagliavini)....Pages 522-536
Front Matter ....Pages 537-537
 Effect of Crowd Composition on the Wisdom of Artificial Crowds Metaheuristic  (Christopher J. Lowrance, Dominic M. Larkin, Sang M. Yim)....Pages 539-551
 Analysis of Consensus Sorting via the Cycle Metric  (Ivan Avramovic, Dana S. Richards)....Pages 552-565
 On the Competitiveness of Memoryless Strategies for the k-Canadian Traveller Problem  (Pierre Bergé, Julien Hemery, Arpad Rimmel, Joanna Tomasik)....Pages 566-576
 Rent Division Among Groups  (Mohammad Ghodsi, Mohamad Latifian, Arman Mohammadi, Sadra Moradian, Masoud Seddighin)....Pages 577-591
 Sequence Sentential Decision Diagrams  (Shuhei Denzumi)....Pages 592-606
Front Matter ....Pages 607-607
 Online Unit Covering in Euclidean Space  (Adrian Dumitrescu, Anirban Ghosh, Csaba D. Tóth)....Pages 609-623
 Isolation Branching: A Branch and Bound Algorithm for the k-Terminal Cut Problem  (Mark Velednitsky, Dorit S. Hochbaum)....Pages 624-639
 Characterizing Cycle-Complete Dissimilarities in Terms of Associated Indexed 2-Hierarchies  (Kazutoshi Ando, Kazuya Shoji)....Pages 640-650
 Making Multiple RNA Interaction Practical  (Syed Ali Ahmed, Saman Farhat, Saad Mneimneh)....Pages 651-671
 Max-Min Dispersion on a Line  (Tetsuya Araki, Shin-ichi Nakano)....Pages 672-678
Front Matter ....Pages 679-679
 Integer-Programming Bounds on Pebbling Numbers of Cartesian-Product Graphs  (Franklin Kenter, Daphne Skipper)....Pages 681-695
 On the Complexity of Resilience for Aggregation Queries  (Dongjing Miao, Zhipeng Cai)....Pages 696-706
 Inefficiency of Equilibria in Doodle Polls  (Barbara M. Anthony, Christine Chung)....Pages 707-721
 Network Cost-Sharing Games: Equilibrium Computation and Applications to Election Modeling  (Rahul Swamy, Timothy Murray, Jugal Garg)....Pages 722-738
 Weak-Barrier Coverage with Adaptive Sensor Rotation  (Catalina Aranzazu-Suescun, Mihaela Cardei)....Pages 739-754
Back Matter ....Pages 755-756