Randomisation in Online Algorithms, Load Balancing and other Dynamic Problems

计算机被用来解决现实世界中出现的各种问题。其中一些问题是静态的。计算机得到一些固定的输入，如街道地图、当前位置和目的地。有了这些信息，至少在原则上，就很容易计算出到达目的地的最快路线。然而，许多问题不是静态的，而是动态的。这主要是由于我们通常没有或很少有关于未来事件的信息，比如在我们预先计算的路线上突然发生交通堵塞。导航系统应该能够对这些不可预见的事件做出反应。计算必须持续进行，解决方案必须不断调整以适应当前情况，尽管以前的决定可能是次优的，但它们不能逆转。虽然不可能避免错误的决定，但目标是至少将它们的负面影响降到最低。本研究的目的是提供策略来处理具有某种动态方面的问题，并研究如何使用随机化来获得良好的解决方案。要研究的动态问题的范围从实践中的具体问题到在许多任务中作为子问题出现的更抽象的问题。

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.