{"id":176384,"date":"2023-11-20T12:32:42","date_gmt":"2023-11-20T18:32:42","guid":{"rendered":"https:\/\/lifeboat.com\/blog\/2023\/11\/researchers-refute-a-widespread-belief-about-online-algorithms"},"modified":"2023-11-20T12:32:42","modified_gmt":"2023-11-20T18:32:42","slug":"researchers-refute-a-widespread-belief-about-online-algorithms","status":"publish","type":"post","link":"https:\/\/lifeboat.com\/blog\/2023\/11\/researchers-refute-a-widespread-belief-about-online-algorithms","title":{"rendered":"Researchers Refute a Widespread Belief About Online Algorithms"},"content":{"rendered":"<p><a class=\"aligncenter blog-photo\" href=\"https:\/\/lifeboat.com\/blog.images\/researchers-refute-a-widespread-belief-about-online-algorithms2.jpg\"><\/a><\/p>\n<p>\u201cIt\u2019s really simple to define this problem,\u201d said <a href=\"https:\/\/sites.google.com\/cs.uni.wroc.pl\/marcinbienkowski\/\">Marcin Bie\u0144kowski<\/a>, an algorithms researcher at the University of Wroc\u0142aw in Poland. But it \u201cturns out to be bizarrely difficult.\u201d Since researchers began attacking the <em>k<\/em>-server problem in the late 1980s, they have wondered exactly how well online algorithms can handle the task.<\/p>\n<p>Over the decades, researchers began to believe there\u2019s a certain level of algorithmic performance you can always achieve for the <em>k<\/em>-server problem. So no matter what version of the problem you\u2019re dealing with, there\u2019ll be an algorithm that reaches this goal. But in a paper first published online last November, three computer scientists <a href=\"https:\/\/arxiv.org\/abs\/2211.05753\">showed<\/a> that this isn\u2019t always achievable. In some cases, every algorithm falls short.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u201cIt\u2019s really simple to define this problem,\u201d said Marcin Bie\u0144kowski, an algorithms researcher at the University of Wroc\u0142aw in Poland. But it \u201cturns out to be bizarrely difficult.\u201d Since researchers began attacking the k-server problem in the late 1980s, they have wondered exactly how well online algorithms can handle the task. Over the decades, researchers [\u2026]<\/p>\n","protected":false},"author":661,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1523,41],"tags":[],"class_list":["post-176384","post","type-post","status-publish","format-standard","hentry","category-computing","category-information-science"],"_links":{"self":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/176384","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/users\/661"}],"replies":[{"embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/comments?post=176384"}],"version-history":[{"count":0,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/176384\/revisions"}],"wp:attachment":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/media?parent=176384"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/categories?post=176384"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/tags?post=176384"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}