dr Paweł Laskoś-⁠Grabowski, IFT Uwr

Online algorithms for physicists

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.