Experimental and Efficient Algorithms: 4th International Workshop, WEA 2005, Santorini Island, Greece, May 10-13, 2005. Proceedings

Christos H. Papadimitriou (auth.), Sotiris E. Nikoletseas (eds.)3540259201, 9783540259206

This book constitutes the refereed proceedings of the 4th International Workshop on Experimental and Efficient Algorithms, WEA 2005, held in Santorini Island, Greece in May 2005.

The 47 revised full papers and 7 revised short papers presented together with extended abstracts of 3 invited talks were carefully reviewed and selected from 176 submissions. The book is devoted to the design, analysis, implementation, experimental evaluation, and engineering of efficient algorithms. Among the application areas addressed are most fields applying advanced algorithmic techniques, such as combinatorial optimization, approximation, graph theory, discrete mathematics, scheduling, searching, sorting, string matching, coding, networking, data mining, data analysis, etc.

---

Table of contents :
Front Matter….Pages –
Tα Π αι δí α Π α í ζε ι The Interaction Between Algorithms and Game Theory….Pages 1-3
Using an Adaptive Memory Strategy to Improve a Multistart Heuristic for Sequencing by Hybridization….Pages 4-15
High-Performance Algorithm Engineering for Large-Scale Graph Problems and Computational Biology….Pages 16-21
The “Real” Approximation Factor of the MST Heuristic for the Minimum Energy Broadcasting….Pages 22-31
Implementing Minimum Cycle Basis Algorithms….Pages 32-43
Rounding to an Integral Program….Pages 44-54
Rectangle Covers Revisited Computationally….Pages 55-66
Don’t Compare Averages….Pages 67-76
Experimental Results for Stackelberg Scheduling Strategies….Pages 77-88
An Improved Branch-and-Bound Algorithm for the Test Cover Problem….Pages 89-100
Degree-Based Treewidth Lower Bounds….Pages 101-112
Inferring AS Relationships: Dead End or Lively Beginning?….Pages 113-125
Acceleration of Shortest Path and Constrained Shortest Path Computation….Pages 126-138
A General Buffer Scheme for the Windows Scheduling Problem….Pages 139-151
Implementation of Approximation Algorithms for the Multicast Congestion Problem….Pages 152-164
Frequency Assignment and Multicoloring Powers of Square and Triangular Meshes….Pages 165-176
From Static Code Distribution to More Shrinkage for the Multiterminal Cut….Pages 177-188
Partitioning Graphs to Speed Up Dijkstra’s Algorithm….Pages 189-202
Efficient Convergence to Pure Nash Equilibria in Weighted Network Congestion Games….Pages 203-215
New Upper Bound Heuristics for Treewidth….Pages 216-227
Accelerating Vickrey Payment Computation in Combinatorial Auctions for an Airline Alliance….Pages 228-239
Algorithm Engineering for Optimal Graph Bipartization….Pages 240-252
Empirical Analysis of the Connectivity Threshold of Mobile Agents on the Grid….Pages 253-264
Multiple-Winners Randomized Tournaments with Consensus for Optimization Problems in Generic Metric Spaces….Pages 265-276
On Symbolic Scheduling Independent Tasks with Restricted Execution Times….Pages 277-289
A Simple Randomized k -Local Election Algorithm for Local Computations….Pages 290-301
Generating and Radiocoloring Families of Perfect Graphs….Pages 302-314
Efficient Implementation of Rank and Select Functions for Succinct Representation….Pages 315-327
Comparative Experiments with GRASP and Constraint Programming for the Oil Well Drilling Problem….Pages 328-340
A Framework for Probabilistic Numerical Evaluation of Sensor Networks: A Case Study of a Localization Protocol….Pages 341-353
A Cut-Based Heuristic to Produce Almost Feasible Periodic Railway Timetables….Pages 354-366
GRASP with Path-Relinking for the Weighted Maximum Satisfiability Problem….Pages 367-379
New Bit-Parallel Indel-Distance Algorithm….Pages 380-390
Dynamic Application Placement Under Service and Memory Constraints….Pages 391-402
Integrating Coordinated Checkpointing and Recovery Mechanisms into DSM Synchronization Barriers….Pages 403-414
Synchronization Fault Cryptanalysis for Breaking A5/1….Pages 415-427
An Efficient Algorithm for δ -Approximate Matching with α -Bounded Gaps in Musical Sequences….Pages 428-439
The Necessity of Timekeeping in Adversarial Queueing….Pages 440-451
BDDs in a Branch and Cut Framework….Pages 452-463
Parallel Smith-Waterman Algorithm for Local DNA Comparison in a Cluster of Workstations….Pages 464-475
Fast Algorithms for Weighted Bipartite Matching….Pages 476-487
A Practical Minimal Perfect Hashing Method….Pages 488-500
Efficient and Experimental Meta-heuristics for MAX-SAT Problems….Pages 501-512
Experimental Evaluation of the Greedy and Random Algorithms for Finding Independent Sets in Random Graphs….Pages 513-523
Local Clustering of Large Graphs by Approximate Fiedler Vectors….Pages 524-533
Almost FPRAS for Lattice Models of Protein Folding….Pages 534-544
Vertex Cover Approximations: Experiments and Observations….Pages 545-557
GRASP with Path-Relinking for the Maximum Diversity Problem….Pages 558-569
How to Splay for loglog N -Competitiveness….Pages 570-579
Distilling Router Data Analysis for Faster and Simpler Dynamic IP Lookup Algorithms….Pages 580-592
Optimal Competitive Online Ray Search with an Error-Prone Robot….Pages 593-596
An Empirical Study for Inversions-Sensitive Sorting Algorithms….Pages 597-601
Approximation Algorithm for Chromatic Index and Edge-Coloring of Multigraphs….Pages 602-605
Finding, Counting and Listing All Triangles in Large Graphs, an Experimental Study….Pages 606-609
Selecting the Roots of a Small System of Polynomial Equations by Tolerance Based Matching….Pages 610-613
Developing Novel Statistical Bandwidths for Communication Networks with Incomplete Information….Pages 614-617
Dynamic Quality of Service Support in Virtual Private Networks….Pages 618-621
Back Matter….Pages –