Online algorithms /
Online algorithms are an optimization paradigm where input is revealed sequentially and an algorithm has to make irrevocable decisions using only causal information. This is a growing area of research with great interest from the theoretical computer science community, having significant practical a...
| Main Author: | |
|---|---|
| Format: | Book |
| Language: | English |
| Published: |
Cambridge ; New York :
Cambridge University Press,
[2023].
|
| Subjects: |
| Summary: | Online algorithms are an optimization paradigm where input is revealed sequentially and an algorithm has to make irrevocable decisions using only causal information. This is a growing area of research with great interest from the theoretical computer science community, having significant practical applications in operations research, big data analysis, design of communication networks and so on. There are many different mathematical techniques that have been developed to analyze online algorithms, such as potential function arguments, primal-dual methods and Yao's principle, to name a few. This textbook presents an easy but rigorous introduction to online algorithms for students. It starts with classical online paradigms like the ski rental, paging, list-accessing and bin packing, where performance of the algorithms is studied under the worst-case input and moves on to newer paradigms like 'beyond worst case', where online algorithms are augmented with predictions using machine learning algorithms. Several other popular online problems, such as metrical task systems, which includes the popular k-server problem as a special case, secretary, knapsack, bipartite matching, load balancing, scheduling to minimize flow-time, facility location, k-means clustering, and travelling salesman, are also covered. A very useful technique for analyzing online algorithms called the primal-dual schema is also included together with its application for multiple problems. The book goes on to cover multiple applied problems such as routing in communication networks, server provisioning in cloud systems, communication with energy harvested from renewable sources and sub-modular partitioning. Finally, a wide range of solved examples and practice exercises are included, allowing hands-on exposure to the concepts. Each exercise has been broken down into simpler parts to provide a clear path towards the solution. |
|---|---|
| Physical Description: | xxii, 465 pages : illustrations ; 24 cm. |
| Bibliography: | Includes bibliographical references and index. |
| ISBN: | 9781009349185 100934918X |