Randomisation in Online Algorithms, Load Balancing and other Dynamic Problems

在线算法、负载平衡和其他动态问题中的随机化

• 批准号: EP/F043333/1
• 负责人: Matthias Englert
• 金额: $ 26.04万
• 依托单位: University of Warwick
• 依托单位国家: 英国
• 项目类别: Fellowship
• 财政年份: 2008
• 资助国家: 英国
• 起止时间: 2008 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FF043333%2F1
• 关键词: Randomisation; Online; Algorithms; Load; Balancing

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.

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

项目成果

Economical Caching

• DOI: 10.1145/2493246.2493247
• 发表时间: 2013-07
• 作者: Matthias Englert;Heiko Röglin;J. Spönemann;Berthold Vöcking

An O (log k )-competitive algorithm for generalized caching

用于广义缓存的 O (log k ) 竞争算法

• DOI: 10.1137/1.9781611973099.133
• 发表时间: 2012
• 作者: Adamaszek A

Catch them if you can

如果可以的话抓住他们

• DOI: 10.1145/2422436.2422489
• 发表时间: 2013
• 作者: Cygan M

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings

近似、随机化和组合优化。

• DOI: 10.1007/978-3-642-15369-3_12
• 发表时间: 2010
• 作者: Englert M

Almost tight bounds for reordering buffer management

重新排序缓冲区管理的几乎严格限制

• DOI: 10.1145/1993636.1993717
• 发表时间: 2011
• 作者: Adamaszek A