Revisiting Online Algorithms: A Survey of Set Cover Solutions Beyond Competitive Analysis

Abstract

Online algorithms are crucial for real-time decision-making and adaptability across diverse fields, such as operations research, computer science, and combinatorics. These algorithms handle data incrementally and make decisions without prior knowledge of future inputs, thereby effectively addressing complex challenges. This study provides a comprehensive survey of online algorithms, focusing on the Set Cover problem (SC). SC is one of the most extensively studied NP-complete problems, contributing significantly to advancements in approximation techniques, complexity theory, and online algorithms research. It involves selecting a minimal-weight subset from a collection of subsets to cover all elements. This survey examines online algorithms for Set Cover in multiple contexts, including competitive analysis, stochastic models, advice complexity, predictive algorithms, and recourse strategies. While competitive analysis, which compares online algorithms to the best possible offline solutions, remains a key evaluation method, this paper aims to extend the understanding beyond traditional worst-case scenarios. By providing in-depth insights into algorithm design, analytical methods, and practical applications, it seeks to advance the field and stimulate further research in evolving contexts. Additionally, it underscores the intersection of online algorithms with broader domains such as machine learning and predictive analytics, establishing new benchmarks for exploring their broader implications.

Keywords

• Set cover
• online algorithms
• competitive analysis
• stochastic model
• advice complexity
• algorithms with predictions