Experimental and Efficient Algorithms: Second International Workshop, Wea 2003, Ascona, Switzerland, May 26-28, 2003 : Proceedings

by Jansen, Klaus; Wea 200 (2003 Ascona, Switzerland); Margraf, Marian; Mastrolilli, Monaldo; Rolim, Jos D. P.

• ISBN13: 9783540402053
• ISBN10: 3540402055
• Format: Paperback
• Copyright: 2003-05-01
• Publisher: Springer Verlag

Summary

This book constitutes the refereed proceedings of the Second International Workshop on Experimental and Efficient Algorithms, WEA 2003, held in Ascona, Switzerland in May 2003. The 19 revised full papers presented together with 3 invited contributions were carefully reviewed and selected from 40 submissions. The focus of the volume is on applications of efficient algorithms for combinatorial problems.

Table of Contents

Improving Linear Programming Approaches for the Steiner Tree Problem	p. 1
Algorithms and Experiments on Colouring Squares of Planar Graphs	p. 15
Experimental Analysis of Online Algorithms for the Bicriteria Scheduling Problem	p. 33
Fast-Search: A New Efficient Variant of the Boyer-Moore String Matching Algorithm	p. 47
An On-Line Algorithm for the Rectangle Packing Problem with Rejection	p. 59
New Lower and Upper Bounds for Graph Treewidth	p. 70
Search Data Structures for Skewed Strings	p. 81
Evaluation of Basic Protocols for Optical Smart Dust Networks	p. 97
Linear Time Local Improvements for Weighted Matchings in Graphs	p. 107
Experimental Studies of Graph Traversal Algorithms	p. 120
A Nondifferentiable Optimization Approach to Ratio-Cut Partitioning	p. 134
Comparing Push- and Pull-Based Broadcasting or: Would "Microsoft Watches" Profit from a Transmitter?	p. 148
Experimental Comparison of Heuristic and Approximation Algorithms for Uncapacitated Facility Location	p. 165
A Lazy Version of Eppstein's K Shortest Paths Algorithm	p. 179
Linear Algorithm for 3-Coloring of Locally Connected Graphs	p. 191
A Clustering Algorithm for Interval Graph Test on Noisy Data	p. 195
Core Instances for Testing: A Case Study	p. 209
The Reliable Algorithmic Software Challenge RASC	p. 222
A New Class of Greedy Heuristics for Job Shop Scheduling Problems	p. 223
Algorithmic Techniques for Memory Energy Reduction	p. 237
A Framework for Designing Approximation Algorithms for Scheduling Problems	p. 253
Analysis and Visualization of Social Networks	p. 261
Author Index	p. 267
Table of Contents provided by Blackwell. All Rights Reserved.