Abstract
In this paper, we investigate to what extent the solution quality of online algorithms can be improved by allowing the algorithm to extract a given amount of information about the input. We consider the recently introduced notion of advice complexity where the algorithm, in addition to being fed the requests one by one, has access to a tape of advice bits that were computed by some oracle function from the complete input. The advice complexity is the number of advice bits read. We introduce an improved model of advice complexity and investigate the connections of advice complexity to the competitive ratio of both deterministic and randomized online algorithms using the paging problem, job shop scheduling, and the routing problem on a line as sample problems. We provide both upper and lower bounds on the advice complexity of all three problems.
Our results for all of these problems show that very small advice (only three bits in the case of paging) already suffices to significantly improve over the best deterministic algorithm. Moreover, to achieve the same competitive ratio as any randomized online algorithm, a logarithmic number of advice bits is sufficient. On the other hand, to obtain optimality, much larger advice is necessary.
This work was partially supported by ETH grant TH 18 07-3, and APVV grant 0433-06.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ben-David, S., Borodin, A.: A new measure for the study of on-line algorithms. Algorithmica 11(1), 73–91 (1994)
Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press, New York (1998)
Böckenhauer, H.-J., Komm, D., Královič, R., Královič, R., Mömke, T.: Online Algorithms with Advice. Technical Report 614. ETH Zurich, Department of Computer Science (2009)
Brucker, P.: An efficient algorithm for the job-shop problem with two jobs. Computing 40(4), 353–359 (1988)
Caragiannis, I., Fishkin, A.V., Kaklamanis, C., Papaioannou, E.: Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs. Discrete Applied Mathematics 155(2), 119–136 (2007)
Dobrev, S., Královič, R., Pardubská, D.: Measuring the Problem-Relevant Information in Input. RAIRO-Theoretical Informatics and Applications 43(3), 585–613 (2009)
Emek, Y., Fraigniaud, P., Korman, A., Rosén, A.: Online Computation with Advice. In: Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5555, pp. 427–438. Springer, Heidelberg (2009)
Hromkovič, J., Mömke, T., Steinhöfel, K., Widmayer, P.: Job shop scheduling with unit length tasks: bounds and algorithms. Algorithmic Operations Research 2(1), 1–14 (2007)
Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communications of the ACM 28(2), 202–208 (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Böckenhauer, HJ., Komm, D., Královič, R., Královič, R., Mömke, T. (2009). On the Advice Complexity of Online Problems. In: Dong, Y., Du, DZ., Ibarra, O. (eds) Algorithms and Computation. ISAAC 2009. Lecture Notes in Computer Science, vol 5878. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10631-6_35
Download citation
DOI: https://doi.org/10.1007/978-3-642-10631-6_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10630-9
Online ISBN: 978-3-642-10631-6
eBook Packages: Computer ScienceComputer Science (R0)