2023/06/09 by Dwibedy, Debasis, Mohanty, Rakesh
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Operating Systems (cs.OS)
paper · doi:10.48550/arxiv.2306.06003
The knowledge of future partial information in the form of a lookahead to design efficient online algorithms is a theoretically-efficient and realistic approach to solving computational problems. Design and analysis of semi-online algorithms with extra-piece-of-information (EPI) as a new input parameter has gained the attention of the theoretical computer science community in the last couple of decades. Though competitive analysis is a pessimistic worst-case performance measure to analyze online algorithms, it has immense theoretical value in developing the foundation and advancing the state-of-the-art contributions in online and semi-online scheduling. In this paper, we study and explore the impact of lookahead as an EPI in the context of online scheduling in identical machine frameworks. We introduce a k-lookahead model and design improved competitive semi-online algorithms. For a 2-identical machine setting, we prove a lower bound of (4)/(3) and design an optimal algorithm with a matching upper bound of (4)/(3) on the competitive ratio. For a 3-identical machine setting, we show a lower bound of (15)/(11) and design a (16)/(11)-competitive improved semi-online algorithm.