Measuring the problem-relevant information in input

Stefan Dobrev; Rastislav Královič; Dana Pardubská

RAIRO - Theoretical Informatics and Applications (2009)

  • Volume: 43, Issue: 3, page 585-613
  • ISSN: 0988-3754

Abstract

top
We propose a new way of characterizing the complexity of online problems. Instead of measuring the degradation of the output quality caused by the ignorance of the future we choose to quantify the amount of additional global information needed for an online algorithm to solve the problem optimally. In our model, the algorithm cooperates with an oracle that can see the whole input. We define the advice complexity of the problem to be the minimal number of bits (normalized per input request, and minimized over all algorithm-oracle pairs) communicated by the algorithm to the oracle in order to solve the problem optimally. Hence, the advice complexity measures the amount of problem-relevant information contained in the input. We introduce two modes of communication between the algorithm and the oracle based on whether the oracle offers an advice spontaneously (helper) or on request (answerer). We analyze the Paging and DiffServ problems in terms of advice complexity and deliver upper and lower bounds in both communication modes; in the case of DiffServ problem in helper mode the bounds are tight.

How to cite

top

Dobrev, Stefan, Královič, Rastislav, and Pardubská, Dana. "Measuring the problem-relevant information in input." RAIRO - Theoretical Informatics and Applications 43.3 (2009): 585-613. <http://eudml.org/doc/250610>.

@article{Dobrev2009,
abstract = { We propose a new way of characterizing the complexity of online problems. Instead of measuring the degradation of the output quality caused by the ignorance of the future we choose to quantify the amount of additional global information needed for an online algorithm to solve the problem optimally. In our model, the algorithm cooperates with an oracle that can see the whole input. We define the advice complexity of the problem to be the minimal number of bits (normalized per input request, and minimized over all algorithm-oracle pairs) communicated by the algorithm to the oracle in order to solve the problem optimally. Hence, the advice complexity measures the amount of problem-relevant information contained in the input. We introduce two modes of communication between the algorithm and the oracle based on whether the oracle offers an advice spontaneously (helper) or on request (answerer). We analyze the Paging and DiffServ problems in terms of advice complexity and deliver upper and lower bounds in both communication modes; in the case of DiffServ problem in helper mode the bounds are tight. },
author = {Dobrev, Stefan, Královič, Rastislav, Pardubská, Dana},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Online algorithms; communication complexity; advice complexity; paging.; online algorithms; paging},
language = {eng},
month = {4},
number = {3},
pages = {585-613},
publisher = {EDP Sciences},
title = {Measuring the problem-relevant information in input},
url = {http://eudml.org/doc/250610},
volume = {43},
year = {2009},
}

TY - JOUR
AU - Dobrev, Stefan
AU - Královič, Rastislav
AU - Pardubská, Dana
TI - Measuring the problem-relevant information in input
JO - RAIRO - Theoretical Informatics and Applications
DA - 2009/4//
PB - EDP Sciences
VL - 43
IS - 3
SP - 585
EP - 613
AB - We propose a new way of characterizing the complexity of online problems. Instead of measuring the degradation of the output quality caused by the ignorance of the future we choose to quantify the amount of additional global information needed for an online algorithm to solve the problem optimally. In our model, the algorithm cooperates with an oracle that can see the whole input. We define the advice complexity of the problem to be the minimal number of bits (normalized per input request, and minimized over all algorithm-oracle pairs) communicated by the algorithm to the oracle in order to solve the problem optimally. Hence, the advice complexity measures the amount of problem-relevant information contained in the input. We introduce two modes of communication between the algorithm and the oracle based on whether the oracle offers an advice spontaneously (helper) or on request (answerer). We analyze the Paging and DiffServ problems in terms of advice complexity and deliver upper and lower bounds in both communication modes; in the case of DiffServ problem in helper mode the bounds are tight.
LA - eng
KW - Online algorithms; communication complexity; advice complexity; paging.; online algorithms; paging
UR - http://eudml.org/doc/250610
ER -

References

