Algorithm Engineering: Bridging the Gap Between Algorithm Theory and Practice (Lecture Notes in Computer Science, 5971)

Algorithms are essential building blocks of computer applications. However, advancements in computer hardware, which render traditional computer models more and more unrealistic, and an ever increasing demand for efficient solution to actual real world problems have led to a rising gap between classical algorithm theory and algorithmics in practice. The emerging discipline of Algorithm Engineering aims at bridging this gap. Driven by concrete applications, Algorithm Engineering complements theory by the benefits of experimentation and puts equal emphasis on all aspects arising during a cyclic solution process ranging from realistic modeling, design, analysis, robust and efficient implementations to careful experiments. This tutorial - outcome of a GI-Dagstuhl Seminar held in Dagstuhl Castle in September 2006 - covers the essential aspects of this process in ten chapters on basic ideas, modeling and design issues, analysis of algorithms, realistic computer models, implementation aspects and algorithmic software libraries, selected case studies, as well as challenges in Algorithm Engineering. Both researchers and practitioners in the field will find it useful as a state-of-the-art survey. Front matter 1 Chapter 1 14 Chapter 1. Foundations of Algorithm Engineering 14 Introduction 14 Classical Algorithmics 14 The New Paradigm: Algorithm Engineering 15 Towards a Definition of Algorithm Engineering 17 Methodology 18 Visibility of Algorithm Engineering 19 Building Blocks of Algorithm Engineering 20 Modeling of Problems 21 Algorithm Design 22 Analysis 22 Realistic Computer Models 23 Implementation 24 Libraries 25 Experiments 25 Success Stories of Algorithm Engineering 26 Challenges 28 Further Topics — Not Covered in This Book 28 Chapter 2 29 Chapter 2. Modeling 29 Introduction 29 Modeling Fundamentals 32 Fundamentals 32 Problem Analysis 34 Problem Specification: Examples 36 Modeling a Solution Approach 39 Model Assessment 41 Inherent Difficulties within the Modeling Process 41 Modeling Frameworks 43 Graph-Based Models 44 Mixed Integer Programming 48 Constraint Programming 56 Algebraic Modeling Languages 62 Summary on Modeling Frameworks 66 Further Issues 66 Specific Input Characteristics 68 Problem Decomposition for Complex Applications 68 Conclusion 69 Chapter 3 71 Chapter 3. Selected Design Issues 71 Introduction 71 Simplicity 73 Advantages for Implementation 74 How to Achieve Simplicity? 74 Effects on Analysis 78 Scalability 80 Towards a Definition of Scalability 81 Scalability in Parallel Computing 83 Basic Techniques for Designing Scalable Algorithms 86 Scalability in Grid Computing and Peer-to-Peer Networks 89 Time-Space Trade-Offs 93 Formal Methods 95 Reuse and Lookup Tables 97 Time-Space Trade-Offs in Storing Data 102 Preprocessing 105 Brute Force Support 106 Robustness 108 Software Engineering Aspects 109 Numerical Robustness Issues 121 Robustness in Computational Geometry 126 Chapter 4 140 Chapter 4. Analysis of Algorithms 140 Introduction and Motivation 140 Worst-Case and Average-Case Analysis 143 Worst-Case Analysis 144 Average-Case Analysis 145 Amortized Analysis 147 Aggregate Analysis 149 The Accounting Method 149 The Potential Method 149 Online Algorithms and Data Structures 151 Smoothed Analysis 153 Smoothed Analysis of Binary Optimization Problems 154 Smoothed Analysis of the Simplex Algorithm 164 Conclusions and Open Questions 171 Realistic Input Models 172 Computational Geometry 173 Definitions and Notations 175 Geometric Input Models 175 Relationships between the Models 176 Applications 177 Computational Testing 181 Representative Operation Counts 182 Identifying Representative Operations 183 Applications of Representative Operation Counts 184 Experimental Study of Asymptotic Performance 186 Performance Analysis Inspired by the Scientific Method 188 Empirical Curve Bounding Rules 191 Conclusions on the Experimental Study of Asymptotic Performance 204 Conclusions 205 Chapter 5 207 Chapter 5. Realistic Computer Models 207 Introduction 207 Large Data Sets 207 RAM Model 209 Real Architecture 209 Disadvantages of the RAM Model 211 Future Trends 212 Realistic Computer Models 212 Exploiting the Memory Hierarchy 213 Memory Hierarchy Models 213 Fundamental Techniques 216 External Memory Data Structures 219 Cache-Aware Optimization 222 Cache-Oblivious Algorithms 227 Cache-Oblivious Data Structures 230 Parallel Computing Models 231 PRAM 232 Network Models 233 Bridging Models 233 Recent Work 236 Application and Comparison 238 Simulating Parallel Algorithms for I/O-Efficiency 242 PRAM Simulation 242 Coarse-Grained Parallel Simulation Results 243 Success Stories of Algorithms for Memory Hierarchies 246 Cache-Oblivious Sorting 246 External Memory BFS 246 External Suffix Array Construction 247 External A*-Search 247 Parallel Bridging Model Libraries 248 Conclusion 248 Chapter 6 250 Chapter 6. Implementation Aspects 250 Introduction 250 Correctness 252 Motivation and Description 252 Testing 252 Checking 255 Verification 258 Debugging 259 Efficiency 261 Implementation Tricks – Tuning the Algorithms 263 Implementation Tricks – Tuning the Code 267 Code Generation 272 Flexibility 275 Achieving Flexibility 276 Ease of Use 280 Interface Design 280 Documentation and Readability 281 Literate Programming 284 Implementing Efficiently 286 Reuse 286 Programming Language 286 Development Environment 288 Avoiding Errors 288 Versioning 289 Geometric Algorithms 289 Correctness: Exact Number Types 291 Efficiency: Floating-Point Filters and Other Techniques 293 Easy to Use: The Number Types CORE::Expr and leda::real 299 Chapter 7 303 Chapter 7. Libraries 303 Introduction 303 Library Overview 305 Libraries as Building Blocks 310 Basic Design Goals and Paradigms of Combinatorial and Geometric Libraries 312 Fundamental Operations 315 Memory Management 315 Iterators versus Items 316 Parameterization of Data Types 317 Callbacks and Functors 318 Advanced Number Types 319 Basic Data Structures and Algorithms 322 Data Structures 322 Algorithms 323 Summary and Comparison 327 Graph Data Structures and Algorithms 327 Data Structures 327 Node and Edge Data 328 Algorithms 329 Summary and Comparison 331 Computational Geometry 332 Kernels and Exact Number Types 332 Low-Level Issues in Geometric Kernels 334 Functionality 335 Performance 336 Conclusion 337 Chapter 8 338 Chapter 8. Experiments 338 Introduction 338 Example Scenarios 338 The Importance of Experiments 340 The Experimentation Process 342 Planning Experiments 344 Introduction 345 Measures 346 Factors and Sampling Points 348 Advanced Techniques 350 Test Data Generation 352 Properties to Have in Mind 352 Three Types of Test Instances 355 What Instances to Use 359 Test Data Libraries 360 Properties of a Perfect Library 360 The Creation of a Library 362 Maintenance and Update of a Library 363 Examples of Existing Libraries 364 Setting-Up and Running the Experiment 366 Setup-Phase 367 Running-Phase 373 Supplementary Advice 377 Evaluating Your Data 380 Graphical Analysis 381 Statistical Analysis 388 Pitfalls for Data Analysis 394 Reporting Your Results 395 Principles for Reporting 395 Presenting Data in Diagrams and Tables 399 Chapter 9 402 Chapter 9. Case Studies 402 Introduction 402 Shortest Paths 403 Phase I: “Theory” (1959 – 1999) 405 Phase II: Speed-Up Techniques for P2P (1999 – 2005) 407 Phase III: Road Networks (2005 – 2008) 411 Phase IV: New Challenges on P2P (Since 2008) 416 Conclusions 420 Steiner Trees 420 Progress with Exact Algorithms 423 Approximation Algorithms and Heuristics 435 Conclusions 439 Voronoi Diagrams 440 Nearest Neighbor Regions 441 Applications 443 Algorithms 444 The Implementation Quest 447 The Exact Geometric Computation Paradigm for the Computation of Voronoi diagrams 447 Topology-Oriented Inexact Approaches 451 Available Implementations 453 Conclusions 457 Chapter 10 459 Chapter 10. Challenges in Algorithm Engineering 459 Challenges for the Algorithm Engineering Discipline 459 Realistic Hardware Models 460 Challenges in the Application Modeling and Design Phase 461 Challenges in the Analysis Phase 462 Challenges in the Implementation Phase 462 Challenges in the Experimentation Phase 463 Increase the Community! 465 Epilogue 466 Back matter 467 Annotation Algorithms are essential building blocks of computer applications. However, advancements in computer hardware, which render traditional computer models more and more unrealistic, and an ever increasing demand for efficient solution to actual real world problems have led to arising gap between classical algorithm theory and algorithmics in practice. The emerging discipline of Algorithm Engineering aims at bridging this gap. Driven by concrete applications, Algorithm Engineering complements theory by the benefits of experimentation and puts equal emphasis on all aspects arising during a cyclic solution process ranging from realistic modeling, design, analysis, robust and efficient implementations to careful experiments. This tutorial - outcome of a GI-Dagstuhl Seminar held in Dagstuhl Castle in September 2006 - covers the essential aspects of this process in ten chapters on basic ideas, modeling and design issues, analysis of algorithms, realistic computer models, implementation aspects andalgorithmic software libraries, selected case studies, as well as challenges in Algorithm Engineering. Both researchers and practitioners in the field will find it useful as a state-of-the-art survey Front Matter....Pages - Chapter 1. Foundations of Algorithm Engineering....Pages 1-15 Chapter 2. Modeling....Pages 16-57 Chapter 3. Selected Design Issues....Pages 58-126 Chapter 4. Analysis of Algorithms....Pages 127-193 Chapter 5. Realistic Computer Models....Pages 194-236 Chapter 6. Implementation Aspects....Pages 237-289 Chapter 7. Libraries....Pages 290-324 Chapter 8. Experiments....Pages 325-388 Chapter 9. Case Studies....Pages 389-445 Chapter 10. Challenges in Algorithm Engineering....Pages 446-453 Back Matter....Pages -