Experimental Algorithms

1. Front Matter

   PDF

2. Reducing Splaying by Taking Advantage of Working Sets

   • Timo Aho, Tapio Elomaa, Jussi Kujala

   Pages 1-13

3. Engineering Burstsort: Towards Fast In-Place String Sorting

   • Ranjan Sinha, Anthony Wirth

   Pages 14-27

4. Comparing Integer Data Structures for 32 and 64 Bit Keys

   • Nicholas Nash, David Gregg

   Pages 28-42

5. A New Graph-Theoretical Model for k-Dimensional Guillotine-Cutting Problems

   • François Clautiaux, Antoine Jouglet, Aziz Moukrim

   Pages 43-54

6. Layer-Free Upward Crossing Minimization

   • Markus Chimani, Carsten Gutwenger, Petra Mutzel, Hoi-Ming Wong

   Pages 55-68

7. On the Efficiency of a Local Iterative Algorithm to Compute Delaunay Realizations

   • Kevin M. Lillis, Sriram V. Pemmaraju

   Pages 69-86

8. Computing Branch Decomposition of Large Planar Graphs

   • Zhengbing Bian, Qian-Ping Gu

   Pages 87-100

9. 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

10. Computing Multiple Watchman Routes

    • Eli Packer

    Pages 114-128

11. Engineering Parallel In-Place Random Generation of Integer Permutations

    • Jens Gustedt

    Pages 129-141

12. Parallel Partition Revisited

    • Leonor Frias, Jordi Petit

    Pages 142-153

13. Broadword Implementation of Rank/Select Queries

    • Sebastiano Vigna

    Pages 154-168

14. Efficient Implementations of Heuristics for Routing and Wavelength Assignment

    • Thiago F. Noronha, Mauricio G. C. Resende, Celso C. Ribeiro

    Pages 169-180

15. Myopic Distributed Protocols for Singleton and Independent-Resource Congestion Games

    • Dimitris Kalles, Alexis C. Kaporis, Paul G. Spirakis

    Pages 181-193

16. 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

17. 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

18. Fast Local Search for the Maximum Independent Set Problem

    • Diogo V. Andrade, Mauricio G. C. Resende, Renato F. Werneck

    Pages 220-234

19. Optimal University Course Timetables and the Partial Transversal Polytope

    • Gerald Lach, Marco E. Lübbecke

    Pages 235-248

20. A Basic Toolbox for Constrained Quadratic 0/1 Optimization

    • Christoph Buchheim, Frauke Liers, Marcus Oswald

    Pages 249-262

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.

• algorithm
• algorithmic mathematics
• algorithmics
• algorithms
• algorithms analysis
• algorithms design
• algorithms implementation
• approximation algorithms
• case study
• combinatorial mathematics
• combinatorial optimization
• computational geomet
• design
• optimization
• structured analysis
• algorithm analysis and problem complexity
• data structures

Policies and ethics