Experimental and Efficient Algorithms

Contenu

Invited Talks.- T? ??? ?í ? ??í?? ? The Interaction Between Algorithms and Game Theory.- Using an Adaptive Memory Strategy to Improve a Multistart Heuristic for Sequencing by Hybridization.- High-Performance Algorithm Engineering for Large-Scale Graph Problems and Computational Biology.- Contributed Regular Papers.- The "Real" Approximation Factor of the MST Heuristic for the Minimum Energy Broadcasting.- Implementing Minimum Cycle Basis Algorithms.- Rounding to an Integral Program.- Rectangle Covers Revisited Computationally.- Don't Compare Averages.- Experimental Results for Stackelberg Scheduling Strategies.- An Improved Branch-and-Bound Algorithm for the Test Cover Problem.- Degree-Based Treewidth Lower Bounds.- Inferring AS Relationships: Dead End or Lively Beginning?.- Acceleration of Shortest Path and Constrained Shortest Path Computation.- A General Buffer Scheme for the Windows Scheduling Problem.- Implementation of Approximation Algorithms for the Multicast Congestion Problem.- Frequency Assignment and Multicoloring Powers of Square and Triangular Meshes.- From Static Code Distribution to More Shrinkage for the Multiterminal Cut.- Partitioning Graphs to Speed Up Dijkstra's Algorithm.- Efficient Convergence to Pure Nash Equilibria in Weighted Network Congestion Games.- New Upper Bound Heuristics for Treewidth.- Accelerating Vickrey Payment Computation in Combinatorial Auctions for an Airline Alliance.- Algorithm Engineering for Optimal Graph Bipartization.- Empirical Analysis of the Connectivity Threshold of Mobile Agents on the Grid.- Multiple-Winners Randomized Tournaments with Consensus for Optimization Problems in Generic Metric Spaces.- On Symbolic Scheduling Independent Tasks with Restricted Execution Times.- A Simple Randomized k-Local Election Algorithm for Local Computations.- Generating and Radiocoloring Families of Perfect Graphs.- Efficient Implementation of Rank and Select Functions for Succinct Representation.- Comparative Experiments with GRASP and Constraint Programming for the Oil Well Drilling Problem.- A Framework for Probabilistic Numerical Evaluation of Sensor Networks: A Case Study of a Localization Protocol.- A Cut-Based Heuristic to Produce Almost Feasible Periodic Railway Timetables.- GRASP with Path-Relinking for the Weighted Maximum Satisfiability Problem.- New Bit-Parallel Indel-Distance Algorithm.- Dynamic Application Placement Under Service and Memory Constraints.- Integrating Coordinated Checkpointing and Recovery Mechanisms into DSM Synchronization Barriers.- Synchronization Fault Cryptanalysis for Breaking A5/1.- An Efficient Algorithm for ?-Approximate Matching with ?-Bounded Gaps in Musical Sequences.- The Necessity of Timekeeping in Adversarial Queueing.- BDDs in a Branch and Cut Framework.- Parallel Smith-Waterman Algorithm for Local DNA Comparison in a Cluster of Workstations.- Fast Algorithms for Weighted Bipartite Matching.- A Practical Minimal Perfect Hashing Method.- Efficient and Experimental Meta-heuristics for MAX-SAT Problems.- Experimental Evaluation of the Greedy and Random Algorithms for Finding Independent Sets in Random Graphs.- Local Clustering of Large Graphs by Approximate Fiedler Vectors.- Almost FPRAS for Lattice Models of Protein Folding.- Vertex Cover Approximations: Experiments and Observations.- GRASP with Path-Relinking for the Maximum Diversity Problem.- How to Splay for loglogN-Competitiveness.- Distilling Router Data Analysis for Faster and Simpler Dynamic IP Lookup Algorithms.- Contributed Short Papers.- Optimal Competitive Online Ray Search with an Error-Prone Robot.- An Empirical Study for Inversions-Sensitive Sorting Algorithms.- Approximation Algorithm for Chromatic Index and Edge-Coloring of Multigraphs.- Finding, Counting and Listing All Triangles in Large Graphs, an Experimental Study.- Selecting the Roots of a Small System of Polynomial Equations by Tolerance Based Matching.- Developing Novel Statistical Bandwidths for Communication Networks with Incomplete Information.- Dynamic Quality of Service Support in Virtual Private Networks.