Improved analysis of the online set cover problem with advice
| Autor: | Richard Královič, Sacha Krug, Tobias Mömke, Stefan Dobrev, Rastislav Královič, Dennis Komm, Jeff Edmonds |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Mathematical optimization General Computer Science 010102 general mathematics Online Computation Advice complexity Set cover problem 0102 computer and information sciences 01 natural sciences Upper and lower bounds Theoretical Computer Science Set (abstract data type) Set packing 010201 computation theory & mathematics Factor (programming language) 0101 mathematics Online algorithm Advice (complexity) computer Mathematics Drawback computer.programming_language |
| Zdroj: | Theoretical Computer Science, 689 |
| ISSN: | 0304-3975 |
| Popis: | We study the advice complexity of an online version of the set cover problem. The goal is to quantify the information that online algorithms for this problem need to be supplied with to compute high-quality solutions and to overcome the drawback of not knowing future requests. This concept was successfully applied to many prominent online problems in the past while trying to capture the essence of “what makes an online problem hard.” The online set cover problem was introduced by Alon et al. (2009) [2] : for a ground set of size n and a set family of m subsets of the ground set, we obtain bounds in both n and m. We show that a linear number (with respect to both n and m) of advice bits is both sufficient and necessary to perform optimally. Furthermore, we prove that O ( ( n log c ) / c ) bits are sufficient to design a c-competitive online algorithm, and this bound is tight up to a factor of O ( log c ) . We further give upper and lower bounds for achieving c-competitiveness with respect to m. Finally, we analyze the advice complexity of the problem with respect to some natural parameters, i.e., measurable properties of the inputs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect