Approximating the optimal algorithm for online scheduling problems via dynamic programming

Very recently Günther et al. [E. Günther, O. Maurer, N. Megow and A. Wiese (2013). A new approach to online scheduling: Approximating the optimal competitive ratio. In Proc. 24th Annual ACM-SIAM Symp. Discrete Algorithms (SODA).] initiate a new systematic way of studying online problems by introducing the competitive ratio approximation scheme (simplified as competitive schemes in this paper), which is a class of algorithms {A^ε| ε > 0} with a competitive ratio at most ρ∗(1 + ε), where ρ∗is the best possible competitive ratio over all online algorithms. Along this line, Günther et al. [E. Günther, O. Maurer, N. Megow and A. Wiese (2013). A new approach to online scheduling: Approximating the optimal competitive ratio. In Proc. 24th Annual ACM-SIAM Symp. Discrete Algorithms (SODA).] provide competitive schemes for several online over time scheduling problems like Qm|r_j, (pmtn)| ε _jcj, while the running times are polynomial if the number of machines is a constant. In this paper, we consider the classical online scheduling problems, where jobs arrive in a list. We present competitive schemes for Rm C_max and Rm∑P_i C^p_i , where the running times are polynomial if the number of machines is a constant. Specifically, we are able to derive a competitive scheme for P∥C_max which runs in polynomial time even if the number of machines is an input. Our method is novel and more efficient than that of Günther et al. [E. Günther, O. Maurer, N. Megow and A. Wiese (2013). A new approach to online scheduling: Approximating the optimal competitive ratio. In Proc. 24th Annual ACM-SIAM Symp. Discrete Algorithms (SODA).] Indeed, by utilizing the standard rounding technique for the off-line scheduling problems, we reformulate the online scheduling problem into a game on an infinite graph, through which we arrive at the following key point: Assuming that the best competitive ratio is ρ∗, for any online algorithm there exists a list of a polynomial number of jobs showing that its competitive ratio is at least ρ∗- O(ε). Interestingly such a result is achieved via a dynamic programming algorithm. Our framework is also applicable to other online problems.