top
  1. D. Achlioptas, M. Chrobak and J. Noga, Competitive analysis of randomized paging algorithms. Theoret. Comput. Sci.234 (2000) 203–218.  
  2. S. Albers, On the influence of lookahead in competitive paging algorithms. Algorithmica18 (1997) 283–305.  
  3. S. Albers, Online algorithms: A survey. Math. Prog.97 (2003) 3–26.  
  4. L.A. Belady, A study of replacement algorithms for virtual storage computers. IBM Systems Journal5 (1966) 78–101.  
  5. S. Ben-David and A. Borodin, A new measure for the study of on-line algorithms. Algorithmica11 (1994) 73–91.  
  6. A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis. Cambridge University Press (1998).  
  7. A. Borodin, S. Irani, P. Raghavan and B. Schieber, Competitive paging with locality of reference. In Proc. 23rd Annual ACM Symposium on Theory of Computing (1991) 249–259.  
  8. J. Boyar, M.R. Ehmsen and K.S. Larsen, Theoretical Evidence for the superiority of LRU-2 over LRU for the paging problem. In Fourth Workshop on Approximation on Online Algorithms. Lecture Notes Comput. Sci. 4368 (2006) 95–107.  
  9. J. Boyar, K.S. Larsen and M.N. Nielsen, The accommodating function: a generalization of the competitive ratio. SIAM J. Comput.31 (2001) 233–258.  
  10. 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–69.  
  11. M. Englert and M. Westermann, lower and upper bounds on FIFO buffer management in QoS switches, In Proc. ESA 2006. Lect. Notes Comput. Sci. 4168 (2006) 352–363.  
  12. A. Fiat, R.M. Karp, M. Luby, L.A. McGeoch, D.D. Sleator and N.E. Young, Competitive paging algorithms. J. Algorithms12 (1991) 685–699.  
  13. P. Fraigniaud, C. Gavoille, D. Ilcinkas and A. Pelc, Distributed computing with advice: information sensitivity of graph coloring. In Proc. 34th International Colloquium on Automata, Languages and Programming (ICALP 2007) (2007).  
  14. P. Fraigniaud, D. Ilcinkas and A. Pelc, Tree exploration with an oracle. In Proc. 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006). Lect. Notes Comput. Sci. 4162 (2006) 24–37.  
  15. P. Fraigniaud, D. Ilcinkas and A. Pelc, Oracle size: a new measure of difficulty for communication problems. In Proc. 25th Ann. ACM Symposium on Principles of Distributed Computing (PODC 2006) (2006) 179–187.  
  16. R.L. Graham, Bounds for certain multiprocessing anomalies. Bell Systems Technical Journal45 (1966) 1563–1581.  
  17. S. Irany and A.R. Karlin, Online computation. In Approximation Algorithms for NP-Hard Problems, D.S. Hochbaum, Ed. PWS Publishing Company (1997) 521–564.  
  18. S. Irani, A.R. Karlin and S. Phillips, Strongly competitive algorithms for paging with locality of reference. In Proc. 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (1992) 228–236.  
  19. B. Kalyanasundaram and K. Pruhs, Speed is as Powerful as Clairvoyance. IEEE Symposium on Foundations of Computer Science (1995) 214–221.  
  20. A.R. Karlin, M.S. Manasse, L. Rudolph and D.D. Sleator, Competitive Snoopy Caching. Algorithmica3 (1988) 79–119.  
  21. R. Karp, On-line algorithms versus off-line algorithms: how much is it worth to know the future? Proc. IFIP 12th World Computer Congress1 (1992) 416–429.  
  22. E. Koutsoupias and C.H. Papadimitriou, Beyond competitive analysis. In Proc. 34th Annual Symposium on Foundations of Computer Science (1994) 394–400.  
  23. Z. Lotker and B. Patt-Shamir, Nearly optimal FIFO buffer management for DiffServ. PODC2002 (2002) 134–143.  
  24. M.M. Manasse, L.A. McGeoch and D.D. Sleator, Competitive Algorithms for Online Problems. In Proc. 20th Annual Symposium on the Theory of Computing (1988) 322–333.  
  25. C.A. Philips, C. Stein, E. Torng and J. Wein, Optimal time-critical scheduling via resource augmentation. In Proc. 29th Annual ACM Symposium on the Theory of Computing (1997) 140–149.  
  26. U.M. O'Reilly and N. Santoro, The expressiveness of silence: tight bounds for synchronous communication of information using bits and silence. In Proc. 18th International Workshop on Graph-Theoretic Concepts in Computer Science (1992) 321–332.  
  27. P. Raghavan, A statistical adversary for on-line algorithms. In On-Line Algorithms, DIMACS Series in Discrete Mathematics and Theoretical Computer Science (1991) 79–83.  
  28. H. Robbins, A Remark of Stirling's Formula. Amer. Math. Month.62 (1955) 26–29.  
  29. D.D. Sleator and R.E. Tarjan, Amortized efficiency of update and paging rules. Commun. ACM 28 (1985) 202–208.  
  30. E. Torng, A Unified Analysis of Paging and Caching. Algorithmica20 (1998) 175–200.  
  31. N. Young, On-line paging against adversially biased random inputs. J. Algorithms37 (2000) 218–235.  
  32. N. Young, The k-server dual and loose competitiveness for paging. Algorithmica11 (1994) 525–541.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.