Measuring the problem-relevant information in input
RAIRO-Theor. Inf. Appl., 43 3 (2009) 585-613
Published online: 2009-04-04
Articles citing this article
The Citing articles tool gives a list of articles citing the current article.
The citing articles come from EDP Sciences database, as well as other publishers participating in CrossRef Cited-by Linking Program. You can set up your personal account to receive an email alert each time this article is cited by a new article (see the menu on the right-hand side of the abstract page).
Cited article:
This article has been cited by the following article(s):
Online Unbounded Knapsack
Hans-Joachim Böckenhauer, Matthias Gehnen, Juraj Hromkovič, Ralf Klasing, Dennis Komm, Henri Lotze, Daniel Mock, Peter Rossmanith and Moritz StockerTheory of Computing Systems 69 (1) (2025)
https://doi.org/10.1007/s00224-025-10215-0
Online computation with untrusted advice
Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali and Marc RenaultJournal of Computer and System Sciences 144 103545 (2024)
https://doi.org/10.1016/j.jcss.2024.103545
Advice complexity of adaptive priority algorithms
Joan Boyar, Kim S. Larsen and Denis PankratovTheoretical Computer Science 984 114318 (2024)
https://doi.org/10.1016/j.tcs.2023.114318
(2024)
https://doi.org/10.2139/ssrn.4821443
13889 62 (2023)
https://doi.org/10.1007/978-3-031-34347-6_6
14079 136 (2023)
https://doi.org/10.1007/978-3-031-38906-1_10
Call Admission Problems on Trees
Hans-Joachim Böckenhauer, Nina Corvelo Benz and Dennis KommTheoretical Computer Science (2022)
https://doi.org/10.1016/j.tcs.2022.04.042
Relative Worst-order Analysis
Joan Boyar, Lene M. Favrholdt and Kim S. LarsenACM Computing Surveys 54 (1) 1 (2022)
https://doi.org/10.1145/3425910
Online Node- and Edge-Deletion Problems with Advice
Li-Hsuan Chen, Ling-Ju Hung, Henri Lotze and Peter RossmanithAlgorithmica 83 (9) 2719 (2021)
https://doi.org/10.1007/s00453-021-00840-9
Online two-way trading: Randomization and advice
Stanley P.Y. FungTheoretical Computer Science 856 41 (2021)
https://doi.org/10.1016/j.tcs.2020.12.016
12126 140 (2020)
https://doi.org/10.1007/978-3-030-48966-3_11
11638 108 (2019)
https://doi.org/10.1007/978-3-030-25005-8_10
The k-Server Problem with Advice in d Dimensions and on the Sphere
Elisabet Burjons, Dennis Komm and Marcel SchöngensAlgorithmica 81 (5) 1859 (2019)
https://doi.org/10.1007/s00453-018-0514-6
Online Graph Coloring Against a Randomized Adversary
Elisabet Burjons, Juraj Hromkovič, Rastislav Královič, et al.International Journal of Foundations of Computer Science 29 (04) 551 (2018)
https://doi.org/10.1142/S0129054118410058
11011 216 (2018)
https://doi.org/10.1007/978-3-319-98355-4_13
Online Bin Packing with Advice of Small Size
Spyros Angelopoulos, Christoph Dürr, Shahin Kamali, Marc P. Renault and Adi RosénTheory of Computing Systems 62 (8) 2006 (2018)
https://doi.org/10.1007/s00224-018-9862-5
Quantum Online Algorithms with Respect to Space and Advice Complexity
K. Khadiev, A. Khadieva and I. MannapovLobachevskii Journal of Mathematics 39 (9) 1377 (2018)
https://doi.org/10.1134/S1995080218090421
SOFSEM 2018: Theory and Practice of Computer Science
Elisabet Burjons, Dennis Komm and Marcel SchöngensLecture Notes in Computer Science, SOFSEM 2018: Theory and Practice of Computer Science 10706 396 (2018)
https://doi.org/10.1007/978-3-319-73117-9_28
Weighted Online Problems with Advice
Joan Boyar, Lene M. Favrholdt, Christian Kudahl and Jesper W. MikkelsenTheory of Computing Systems 62 (6) 1443 (2018)
https://doi.org/10.1007/s00224-017-9806-5
Online Algorithms with Advice
Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen and Jesper W. MikkelsenACM Computing Surveys 50 (2) 1 (2018)
https://doi.org/10.1145/3056461
11011 231 (2018)
https://doi.org/10.1007/978-3-319-98355-4_14
Improved analysis of the online set cover problem with advice
Stefan Dobrev, Jeff Edmonds, Dennis Komm, et al.Theoretical Computer Science 689 96 (2017)
https://doi.org/10.1016/j.tcs.2017.05.029
Time vs. Information Tradeoffs for Leader Election in Anonymous Trees
Christian Glacet, Avery Miller and Andrzej PelcACM Transactions on Algorithms 13 (3) 1 (2017)
https://doi.org/10.1145/3039870
On the advice complexity of the k-server problem
Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič and Richard KrálovičJournal of Computer and System Sciences 86 159 (2017)
https://doi.org/10.1016/j.jcss.2017.01.001
The Advice Complexity of a Class of Hard Online Problems
Joan Boyar, Lene M. Favrholdt, Christian Kudahl and Jesper W. MikkelsenTheory of Computing Systems 61 (4) 1128 (2017)
https://doi.org/10.1007/s00224-016-9688-y
Combinatorial Algorithms
Joan Boyar, Lene M. Favrholdt, Christian Kudahl and Jesper W. MikkelsenLecture Notes in Computer Science, Combinatorial Algorithms 9843 179 (2016)
https://doi.org/10.1007/978-3-319-44543-4_14
Online Bin Packing with Advice
Joan Boyar, Shahin Kamali, Kim S. Larsen and Alejandro López-OrtizAlgorithmica 74 (1) 507 (2016)
https://doi.org/10.1007/s00453-014-9955-8
Online Algorithms with Advice: A Survey
Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen and Jesper W. MikkelsenACM SIGACT News 47 (3) 93 (2016)
https://doi.org/10.1145/2993749.2993766
SOFSEM 2016: Theory and Practice of Computer Science
Elisabet Burjons, Juraj Hromkovič, Xavier Muñoz and Walter UngerLecture Notes in Computer Science, SOFSEM 2016: Theory and Practice of Computer Science 9587 229 (2016)
https://doi.org/10.1007/978-3-662-49192-8_19
50 (2015)
https://doi.org/10.1109/COMPSAC.2015.92
Algorithms and Complexity
Jesper W. MikkelsenLecture Notes in Computer Science, Algorithms and Complexity 9079 352 (2015)
https://doi.org/10.1007/978-3-319-18173-8_26
Algorithms and Data Structures
Spyros Angelopoulos, Christoph Dürr, Shahin Kamali, Marc Renault and Adi RosénLecture Notes in Computer Science, Algorithms and Data Structures 9214 40 (2015)
https://doi.org/10.1007/978-3-319-21840-3_4
Computing and Combinatorics
Heidi Gebauer, Dennis Komm, Rastislav Královič, Richard Královič and Jasmin SmulaLecture Notes in Computer Science, Computing and Combinatorics 9198 417 (2015)
https://doi.org/10.1007/978-3-319-21398-9_33
Approximation and Online Algorithms
Marie G. Christ, Lene M. Favrholdt and Kim S. LarsenLecture Notes in Computer Science, Approximation and Online Algorithms 8952 83 (2015)
https://doi.org/10.1007/978-3-319-18263-6_8
Online multi-coloring with advice
Marie G. Christ, Lene M. Favrholdt and Kim S. LarsenTheoretical Computer Science 596 79 (2015)
https://doi.org/10.1016/j.tcs.2015.06.044
The online knapsack problem: Advice and randomization
Hans-Joachim Böckenhauer, Dennis Komm, Richard Královič and Peter RossmanithTheoretical Computer Science 527 61 (2014)
https://doi.org/10.1016/j.tcs.2014.01.027
Language and Automata Theory and Applications
Joan Boyar, Shahin Kamali, Kim S. Larsen and Alejandro López-OrtizLecture Notes in Computer Science, Language and Automata Theory and Applications 8370 210 (2014)
https://doi.org/10.1007/978-3-319-04921-2_17
140 (2014)
https://doi.org/10.1109/COMPSACW.2014.27
On the advice complexity of the online L(2,1)-coloring problem on paths and cycles
Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovič, Sacha Krug and Björn SteffenTheoretical Computer Science 554 22 (2014)
https://doi.org/10.1016/j.tcs.2014.06.027
On the advice complexity of online bipartite matching and online stable marriage
Shuichi MiyazakiInformation Processing Letters 114 (12) 714 (2014)
https://doi.org/10.1016/j.ipl.2014.06.013
SOFSEM 2014: Theory and Practice of Computer Science
Kfir Barhum, Hans-Joachim Böckenhauer, Michal Forišek, et al.Lecture Notes in Computer Science, SOFSEM 2014: Theory and Practice of Computer Science 8327 89 (2014)
https://doi.org/10.1007/978-3-319-04298-5_9
Computer Science – Theory and Applications
Dennis Komm, Richard Královič and Tobias MömkeLecture Notes in Computer Science, Computer Science – Theory and Applications 7353 241 (2012)
https://doi.org/10.1007/978-3-642-30642-6_23
Languages Alive
Hans-Joachim Böckenhauer, Juraj Hromkovič, Dennis Komm, Richard Královič and Peter RossmanithLecture Notes in Computer Science, Languages Alive 7300 30 (2012)
https://doi.org/10.1007/978-3-642-31644-9_2
LATIN 2012: Theoretical Informatics
Hans-Joachim Böckenhauer, Dennis Komm, Richard Královič and Peter RossmanithLecture Notes in Computer Science, LATIN 2012: Theoretical Informatics 7256 61 (2012)
https://doi.org/10.1007/978-3-642-29344-3_6
Algorithms and Computation
Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, Richard Královič and Tobias MömkeLecture Notes in Computer Science, Algorithms and Computation 5878 331 (2009)
https://doi.org/10.1007/978-3-642-10631-6_35