Experimental and Efficient Algorithms: Third International Workshop, WEA 2004, Angra dos Reis, Brazil, May 25-28, 2004. Proceedings

Adriana C. F. Alvim, Celso C. Ribeiro (auth.), Celso C. Ribeiro, Simone L. Martins (eds.)3540220674, 9783540220671, 9783540248385

This book constitutes the refereed proceedings of the Third International Workshop on Experimental and Efficient Algorithms, WEA 2004, held in Angra dos Reis, Brazil in May 2004.

The 40 revised full papers presented together with abstracts of two invited talks were carefully reviewed and selected from numerous submissions. The book is devoted to the areas of design, analysis, and experimental evaluation of algorithms. Among the topics covered are scheduling, heuristics, combinatorial optimization, evolutionary optimization, graph computations, labeling, robot navigation, shortest path algorithms, flow problems, searching, randomization and derandomization, string matching, graph coloring, networking, error detecting codes, timetabling, sorting, energy minimization, etc.

---

Table of contents :
Front Matter….Pages –
A Hybrid Bin-Packing Heuristic to Multiprocessor Scheduling….Pages 1-13
Efficient Edge-Swapping Heuristics for Finding Minimum Fundamental Cycle Bases….Pages 14-29
Solving Chance-Constrained Programs Combining Tabu Search and Simulation….Pages 30-41
An Algorithm to Identify Clusters of Solutions in Multimodal Optimisation….Pages 42-56
On an Experimental Algorithm for Revenue Management for Cargo Airlines….Pages 57-71
Cooperation between Branch and Bound and Evolutionary Approaches to Solve a Bi-objective Flow Shop Problem….Pages 72-86
Simple Max-Cut for Split-Indifference Graphs and Graphs with Few P 4 ’s….Pages 87-99
A Randomized Heuristic for Scene Recognition by Graph Matching….Pages 100-113
An Efficient Implementation of a Joint Generation Algorithm….Pages 114-128
Lempel, Even, and Cederbaum Planarity Method….Pages 129-144
A Greedy Approximation Algorithm for the Uniform Labeling Problem Analyzed by a Primal-Dual Technique….Pages 145-158
Distributed Circle Formation for Anonymous Oblivious Robots….Pages 159-174
Dynamic Programming and Column Generation Based Approaches for Two-Dimensional Guillotine Cutting Problems….Pages 175-190
Engineering Shortest Path Algorithms….Pages 191-198
How to Tell a Good Neighborhood from a Bad One: Satisfiability of Boolean Formulas….Pages 199-212
Implementing Approximation Algorithms for the Single-Source Unsplittable Flow Problem….Pages 213-227
Fingered Multidimensional Search Trees….Pages 228-242
Faster Deterministic and Randomized Algorithms on the Homogeneous Set Sandwich Problem….Pages 243-252
Efficient Implementation of the BSP/CGM Parallel Vertex Cover FPT Algorithm….Pages 253-268
Combining Speed-Up Techniques for Shortest-Path Computations….Pages 269-284
Increased Bit-Parallelism for Approximate String Matching….Pages 285-298
The Role of Experimental Algorithms in Genomics….Pages 299-300
A Fast Algorithm for Constructing Suffix Arrays for Fixed-Size Alphabets….Pages 301-314
Pre-processing and Linear-Decomposition Algorithm to Solve the k-Colorability Problem….Pages 315-325
An Experimental Study of Unranking Algorithms….Pages 326-340
An Improved Derandomized Approximation Algorithm for the Max-Controlled Set Problem….Pages 341-355
GRASP with Path-Relinking for the Quadratic Assignment Problem….Pages 356-368
Finding Minimum Transmission Radii for Preserving Connectivity and Constructing Minimal Spanning Trees in Ad Hoc and Sensor Networks….Pages 369-382
A Dynamic Algorithm for Topologically Sorting Directed Acyclic Graphs….Pages 383-398
Approximating Interval Coloring and Max-Coloring in Chordal Graphs….Pages 399-416
A Statistical Approach for Algorithm Selection….Pages 417-431
An Improved Time-Sensitive Metaheuristic Framework for Combinatorial Optimization….Pages 432-445
A Huffman-Based Error Detecting Code….Pages 446-457
Solving Diameter Constrained Minimum Spanning Tree Problems in Dense Graphs….Pages 458-467
An Efficient Tabu Search Heuristic for the School Timetabling Problem….Pages 468-481
Experimental Studies of Symbolic Shortest-Path Algorithms….Pages 482-497
Experimental Comparison of Greedy Randomized Adaptive Search Procedures for the Maximum Diversity Problem….Pages 498-512
Using Compact Tries for Cache-Efficient Sorting of Integers….Pages 513-528
Using Random Sampling to Build Approximate Tries for Efficient String Sorting….Pages 529-544
The Datapath Merging Problem in Reconfigurable Systems: Lower Bounds and Heuristic Evaluation….Pages 545-558
An Analytical Model for Energy Minimization….Pages 559-569
A Heuristic for Minimum-Width Graph Layering with Consideration of Dummy Nodes….Pages 570-583
Back Matter….Pages –