Improved combination of online algorithms for acceptance and rejection
Given two admission control algorithms that are <i>c<inf>A</inf></i>-accept-competitive and <i>c<inf>R</inf></i>-reject-competitive respectively, we give two ways to make an algorithm that is simultaneously <i>O</i>(<i>c<inf>A</inf></i>)-accept-competitive and <i>O</i>(<i>c<inf>A</inf></i><i>c<inf>R</inf></i>)-reject-competitive. The combined algorithms make no reference to the offline optimal solution. In addition, one of the algorithms does not require knowing the value of either <i>c<inf>A</inf></i> or <i>c<inf>R</inf></i>. This improves on work of Azar, Blum, and Mansour, whose combined algorithm was <i>O</i>(<i>c<sup>2</sup><inf>A</inf></i>)-accept-competitive, involved computing offline optimal solutions, and required knowing the values of both <i>c<inf>A</inf></i> and <i>c<inf>R</inf></i>.