{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T05:43:05Z","timestamp":1774590185062,"version":"3.50.1"},"reference-count":32,"publisher":"EDP Sciences","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[2009,7]]},"DOI":"10.1051\/ita\/2009012","type":"journal-article","created":{"date-parts":[[2009,4,3]],"date-time":"2009-04-03T12:55:28Z","timestamp":1238763328000},"page":"585-613","source":"Crossref","is-referenced-by-count":45,"title":["Measuring the problem-relevant information in input"],"prefix":"10.1051","volume":"43","author":[{"given":"Stefan","family":"Dobrev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rastislav","family":"Kr\u00e1lovi\u010d","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dana","family":"Pardubsk\u00e1","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2009,4,4]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/S0304-3975(98)00116-9","volume":"234","author":"Achlioptas","year":"2000","journal-title":"Theoret. Comput. Sci."},{"key":"R2","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/PL00009158","volume":"18","author":"Albers","year":"1997","journal-title":"Algorithmica"},{"key":"R3","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10107-003-0436-0","volume":"97","author":"Albers","year":"2003","journal-title":"Math. Prog."},{"key":"R4","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1147\/sj.52.0078","volume":"5","author":"Belady","year":"1966","journal-title":"IBM Systems Journal"},{"key":"R5","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BF01294264","volume":"11","author":"Ben-David","year":"1994","journal-title":"Algorithmica"},{"key":"R6","unstructured":"A. Borodin and R. El-Yaniv,Online Computation and Competitive Analysis. Cambridge University Press (1998)."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"A. Borodin, S. Irani, P. Raghavan and B. Schieber, Competitive paging with locality of reference. InProc. 23rd Annual ACM Symposium on Theory of Computing(1991) 249\u2013259.","DOI":"10.1145\/103418.103422"},{"key":"R8","unstructured":"J. Boyar, M.R. Ehmsen and K.S. Larsen, Theoretical Evidence for the superiority of LRU-2 over LRU for the paging problem. InFourth Workshop on Approximation on Online Algorithms. Lecture Notes Comput. Sci.4368(2006) 95\u2013107."},{"key":"R9","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1137\/S0097539799361786","volume":"31","author":"Boyar","year":"2001","journal-title":"SIAM J. Comput."},{"key":"R10","unstructured":"J. Boyar and L.M. Favrholdt, The relative worst order ratio for online algorithms,Algorithms and Complexity, 5th Italian Conference, CIAC 2003, Rome, Italy.Lect. Notes Comput. Sci.2653(2003) 58\u201369."},{"key":"R11","unstructured":"M. Englert and M. Westermann, lower and upper bounds on FIFO buffer management in QoS switches, InProc. ESA 2006. Lect. Notes Comput. Sci.4168(2006) 352\u2013363."},{"key":"R12","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1016\/0196-6774(91)90041-V","volume":"12","author":"Fiat","year":"1991","journal-title":"J. Algorithms"},{"key":"R13","unstructured":"P. Fraigniaud, C. Gavoille, D. Ilcinkas and A. Pelc, Distributed computing with advice: information sensitivity of graph coloring. InProc. 34th International Colloquium on Automata, Languages and Programming (ICALP 2007)(2007)."},{"key":"R14","unstructured":"P. Fraigniaud, D. Ilcinkas and A. Pelc, Tree exploration with an oracle. InProc. 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006). Lect. Notes Comput. Sci.4162(2006) 24\u201337."},{"key":"R15","unstructured":"P. Fraigniaud, D. Ilcinkas and A. Pelc, Oracle size: a new measure of difficulty for communication problems. InProc. 25th Ann. ACM Symposium on Principles of Distributed Computing (PODC 2006)(2006) 179\u2013187."},{"key":"R16","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"Graham","year":"1966","journal-title":"Bell Systems Technical Journal"},{"key":"R17","unstructured":"S. Irany and A.R. Karlin, Online computation. InApproximation Algorithms for NP-Hard Problems, D.S. Hochbaum, Ed. PWS Publishing Company (1997) 521\u2013564."},{"key":"R18","unstructured":"S. Irani, A.R. Karlin and S. Phillips, Strongly competitive algorithms for paging with locality of reference. InProc. 3rd Annual ACM-SIAM Symposium on Discrete Algorithms(1992) 228\u2013236."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"B. Kalyanasundaram and K. Pruhs, Speed is as Powerful as Clairvoyance.IEEE Symposium on Foundations of Computer Science(1995) 214\u2013221.","DOI":"10.1109\/SFCS.1995.492478"},{"key":"R20","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/BF01762111","volume":"3","author":"Karlin","year":"1988","journal-title":"Algorithmica"},{"key":"R21","first-page":"416","volume":"1","author":"Karp","year":"1992","journal-title":"Proc. IFIP 12th World Computer Congress"},{"key":"R22","unstructured":"E. Koutsoupias and C.H. Papadimitriou, Beyond competitive analysis. InProc. 34th Annual Symposium on Foundations of Computer Science(1994) 394\u2013400."},{"key":"R23","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1145\/571825.571851","volume":"2002","author":"Lotker","year":"2002","journal-title":"PODC"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"M.M. Manasse, L.A. McGeoch and D.D. Sleator, Competitive Algorithms for Online Problems. InProc. 20th Annual Symposium on the Theory of Computing(1988) 322\u2013333.","DOI":"10.1145\/62212.62243"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"C.A. Philips, C. Stein, E. Torng and J. Wein, Optimal time-critical scheduling via resource augmentation. InProc. 29th Annual ACM Symposium on the Theory of Computing(1997) 140\u2013149.","DOI":"10.1145\/258533.258570"},{"key":"R26","unstructured":"U.M. O'Reilly and N. Santoro, The expressiveness of silence: tight bounds for synchronous communication of information using bits and silence. InProc. 18th International Workshop on Graph-Theoretic Concepts in Computer Science(1992) 321\u2013332."},{"key":"R27","doi-asserted-by":"crossref","unstructured":"P. Raghavan, A statistical adversary for on-line algorithms. InOn-Line Algorithms, DIMACS Series in Discrete Mathematics and Theoretical Computer Science (1991) 79\u201383.","DOI":"10.1090\/dimacs\/007\/05"},{"key":"R28","doi-asserted-by":"crossref","first-page":"26","DOI":"10.2307\/2308012","volume":"62","author":"Robbins","year":"1955","journal-title":"Amer. Math. Month."},{"key":"R29","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"Sleator","year":"1985","journal-title":"Commun. ACM"},{"key":"R30","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/PL00009192","volume":"20","author":"Torng","year":"1998","journal-title":"Algorithmica"},{"key":"R31","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1006\/jagm.2000.1099","volume":"37","author":"Young","year":"2000","journal-title":"J. Algorithms"},{"key":"R32","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/BF01189992","volume":"11","author":"Young","year":"1994","journal-title":"Algorithmica"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2009012\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T21:04:54Z","timestamp":1739048694000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2009012"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4,4]]},"references-count":32,"journal-issue":{"issue":"3"},"alternative-id":["ita08024"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2009012","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4,4]]}}}