Online algorithms with advice: The tape model
| Autor: | Rastislav Královič, Hans-Joachim Böckenhauer, Tobias Mömke, Richard Královič, Dennis Komm |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Theoretical computer science
Competitive analysis Job shop scheduling Computer science String (computer science) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Oracle Computer Science Applications Theoretical Computer Science Randomized algorithm Computational Theory and Mathematics 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Paging 020201 artificial intelligence & image processing Online algorithm Advice (complexity) Information Systems |
| Zdroj: | Information and Computation. 254:59-83 |
| ISSN: | 0890-5401 |
| DOI: | 10.1016/j.ic.2017.03.001 |
| Popis: | We investigate to what extent the solution quality of online algorithms can be improved when supplying them with information about the input. To this end, we refine the recently introduced notion of advice complexity where the algorithm has access to an advice string that is communicated by an oracle with access to the complete input. The advice complexity is the length of this communication. We study the connections between advice complexity and both determinism and randomization using the paging problem, job shop scheduling, and a routing problem as sample problems. Our results for these problems show that very small advice (only three bits in the case of paging) suffices to significantly improve over the best deterministic algorithms. To be as good as randomized algorithms, a moderate number of advice bits is sufficient, but it varies with the specific problem considered. However, to obtain optimality, usually very large advice is necessary. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect