论文标题
在在线问题中实现竞争力
Achieving Competitiveness in Online Problems
论文作者
论文摘要
在在线算法的设置中，输入最初不存在，而是随着时间的推移和每次输入之后一对一到达，该算法必须做出决定。根据问题的提出，可以允许该算法在以后更改其先前的决定。我们分析了两个问题，以表明在线算法可以通过改变其以前的决策来提高竞争力。我们首先考虑边缘一对一到达空图的在线边缘方向，其目的是以使最大程度的最大程度的最大程度的方式定向。然后，我们考虑在线双方B匹配。在此问题中，我们给我们提供了一个两分图，最初存在图形的一侧以及另一侧在线到达的位置。目的是保持匹配集，以使集合中的最高度最小化。对于这两个问题，当决策不可逆转时，最佳可实现的竞争比是N输入到达的$θ（\ log n）$。我们研究了这些问题的三种算法，两个算法是前者的三个算法，另一种是通过更改N到达的O（1）的竞争比。除此之外，我们还针对对手分析了一种算法，最短的路径算法。通过此，我们证明了有关算法性能的一些新结果。
In the setting of online algorithms, the input is initially not present but rather arrive one-by-one over time and after each input, the algorithm has to make a decision. Depending on the formulation of the problem, the algorithm might be allowed to change its previous decisions or not at a later time. We analyze two problems to show that it is possible for an online algorithm to become more competitive by changing its former decisions. We first consider the online edge orientation in which the edges arrive one-by-one to an empty graph and the aim is to orient them in a way such that the maximum in-degree is minimized. We then consider the online bipartite b-matching. In this problem, we are given a bipartite graph where one side of the graph is initially present and where the other side arrive online. The goal is to maintain a matching set such that the maximum degree in the set is minimized. For both of the problems, the best achievable competitive ratio is $Θ(\log n)$ over n input arrivals when decisions are irreversible. We study three algorithms for these problems, two for the former and one for the latter, that achieve O(1) competitive ratio by changing O(n) of their decisions over n arrivals. In addition to that, we analyze one of the algorithms, the shortest path algorithm, against an adversary. Through that, we prove some new results about algorithms performance.
