Revisiting Online Algorithms: A Survey of Set Cover Solutions Beyond Competitive Analysis
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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2024-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10765974/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1846150401165885440 |
|---|---|
| author | Christine Markarian Claude Fachkha Noura Yassine |
| author_facet | Christine Markarian Claude Fachkha Noura Yassine |
| author_sort | Christine Markarian |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-7ff500fb4e284225af77e57ea6541810 |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-7ff500fb4e284225af77e57ea65418102024-11-29T00:02:11ZengIEEEIEEE Access2169-35362024-01-011217472317473910.1109/ACCESS.2024.350454110765974Revisiting Online Algorithms: A Survey of Set Cover Solutions Beyond Competitive AnalysisChristine Markarian0https://orcid.org/0000-0003-2689-4412Claude Fachkha1https://orcid.org/0000-0003-2863-4817Noura Yassine2https://orcid.org/0000-0002-8994-5427College of Engineering and Information Technology, University of Dubai, Dubai, United Arab EmiratesCollege of Engineering and Information Technology, University of Dubai, Dubai, United Arab EmiratesMathematics and Computer Science Department, Faculty of Science, Beirut Arab University, Beirut, LebanonOnline 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.https://ieeexplore.ieee.org/document/10765974/Set coveronline algorithmscompetitive analysisstochastic modeladvice complexityalgorithms with predictions |
| spellingShingle | Christine Markarian Claude Fachkha Noura Yassine Revisiting Online Algorithms: A Survey of Set Cover Solutions Beyond Competitive Analysis IEEE Access Set cover online algorithms competitive analysis stochastic model advice complexity algorithms with predictions |
| title | Revisiting Online Algorithms: A Survey of Set Cover Solutions Beyond Competitive Analysis |
| title_full | Revisiting Online Algorithms: A Survey of Set Cover Solutions Beyond Competitive Analysis |
| title_fullStr | Revisiting Online Algorithms: A Survey of Set Cover Solutions Beyond Competitive Analysis |
| title_full_unstemmed | Revisiting Online Algorithms: A Survey of Set Cover Solutions Beyond Competitive Analysis |
| title_short | Revisiting Online Algorithms: A Survey of Set Cover Solutions Beyond Competitive Analysis |
| title_sort | revisiting online algorithms a survey of set cover solutions beyond competitive analysis |
| topic | Set cover online algorithms competitive analysis stochastic model advice complexity algorithms with predictions |
| url | https://ieeexplore.ieee.org/document/10765974/ |
| work_keys_str_mv | AT christinemarkarian revisitingonlinealgorithmsasurveyofsetcoversolutionsbeyondcompetitiveanalysis AT claudefachkha revisitingonlinealgorithmsasurveyofsetcoversolutionsbeyondcompetitiveanalysis AT nourayassine revisitingonlinealgorithmsasurveyofsetcoversolutionsbeyondcompetitiveanalysis |