Abstract
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 $\Theta(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.
Users
Please
log in to take part in the discussion (add own reviews or comments).