Approximating the optimal algorithm for online scheduling problems via dynamic programming

Lin Chen, Deshi Ye, Guochuan Zhang

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

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|rj, (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 Cmax and Rm∑Pi Cpi , 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∥Cmax 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.

Original languageEnglish
Article number1540011
JournalAsia-Pacific Journal of Operational Research
Volume32
Issue number1
DOIs
StatePublished - Feb 25 2015

Keywords

  • Competitive analysis
  • dynamic programming
  • online scheduling

Fingerprint Dive into the research topics of 'Approximating the optimal algorithm for online scheduling problems via dynamic programming'. Together they form a unique fingerprint.

Cite this