Experimental Algorithms: 7th International Workshop, WEA 2008 Provincetown, MA, USA, May 30-June 1, 2008 Proceedings

Timo Aho, Tapio Elomaa, Jussi Kujala (auth.), Catherine C. McGeoch (eds.)3540685480, 9783540685487

The Workshop on Experimental Algorithms, WEA, is intended to be an int- national forum for research on the experimental evaluation and engineering of algorithms, as well as in various aspects of computational optimization and its applications. The emphasis of the workshop is the use of experimental me- ods to guide the design, analysis, implementation, and evaluation of algorithms, heuristics, and optimization programs. WEA 2008 was held at the Provincetown Inn, Provincetown, MA, USA, on May 30 – June 1, 2008. This was the seventh workshop of the series, after Rome (2007),Menorca(2006),Santorini(2005),RiodeJaniero(2004),Asconia(2003), and Riga (2001). This volume contains all contributed papers accepted for presentation at the workshop. The 26 contributed papers were selected by the Program Committee onthebasisofatleastthreerefereereports,somecontributedbytrustedexternal referees. In addition to the 26 contributed papers, the program contained two invited talks. Camil Demetrescu, of the University of Rome “La Sapienza,” spoke on “Visualization in Algorithm Engineering.” David S. Johnson of AT & T Labs – Research, gave a talk on “Bin Packing: From Theory to Experiment and Back Again.” We would like to thank the authors who responded to the call for papers, our invited speakers, the members of the ProgramCommittee, the external referees, and the Organizing Committee members for making this workshop possible.

---

Table of contents :
Front Matter….Pages –
Reducing Splaying by Taking Advantage of Working Sets….Pages 1-13
Engineering Burstsort: Towards Fast In-Place String Sorting….Pages 14-27
Comparing Integer Data Structures for 32 and 64 Bit Keys….Pages 28-42
A New Graph-Theoretical Model for k -Dimensional Guillotine-Cutting Problems….Pages 43-54
Layer-Free Upward Crossing Minimization….Pages 55-68
On the Efficiency of a Local Iterative Algorithm to Compute Delaunay Realizations….Pages 69-86
Computing Branch Decomposition of Large Planar Graphs….Pages 87-100
Experimental Evaluation of an Exact Algorithm for the Orthogonal Art Gallery Problem….Pages 101-113
Computing Multiple Watchman Routes….Pages 114-128
Engineering Parallel In-Place Random Generation of Integer Permutations….Pages 129-141
Parallel Partition Revisited….Pages 142-153
Broadword Implementation of Rank/Select Queries….Pages 154-168
Efficient Implementations of Heuristics for Routing and Wavelength Assignment….Pages 169-180
Myopic Distributed Protocols for Singleton and Independent-Resource Congestion Games….Pages 181-193
When to Reap and When to Sow – Lowering Peak Usage with Realistic Batteries….Pages 194-207
Characterizing the Performance of Flash Memory Storage Devices and Its Impact on Algorithm Design….Pages 208-219
Fast Local Search for the Maximum Independent Set Problem….Pages 220-234
Optimal University Course Timetables and the Partial Transversal Polytope….Pages 235-248
A Basic Toolbox for Constrained Quadratic 0/1 Optimization….Pages 249-262
Empirical Investigation of Simplified Step-Size Control in Metaheuristics with a View to Theory….Pages 263-274
Reconstructing Phylogenetic Networks with One Recombination….Pages 275-288
Exact Algorithms for Cluster Editing: Evaluation and Experiments….Pages 289-302
Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm….Pages 303-318
Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks….Pages 319-333
Bidirectional A  ∗  Search for Time-Dependent Fast Paths….Pages 334-346
Multi-criteria Shortest Paths in Time-Dependent Train Networks….Pages 347-361
Back Matter….Pages –