Experimental Algorithms
7th International Workshop, WEA 2008 Provincetown, MA, USA, May/June 2008 ProceedingsCatherine C. McGeoch (Ed.)
This book constitutes the refereed proceedings of the 7th International Workshop on Experimental and Efficient Algorithms, WEA 2008, held in Provincetown, MA, USA, in May/June 2008. The 26 revised full papers were carefully reviewed and selected from numerous submissions and present current research on experimental evaluation and engineering of algorithms, as well as in various aspects of computational optimization and its applications. Special focus is put on the use of experimental methods to guide the design, analysis, implementation, and evaluation of algorithms, heuristics, and optimization programs.
Reducing Splaying by Taking Advantage of Working Sets - Timo Aho, Tapio Elomaa, Jussi Kujala - Pages 1-13
Engineering Burstsort: Towards Fast In-Place String Sorting - Ranjan Sinha, Anthony Wirth - Pages 14-27
Comparing Integer Data Structures for 32 and 64 Bit Keys - Nicholas Nash, David Gregg - Pages 28-42
A New Graph-Theoretical Model for k-Dimensional Guillotine-Cutting Problems - François Clautiaux, Antoine Jouglet, Aziz Moukrim - Pages 43-54
Layer-Free Upward Crossing Minimization - Markus Chimani, Carsten Gutwenger, Petra Mutzel, Hoi-Ming Wong - Pages 55-68
On the Efficiency of a Local Iterative Algorithm to Compute Delaunay Realizations - Kevin M. Lillis, Sriram V. Pemmaraju - Pages 69-86
Computing Branch Decomposition of Large Planar Graphs - Zhengbing Bian, Qian-Ping Gu - Pages 87-100
Experimental Evaluation of an Exact Algorithm for the Orthogonal Art Gallery Problem - Marcelo C. Couto, Cid C. de Souza, Pedro J. de Rezende - Pages 101-113
Computing Multiple Watchman Routes - Eli Packer - Pages 114-128
Engineering Parallel In-Place Random Generation of Integer Permutations - Jens Gustedt - Pages 129-141
Parallel Partition Revisited - Leonor Frias, Jordi Petit - Pages 142-153
Broadword Implementation of Rank/Select Queries - Sebastiano Vigna - Pages 154-168
Efficient Implementations of Heuristics for Routing and Wavelength Assignment - Thiago F. Noronha, Mauricio G. C. Resende, Celso C. Ribeiro - Pages 169-180
Myopic Distributed Protocols for Singleton and Independent-Resource Congestion Games - Dimitris Kalles, Alexis C. Kaporis, Paul G. Spirakis - Pages 181-193
When to Reap and When to Sow – Lowering Peak Usage with Realistic Batteries - Amotz Bar-Noy, Yi Feng, Matthew P. Johnson, Ou Liu - Pages 194-207
Characterizing the Performance of Flash Memory Storage Devices and Its Impact on Algorithm Design - Deepak Ajwani, Itay Malinger, Ulrich Meyer, Sivan Toledo - Pages 208-219
Fast Local Search for the Maximum Independent Set Problem - Diogo V. Andrade, Mauricio G. C. Resende, Renato F. Werneck - Pages 220-234
Optimal University Course Timetables and the Partial Transversal Polytope - Gerald Lach, Marco E. Lübbecke - Pages 235-248
A Basic Toolbox for Constrained Quadratic 0/1 Optimization - Christoph Buchheim, Frauke Liers, Marcus Oswald - Pages 249-262
Empirical Investigation of Simplified Step-Size Control in Metaheuristics with a View to Theory - Jens Jägersküpper, Mike Preuss - Pages 263-274
Reconstructing Phylogenetic Networks with One Recombination - Ernst Althaus, Rouven Naujoks - Pages 275-288
Exact Algorithms for Cluster Editing: Evaluation and Experiments - Sebastian Böcker, Sebastian Briesemeister, Gunnar W. Klau - Pages 289-302
Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm - Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, Dorothea Wagner - Pages 303-318
Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks - Robert Geisberger, Peter Sanders, Dominik Schultes, Daniel Delling - Pages 319-333
Bidirectional A?*? Search for Time-Dependent Fast Paths - Giacomo Nannicini, Daniel Delling, Leo Liberti, Dominik Schultes - Pages 334-346
Multi-criteria Shortest Paths in Time-Dependent Train Networks - Yann Disser, Matthias Müller–Hannemann, Mathias Schnee - Pages 347-361
Springer, Lecture Notes in Computer Science - Volume 5038, Paperback, english, 361 pages
