Seminar of the Institute of Theoretical Physics of University of Wrocław

12:15, 18-03-16
UWr, pl. Maksa Borna 9, sala 422

Online algorithms for physicists

dr Paweł Laskoś-⁠Grabowski


In the name of the field of online algorithms, "online" does not refer to computer networks, but instead to making decisions based on partial information, which is revealed only over time.  Algorithms are primarily analysed in terms of their incurred cost (or, conversely, accumulated gain) and how it compares to an optimal offline (that is, omniscient or prescient) solution.  As such, this situation is different from more traditional algorithm analysis, which focuses on time and/or space complexity.

In this talk, I will provide a brief overview and introduction into online algorithms.  I will introduce the central concept of competitiveness and walk through several typical problems, from toy examples to more realistic ones.  The pretext for this talk is an article I co-authored, „Logarithmic price of buffer downscaling on line metrics” [arXiv:1610.04915], recently published in Theoretical Computer Science, which I hope to briefly cover, but which will by no means be the main focus of the talk.

  • Institute address:
    ul. Okólna 2, 50-422 Wrocław
    Mailing address:
    P Nr 1410, 50-950 Wrocław 2
  • 71 343 5021, 71 395 4xxx (where XXX is the ext. number)
    Fax:  71 344 1029
  • Mon - Fri 7:30-15:30