000			03507nam a22003257a 4500
001			23337054
003			IIITD
005			20240510164904.0
006			m |o d |
007			cr_|||||||||||
008			230920s2023 enk ob 001 0 eng
010			_a 2023028777
020			_a9781009349185
040			_aIIITD
042			_apcc
082	0	0	_a518.1 _bVAZ-O
100	1		_aVaze, Rahul
245	1	0	_aOnline algorithms _cby Rahul Vaze.
260			_aNew York : _bCambridge University Press, _c©2023
300			_axxii, 465 p. : _bill. ; _c24 cm.
504			_aIncludes bibliographical references and index.
505	0		_aSki-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.
520			_a"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 analyse 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, travelling salesman, are also covered. A very useful technique for analysing 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"--
650		0	_aOnline algorithms.
650		0	_aalgorithms.
776	0	8	_iPrint version: _aVaze, Rahul. _tOnline algorithms _dCambridge ; New York, NY : Cambridge University Press, 2023 _z9781009349185 _w(DLC) 2023028776
906			_a7 _bcbc _corignew _d1 _eecip _f20 _gy-gencatlg
942			_2ddc _cBK
999			_c172560 _d172560