Algorithms – ESA 2005: 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings

Front Cover
Gerth S. Brodal, Stefano Leonardi
Springer Science & Business Media, Sep 19, 2005 - Computers - 901 pages
This volume contains the 75 contributed papers and the abstracts of the three invited lectures presented at the 13th Annual European Symposium on Al- rithms (ESA 2005), held in Palma de Mallorca, Spain, October 3–6, 2005. The threedistinguishedinvitedspeakerswereGiuseppeF.Italiano,CristopherMoore and Joseph (Se?) Naor. Since 2002,ESA has consisted of two tracks, with separate programcomm- tees, which dealt respectively with – the designandmathematicalanalysis ofalgorithms(the “DesignandAna- sis” track); – real-worldapplications, engineering and experimental analysis of algorithms (the “Engineering and Applications” track). Previous ESAs in the current two track format were held in Rome, Italy (2002);Budapest,Hungary(2003);andBergen,Norway(2004).Theproceedings of these symposia were published as Springer's LNCS volumes 2461, 2832, and 3221 respectively. Papers were solicited in all areas of algorithmic research, including but not limited to algorithmic aspects of networks, approximation and on-line al- rithms, computational biology, computational geometry, computational ?nance and algorithmic game theory, data structures, database and information - trieval, external memory algorithms, graph algorithms, graph drawing, machine learning, mobile computing, pattern matching and data compression, quantum computing, and randomized algorithms. The algorithms could be sequential, distributed, or parallel. Submissions were especially encouraged in the area of mathematical programming and operations research, including combinatorial optimization, integer programming, polyhedral combinatorics, and semide?nite programming.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Designing Reliable Algorithms in Unreliable Memories
1
From Balanced Graph Partitioning to Balanced Metric Labeling
9
Quantum Computing Factoring and Graph Isomorphism
10
Exploring an Unknown Graph Efficiently
11
Online Routing in Faulty Meshes with Sublinear Comparative Time and Traffic Ratio
23
Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut
35
RelaxandCut for Capacitated Network Design
47
On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games
59
Problems?
448
Geometric Clustering to Minimize the Sum of Cluster Sizes
460
Approximation Schemes for Minimum 2Connected Spanning Subgraphs in Weighted Planar Graphs
472
Packet Routing and Information Gathering in Lines Rings and Trees
484
Jitter Regulation for Multiple Streams Extended Abstract
496
Efficient cOriented Range Searching with DOPTrees
508
Matching Point Sets with Respect to the Earth Movers Distance
520
Small Stretch Spanners on Dynamic Graphs
532

The Complexity of Games on Highly Regular Graphs
71
Does Theory Meet Practice?
83
Exploiting Sphere Cut Branch Decompositions
95
An Algorithm for the SAT Problem for Formulae of Linear Length
107
LinearTime Enumeration of Isolated Cliques
119
Finding Shortest Nonseparating and Noncontractible Cycles for Topologically Embedded Graphs
131
Delineating Boundaries for Imprecise Regions
143
Efficient and Exact Algorithms for Curves and Surfaces
155
Min Sum Clustering with Penalties
167
Improved Approximation Algorithms for Metric Max TSP
179
Unbalanced Graph Cuts
191
Low Degree Connectivity in AdHoc Networks
203
5Regular Graphs are 3Colorable with Positive Probability
215
Optimal Integer Alphabetic Trees in Linear Time
226
Predecessor Queries in Constant Time?
238
An Algorithm for NodeCapacitated Ring Routing
249
On Degree Constrained Shortest Paths
259
Extended Abstract
271
Extended Abstract
283
Space Efficient Algorithms for the BurrowsWheeler Backtransformation
293
CacheOblivious ComparisonBased Algorithms on Multisets
305
An Experimental Evaluation
317
Allocating Memory in a LockFree Manner
329
Generating Realistic Terrains with HigherOrder Delaunay Triangulations
343
IOEfficient Construction of Constrained Delaunay Triangulations
355
Convex Hull and Voronoi Diagram of Additively Weighted Points
367
New Tools and Simpler Algorithms for Branchwidth
379
Treewidth Lower Bounds with Brambles
391
Minimal Interval Completions
403
A 2Approximation Algorithm for Sorting by Prefix Reversals
415
Approximating the 2Interval Pattern Problem
426
A Loopless Gray Code for Minimal SignedBinary Representations
438
An Experimental Study of Algorithms for Fully Dynamic Transitive Closure
544
Experimental Study of Geometric tSpanners
556
Highway Hierarchies Hasten Exact Shortest Path Queries
568
Preemptive Scheduling of Independent Jobs on Identical Parallel Machines Subject to Migration Delays
580
FairnessFree Periodic Scheduling with Vacations
592
Online Bin Packing with Cardinality Constraints
604
Fast Monotone 3Approximation Algorithm for Scheduling Related Machines
616
Engineering Planar Separator Algorithms
628
Standard Template Library for XXL Data Sets
640
Negative Cycle Detection Problem
652
Monotone Boolean Functions and Game Trees
664
Online View Maintenance Under a ResponseTime Constraint
677
Online PrimalDual Algorithms for Covering and Packing Problems
689
Efficient Algorithms for Shared Backup Allocation in Networks with Partial Information
702
Using Fractional PrimalDual to Schedule Split Intervals with Demands
714
An Approximation Algorithm for the Minimum Latency Set Cover Problem
726
WorkloadOptimal Histograms on Streams
734
Finding Frequent Patterns in a String in Sublinear Time
746
Online Occlusion Culling
758
Shortest Paths in Matrix Multiplication Time Extended Abstract
770
Computing Common Intervals of K Permutations with Applications to Modular Decomposition of Graphs
779
Greedy Routing in TreeDecomposed Graphs
791
Making Chord Robust to Byzantine Attacks
803
Bucket Game with Applications to Set Multicover and Dynamic Page Migration
815
Bootstrapping a HopOptimal Network in the Weak Sensor Model
827
Approximating Integer Quadratic Programs and MAXCUT in Subdense Graphs
839
A Cutting Planes Algorithm Based Upon a Semidefinite Relaxation for the Quadratic Assignment Problem
850
Approximation Complexity of minmax Regret Versions of Shortest Path Spanning Tree and Knapsack
862
Robust Approximate Zeros Extended Abstract
874
Optimizing a 2D Function Satisfying Unimodality Properties
887
Author Index
899
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information