rdf-syntax-grammar
mods:
  schema location: http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-2.xsd
  title info:
    title: Online algorithms
  name:
    name part: Vaze, Rahul
    role:
      role term: creator
    role:
      role term: author.
  type of resource: text
  genre: bibliography
  origin info:
    place:
      place term: enk
    date issued: 2023
    copyright date: 2023
    issuance: monographic
  language:
    language term: eng
  physical description:
    form: print
    extent: xxii, 465 pages : illustrations ; 24 cm.
  abstract: 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.
  table of contents: Ski-rental -- List accessing -- Bin-packing -- Paging -- Metrical task system -- Secretary problem -- Knapsack -- Bipartite matching -- Primal-dual technique -- Facility location and k-Means clustering -- Load balancing -- Scheduling to minimize flow time (delay) -- Scheduling with speed scaling -- Scheduling to minimize energy with job deadlines -- Travelling salesman -- Convex optimization (server provisioning in cloud computing) -- Multi-commodity flow routing -- Resource constrained scheduling (energy harvesting communication) -- Submodular partitioning for welfare maximization.
  note: Rahul Vaze.
  note: Includes bibliographical references and index.
  subject:
    topic: Online algorithms
  classification: QA76.9.A43 V38 2023
  classification: 518/.1
  identifier: 9781009349185
  identifier: 100934918X
  identifier: 9781009349178
  identifier: 2023028776
  record info:
    record content source: DLC
    record creation date: 230920
    record change date: 20240320155412.0
    record identifier: in00004781586