Randomisation in Online Algorithms, Load Balancing and other Dynamic Problems
Lead Research Organisation:
University of Warwick
Department Name: Computer Science
Abstract
Computers are used to solve all kinds of problems emerging in the real world. Some of these problems are static. The computer is given some fixed input like a street map, the current location, and a destination. With these information it is, at least in principle, easy to calculate the fastest route to the destination.However, many problems are not static but dynamic. This is mostly due to the fact that we usually have no or very little information about future events like a sudden traffic jam on our pre-calculated route.A navigation system should be able to react to such unforeseeable events. The computation has to be ongoing and the solution has to be incessantly adjusted to the current situation and although previous decisions may turn out to be suboptimal, they cannot be reverted. Although it is impossible to avoid wrong decisions, the goal is to at least minimise the negative impact they have. The aim of this research is to give strategies to deal with problems that have some kind of dynamic aspect to them and study how randomisation can be used to obtain good solutions. The range of dynamic problems to be studied goes from concrete problems from practise to more abstract problems that emerge as sub-problems in numerous tasks.
Organisations
People |
ORCID iD |
| Matthias Englert (Principal Investigator) |
Publications
Adamaszek A
(2011)
Almost tight bounds for reordering buffer management
Adamaszek A
(2022)
Almost Tight Bounds for Reordering Buffer Management
in SIAM Journal on Computing
Adamaszek A
(2012)
Optimal online buffer scheduling for block devices
Adamaszek A
(2012)
An O (log k )-competitive algorithm for generalized caching
Azar Y.
(2014)
Generalized reordering buffer management
in Leibniz International Proceedings in Informatics, LIPIcs
Cygan M
(2013)
Catch them if you can
Englert M
(2014)
The Power of Reordering for Online Minimum Makespan Scheduling
in SIAM Journal on Computing
Englert M
(2009)
Stochastic Algorithms: Foundations and Applications
Englert M
(2014)
Vertex Sparsifiers: New Results from Old Techniques
in SIAM Journal on Computing
| Description | Computers and algorithms are playing an essential role in solving problems emerging in the real world. Many of these natural problems are of static nature: the computer is given some fixed input (like a street map, the current location, and a destination) that ought to be efficiently processed. With this information it is, at least in principle, easy to calculate the fastest route to the destination. This is the typical way in which algorithmic problems have been traditionally set up, and where the researchers have been concentrating their efforts for many decades. Nowadays however, we have to cope with more complex problems: many problems arising in modern applications are not static, but are of dynamic nature. This is mostly due to the fact that we usually have none or very little information about future events, like, for example, unexpected traffic works, a traffic accident, or a sudden traffic jam on our pre-calculated route, or, as an example from another area of applications: a financial crisis of a bank. We need modern algorithms to be able to efficiently deal with such unforeseeable events. The computation has to be often ongoing and the solution has to be continually adjusted to the current situation; for example, and this is a common feature of such algorithms, although previous decisions may turn out to be suboptimal, they cannot be reverted. Although it is impossible to avoid wrong decisions, the goal is to at least minimize the negative impact they have. The aim of this research is to study efficient algorithmic strategies to deal with problems of dynamic nature. We want to understand the way how decisions have to be made, how to make them efficiently (quickly) using algorithms, and how to ensure that the obtained solutions are of good quality. Our focus is on problems of dynamic nature for routing and traffic planning problems, and for scheduling problems. To see the flavor of the challenges, think about the following questions. How should we set up low congestion routing paths for traffic in data or street networks, if we do not know anything about the traffic patterns in advance? If we do not know what data will be needed next on a computer, what data should we keep in the small but fast access memory of a computer and what data should be kept on the slow hard disk instead? If we need 1000 EUR but do not know anything about future exchange rates, at what points in time should we exchange it to GBP? These are some broad descriptions of question addressed in this project. |
| Exploitation Route | The research outputs have been cited frequently. Highlights include a result on vertex sparsification which was subsequently used by others to make advances on a wide range of other problems. Lee, Mendel, and Moharrami use our results to show an approximate version of the Okamura-Seymour theorem. Chekuri, Shepherd, and Weibel also use our results to investigate problems related to the Okamura-Seymour theorem. Chuzhoy et al. provide a new efficient algorithm, which relies on our techniques, for the edge-connectivity k-route cut problem. Another example is our work on Generalized Caching which resolved a long-standing open question. This result was used by Epstein, Imreh, Levin, and Nagy-Gyorgy (Haifa, Szeged, and The Technion) to vastly simplify a proof in their work on a related problem. The techniques were also instrumental for our later paper demonstrating optimal bounds for a different scheduling problem. This in turn was partly built on by Avigdor-Elgrabli and Rabani (Hebrew University of Jerusalem) to solve yet another related fundamental scheduling problem that was open for over a decade. |
| Sectors | Digital/Communication/Information Technologies (including Software),Other |
| Description | As this is foundational research, its impact is most likely indirect rather than direct. The problems studied are, among other things, motivated by problems emerging in the management of information system memory components and information system networks. A deeper understanding of these problems should eventually lead to advances in these areas, e.g., in improved cache management strategies in operating systems and more advanced routing strategies for special large computer networks. Advances in our understanding of the problems studied here (like e.g. caching) |