Notice: Function _load_textdomain_just_in_time was called incorrectly. Translation loading for the wp-plugin-hostgator domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114

Notice: Function _load_textdomain_just_in_time was called incorrectly. Translation loading for the ol-scrapes domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893
{"id":38267,"date":"2023-11-21T21:58:03","date_gmt":"2023-11-21T21:58:03","guid":{"rendered":"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/"},"modified":"2023-11-21T21:58:05","modified_gmt":"2023-11-21T21:58:05","slug":"researchers-refute-a-widespread-belief-about-online-algorithms","status":"publish","type":"post","link":"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/","title":{"rendered":"Researchers Refute a Widespread Belief About Online Algorithms"},"content":{"rendered":"

Source:https:\/\/www.quantamagazine.org\/researchers-refute-a-widespread-belief-about-online-algorithms-20231120\/#comments<\/a><\/br>
\nResearchers Refute a Widespread Belief About Online Algorithms<\/br>
\n2023-11-21 21:58:03<\/br><\/p>\n

\n

When they study these problems, scientists like to envision them as games against an adversary. The adversary chooses a devilish sequence of requests to make the online algorithm perform as badly as possible compared to its offline counterpart. To rob the adversary of some of its power, researchers use algorithms that include random decisions<\/a>.<\/p>\n

This strategy is quite effective, and researchers have suspected since the early 1990s that you can always find a randomized algorithm that reaches a specific performance goal: a competitive ratio proportional to log k<\/em>, where k <\/em>is the number of agents. This is called the randomized k<\/em>-server conjecture, and researchers have shown that it\u2019s true for some spaces, or specific collections of points (the equivalent of houses that could call for plumbers). But it hasn\u2019t been proved for all cases.<\/p>\n

Like most researchers, Rabani and his co-authors \u2014 S\u00e9bastien Bubeck<\/a> of Microsoft Research and Christian Coester<\/a> of the University of Oxford \u2014 figured the conjecture was true. \u201cI had no reason to doubt it,\u201d Coester said.<\/p>\n

But that started to change as they worked on another online problem. It had connections to the k<\/em>-server problem, and the known lower limit on the competitive ratio was unexpectedly high. It made them think perhaps a goal as low as log k <\/em>for the k<\/em>-server problem was overly optimistic.<\/p>\n

Rabani said it was Coester who first suggested that the randomized k<\/em>-server conjecture might be false. \u201cAs soon as he said it, it all made sense.\u201d<\/p>\n

To disprove the conjecture, the authors played the adversary, creating a perfect storm that would prevent any online algorithm from reaching a competitive ratio of log k<\/em>. Their strategy had two parts: They constructed a family of complex, fractal-like spaces and designed a distribution of request sequences that would be difficult for any possible algorithm. On the algorithm\u2019s very first move, the structure of the space meant it had to choose between two identical paths, one of which would eventually require extra travel based on the requests. Then the authors used a method called recursion to build spaces that multiplied these decision points, forcing the algorithm into a morass of bad options and driving up the cost.<\/p>\n

The choices reminded Rabani of the Robert Frost poem \u201cThe Road Not Taken,<\/a>\u201d in which a traveler contemplates two potential paths through a yellow wood. \u201cWe just apply the poem recursively,\u201d he joked. \u201cAnd then things go really bad.\u201d<\/p>\n

The authors showed that, in the spaces they had constructed, a randomized algorithm can never achieve a competitive ratio better than (log k<\/em>)2<\/sup>, pushing a universal goal of log k <\/em>forever out of reach. They had refuted the conjecture.<\/p>\n

This work, which won a Best Paper Award<\/a> at the 2023 Symposium on Theory of Computing<\/a>, marks a \u201csolidly theoretical\u201d milestone, Gupta said. This kind of result helps indicate what kind of performance we can hope for from our algorithms. In practice, however, algorithm designers often aren\u2019t planning around worst-case scenarios, with an omnipotent adversary and complete ignorance of the future. When algorithms are unleashed on real-world problems, they often exceed theoretical expectations.<\/p>\n

The paper, which also proved cutoffs for randomized algorithms used for other problems, could also have implications for future work in the field. The result clearly \u201chighlights the power\u201d of the technique the authors used, Gupta said.<\/p>\n

Perhaps those future findings will defy researchers\u2019 expectations as this one did, Rabani said. \u201cThis is one of the cases where it feels really good to be wrong.\u201d<\/p>\n

Quanta\u00a0is conducting a series of surveys to better serve our audience. Take our\u00a0<\/i>computer science reader survey<\/i><\/a>\u00a0and you will be entered to win free<\/i>\u00a0Quanta\u00a0merchandise.<\/i><\/p>\n<\/div>\n

<\/br><\/br><\/br><\/p>\n

Uncategorized<\/br>
\n<\/br>
\nSource:https:\/\/www.quantamagazine.org\/researchers-refute-a-widespread-belief-about-online-algorithms-20231120\/#comments<\/a><\/br><\/br><\/p>\n","protected":false},"excerpt":{"rendered":"

Source:https:\/\/www.quantamagazine.org\/researchers-refute-a-widespread-belief-about-online-algorithms-20231120\/#comments Researchers Refute a Widespread Belief About Online Algorithms 2023-11-21 21:58:03 When they study these problems, scientists like to envision them as games against an adversary. The adversary chooses a devilish sequence of requests to make the online algorithm perform as badly as possible compared to its offline counterpart. To rob the adversary of some […]<\/p>\n","protected":false},"author":1,"featured_media":38268,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","om_disable_all_campaigns":false,"pagelayer_contact_templates":[],"_pagelayer_content":"","_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-38267","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-uncategorized"],"yoast_head":"\nResearchers Refute a Widespread Belief About Online Algorithms - Science and Nerds<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Researchers Refute a Widespread Belief About Online Algorithms - Science and Nerds\" \/>\n<meta property=\"og:description\" content=\"Source:https:\/\/www.quantamagazine.org\/researchers-refute-a-widespread-belief-about-online-algorithms-20231120\/#comments Researchers Refute a Widespread Belief About Online Algorithms 2023-11-21 21:58:03 When they study these problems, scientists like to envision them as games against an adversary. The adversary chooses a devilish sequence of requests to make the online algorithm perform as badly as possible compared to its offline counterpart. To rob the adversary of some […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/\" \/>\n<meta property=\"og:site_name\" content=\"Science and Nerds\" \/>\n<meta property=\"article:published_time\" content=\"2023-11-21T21:58:03+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2023-11-21T21:58:05+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/scienceandnerds.com\/wp-content\/uploads\/2023\/11\/researchers-refute-a-widespread-belief-about-online-algorithms_655d27ec7a798.webp\" \/>\n\t<meta property=\"og:image:width\" content=\"2560\" \/>\n\t<meta property=\"og:image:height\" content=\"1440\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/webp\" \/>\n<meta name=\"author\" content=\"admin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/\",\"url\":\"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/\",\"name\":\"Researchers Refute a Widespread Belief About Online Algorithms - Science and Nerds\",\"isPartOf\":{\"@id\":\"https:\/\/scienceandnerds.com\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/11\/researchers-refute-a-widespread-belief-about-online-algorithms_655d27ec7a798.webp?fit=2560%2C1440&ssl=1\",\"datePublished\":\"2023-11-21T21:58:03+00:00\",\"dateModified\":\"2023-11-21T21:58:05+00:00\",\"author\":{\"@id\":\"https:\/\/scienceandnerds.com\/#\/schema\/person\/ea2991abeb2b9ab04b32790dff28360e\"},\"breadcrumb\":{\"@id\":\"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/#primaryimage\",\"url\":\"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/11\/researchers-refute-a-widespread-belief-about-online-algorithms_655d27ec7a798.webp?fit=2560%2C1440&ssl=1\",\"contentUrl\":\"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/11\/researchers-refute-a-widespread-belief-about-online-algorithms_655d27ec7a798.webp?fit=2560%2C1440&ssl=1\",\"width\":2560,\"height\":1440},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/scienceandnerds.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Researchers Refute a Widespread Belief About Online Algorithms\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/scienceandnerds.com\/#website\",\"url\":\"https:\/\/scienceandnerds.com\/\",\"name\":\"Science and Nerds\",\"description\":\"My WordPress Blog\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/scienceandnerds.com\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/scienceandnerds.com\/#\/schema\/person\/ea2991abeb2b9ab04b32790dff28360e\",\"name\":\"admin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/scienceandnerds.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/7e6e14fc6691445ef2b2c0a3a6c43882?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/7e6e14fc6691445ef2b2c0a3a6c43882?s=96&d=mm&r=g\",\"caption\":\"admin\"},\"sameAs\":[\"https:\/\/scienceandnerds.com\"],\"url\":\"https:\/\/scienceandnerds.com\/author\/admin\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Researchers Refute a Widespread Belief About Online Algorithms - Science and Nerds","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/","og_locale":"en_US","og_type":"article","og_title":"Researchers Refute a Widespread Belief About Online Algorithms - Science and Nerds","og_description":"Source:https:\/\/www.quantamagazine.org\/researchers-refute-a-widespread-belief-about-online-algorithms-20231120\/#comments Researchers Refute a Widespread Belief About Online Algorithms 2023-11-21 21:58:03 When they study these problems, scientists like to envision them as games against an adversary. The adversary chooses a devilish sequence of requests to make the online algorithm perform as badly as possible compared to its offline counterpart. To rob the adversary of some […]","og_url":"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/","og_site_name":"Science and Nerds","article_published_time":"2023-11-21T21:58:03+00:00","article_modified_time":"2023-11-21T21:58:05+00:00","og_image":[{"width":2560,"height":1440,"url":"https:\/\/scienceandnerds.com\/wp-content\/uploads\/2023\/11\/researchers-refute-a-widespread-belief-about-online-algorithms_655d27ec7a798.webp","type":"image\/webp"}],"author":"admin","twitter_card":"summary_large_image","twitter_misc":{"Written by":"admin","Est. reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/","url":"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/","name":"Researchers Refute a Widespread Belief About Online Algorithms - Science and Nerds","isPartOf":{"@id":"https:\/\/scienceandnerds.com\/#website"},"primaryImageOfPage":{"@id":"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/#primaryimage"},"image":{"@id":"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/#primaryimage"},"thumbnailUrl":"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/11\/researchers-refute-a-widespread-belief-about-online-algorithms_655d27ec7a798.webp?fit=2560%2C1440&ssl=1","datePublished":"2023-11-21T21:58:03+00:00","dateModified":"2023-11-21T21:58:05+00:00","author":{"@id":"https:\/\/scienceandnerds.com\/#\/schema\/person\/ea2991abeb2b9ab04b32790dff28360e"},"breadcrumb":{"@id":"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/#primaryimage","url":"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/11\/researchers-refute-a-widespread-belief-about-online-algorithms_655d27ec7a798.webp?fit=2560%2C1440&ssl=1","contentUrl":"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/11\/researchers-refute-a-widespread-belief-about-online-algorithms_655d27ec7a798.webp?fit=2560%2C1440&ssl=1","width":2560,"height":1440},{"@type":"BreadcrumbList","@id":"https:\/\/scienceandnerds.com\/2023\/11\/21\/researchers-refute-a-widespread-belief-about-online-algorithms\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/scienceandnerds.com\/"},{"@type":"ListItem","position":2,"name":"Researchers Refute a Widespread Belief About Online Algorithms"}]},{"@type":"WebSite","@id":"https:\/\/scienceandnerds.com\/#website","url":"https:\/\/scienceandnerds.com\/","name":"Science and Nerds","description":"My WordPress Blog","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/scienceandnerds.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/scienceandnerds.com\/#\/schema\/person\/ea2991abeb2b9ab04b32790dff28360e","name":"admin","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/scienceandnerds.com\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/7e6e14fc6691445ef2b2c0a3a6c43882?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/7e6e14fc6691445ef2b2c0a3a6c43882?s=96&d=mm&r=g","caption":"admin"},"sameAs":["https:\/\/scienceandnerds.com"],"url":"https:\/\/scienceandnerds.com\/author\/admin\/"}]}},"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2023\/11\/researchers-refute-a-widespread-belief-about-online-algorithms_655d27ec7a798.webp?fit=2560%2C1440&ssl=1","_links":{"self":[{"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/posts\/38267","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/comments?post=38267"}],"version-history":[{"count":1,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/posts\/38267\/revisions"}],"predecessor-version":[{"id":38269,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/posts\/38267\/revisions\/38269"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/media\/38268"}],"wp:attachment":[{"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/media?parent=38267"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/categories?post=38267"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/tags?post=38267"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}