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

Generalized reordering buffer management

通用重排序缓冲区管理

• DOI: 10.4230/lipics.stacs.2014.87
• 发表时间: 2014
• 期刊: Leibniz International Proceedings in Informatics, LIPIcs
• 作者: Azar Y.