Analysis of Experimental Algorithms: Special Event, SEA² 2019, Kalamata, Greece, June 24-29, 2019, Revised Selected Papers

Description

This book constitutes the refereed post-conference proceedings of the Special Event on the Analysis of Experimental Algorithms, SEA² 2019, held in Kalamata, Greece, in June 2019. The 35 revised full papers presented were carefully reviewed and selected from 45 submissions. The papers cover a wide range of topics in both computer science and operations research/mathematical programming. They focus on the role of experimentation and engineering techniques in the design and evaluation of algorithms, data structures, and computational optimization methods. Front Matter ....Pages i-xi Voronoi Diagram of Orthogonal Polyhedra in Two and Three Dimensions (Ioannis Z. Emiris, Christina Katsamaki)....Pages 1-20 The Complexity of Subtree Intersection Representation of Chordal Graphs and Linear Time Chordal Graph Generation (Tınaz Ekim, Mordechai Shalom, Oylum Şeker)....Pages 21-34 Computing a Minimum Color Path in Edge-Colored Graphs (Neeraj Kumar)....Pages 35-50 Student Course Allocation with Constraints (Akshay Utture, Vedant Somani, Prem Krishnaa, Meghana Nasre)....Pages 51-68 A Combinatorial Branch and Bound for the Min-Max Regret Spanning Tree Problem (Noé Godinho, Luís Paquete)....Pages 69-81 Navigating a Shortest Path with High Probability in Massive Complex Networks (Jun Liu, Yicheng Pan, Qifu Hu, Angsheng Li)....Pages 82-97 Engineering a PTAS for Minimum Feedback Vertex Set in Planar Graphs (Glencora Borradaile, Hung Le, Baigong Zheng)....Pages 98-113 On New Rebalancing Algorithm (Koba Gelashvili, Nikoloz Grdzelidze, Mikheil Tutberidze)....Pages 114-124 Colorful Frontier-Based Search: Implicit Enumeration of Chordal and Interval Subgraphs (Jun Kawahara, Toshiki Saitoh, Hirofumi Suzuki, Ryo Yoshinaka)....Pages 125-141 Unit Disk Cover for Massive Point Sets (Anirban Ghosh, Brian Hicks, Ronald Shevchenko)....Pages 142-157 Improved Contraction Hierarchy Queries via Perfect Stalling (Stefan Funke, Thomas Mendel)....Pages 158-166 Constraint Generation Algorithm for the Minimum Connectivity Inference Problem (Édouard Bonnet, Diana-Elena Fălămaş, Rémi Watrigant)....Pages 167-183 Efficient Split-Radix and Radix-4 DCT Algorithms and Applications (Sirani M. Perera, Daniel Silverio, Austin Ogle)....Pages 184-201 Analysis of Max-Min Ant System with Local Search Applied to the Asymmetric and Dynamic Travelling Salesman Problem with Moving Vehicle (João P. Schmitt, Rafael S. Parpinelli, Fabiano Baldo)....Pages 202-218 Computing Treewidth via Exact and Heuristic Lists of Minimal Separators (Hisao Tamaki)....Pages 219-236 Fast Public Transit Routing with Unrestricted Walking Through Hub Labeling (Duc-Minh Phan, Laurent Viennot)....Pages 237-247 Effective Heuristics for Matchings in Hypergraphs (Fanny Dufossé, Kamer Kaya, Ioannis Panagiotas, Bora Uçar)....Pages 248-264 Approximated ZDD Construction Considering Inclusion Relations of Models (Kotaro Matsuda, Shuhei Denzumi, Kengo Nakamura, Masaaki Nishino, Norihito Yasuda)....Pages 265-282 Efficient Implementation of Color Coding Algorithm for Subgraph Isomorphism Problem (Josef Malík, Ondřej Suchý, Tomáš Valla)....Pages 283-299 Quantum-Inspired Evolutionary Algorithms for Covering Arrays of Arbitrary Strength (Michael Wagner, Ludwig Kampel, Dimitris E. Simos)....Pages 300-316 An Experimental Study of Algorithms for Geodesic Shortest Paths in the Constant-Workspace Model (Jonas Cleve, Wolfgang Mulzer)....Pages 317-331 Searching for Best Karatsuba Recurrences (Çağdaş Çalık, Morris Dworkin, Nathan Dykas, Rene Peralta)....Pages 332-342 Minimum and Maximum Category Constraints in the Orienteering Problem with Time Windows (Konstantinos Ameranis, Nikolaos Vathis, Dimitris Fotakis)....Pages 343-358 Internal Versus External Balancing in the Evaluation of Graph-Based Number Types (Hanna Geppert, Martin Wilhelm)....Pages 359-375 Hacker’s Multiple-Precision Integer-Division Program in Close Scrutiny (Jyrki Katajainen)....Pages 376-391 Assessing Algorithm Parameter Importance Using Global Sensitivity Analysis (Alessio Greco, Salvatore Danilo Riccio, Jon Timmis, Giuseppe Nicosia)....Pages 392-407 A Machine Learning Framework for Volume Prediction (Umutcan Önal, Zafeirakis Zafeirakopoulos)....Pages 408-423 Faster Biclique Mining in Near-Bipartite Graphs (Blair D. Sullivan, Andrew van der Poel, Trey Woodlief)....Pages 424-453 k-Maximum Subarrays for Small k: Divide-and-Conquer Made Simpler (Ovidiu Daescu, Hemant Malik)....Pages 454-472 A Faster Convex-Hull Algorithm via Bucketing (Ask Neve Gamby, Jyrki Katajainen)....Pages 473-489 Fixed Set Search Applied to the Minimum Weighted Vertex Cover Problem (Raka Jovanovic, Stefan Voß)....Pages 490-504 Automated Deep Learning for Threat Detection in Luggage from X-Ray Images (Alessio Petrozziello, Ivan Jordanov)....Pages 505-512 Algorithmic Aspects on the Construction of Separating Codes (Marcel Fernandez, John Livieratos)....Pages 513-526 Lagrangian Relaxation in Iterated Local Search for the Workforce Scheduling and Routing Problem (Hanyu Gu, Yefei Zhang, Yakov Zinder)....Pages 527-540 Approximation Algorithms and an Integer Program for Multi-level Graph Spanners (Reyan Ahmed, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, Faryad Darabi Sahneh, Richard Spence)....Pages 541-562 Back Matter ....Pages 563-564