* . *
  • About
  • Advertise
  • Privacy & Policy
  • Contact
Monday, October 20, 2025
Earth-News
  • Home
  • Business
  • Entertainment
    Placer County town of Loomis considers entertainment zone for downtown – CBS News

    Loomis Unveils Thrilling New Entertainment Zone to Revitalize Downtown

    CT Culture Corner: Robert Redford films to watch – CT Insider

    CT Culture Corner: Robert Redford films to watch – CT Insider

    Elmira’s New Entertainment Venue ‘Centertown Social’ Adding its Final Touches – WENY News

    Elmira’s New Entertainment Venue ‘Centertown Social’ Adding its Final Touches – WENY News

    Bella Thorne Shows Off Her Toned Abs in Crop Top – Yahoo

    Bella Thorne Shows Off Her Toned Abs in a Chic Crop Top

    Bricktown continues to thrive as OKC’s entertainment district – OKC VeloCity

    Bricktown Shines as Oklahoma City’s Premier Entertainment Hotspot

    This Haunting ‘60s Country Song Is Even More Tragic Than You Remember – Yahoo

    This Haunting ’60s Country Song Will Break Your Heart All Over Again

  • General
  • Health
  • News

    Cracking the Code: Why China’s Economic Challenges Aren’t Shaking Markets, Unlike America’s” – Bloomberg

    Trump’s Narrow Window to Spread the Truth About Harris

    Trump’s Narrow Window to Spread the Truth About Harris

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Trending Tags

    • Trump Inauguration
    • United Stated
    • White House
    • Market Stories
    • Election Results
  • Science
  • Sports
  • Technology
    ‘New frontier’: Austin leaders start discussions on air taxi technology – KXAN Austin

    Austin Leaders Ignite Exciting Conversations on the Future of Air Taxi Technology

    How a Gemma model helped discover a new potential cancer therapy pathway – blog.google

    How a Gemma Model Revealed a Breakthrough Pathway for Cancer Treatment

    Italian Technology in Manufacturing: Supporting North American Industries and Keeping Production Local – Thomasnet

    How Italian Technology is Revolutionizing North American Manufacturing and Boosting Local Production

    Guide to Proteomics Project Planning: Sample Preparation Strategies – Technology Networks

    Guide to Proteomics Project Planning: Sample Preparation Strategies – Technology Networks

    DLG−Agrifuture Concept Winners 2025 announced – Visionary Ideas in agricultural technology recognized – TheNewsMarket

    Meet the Visionary Innovators Revolutionizing Agricultural Technology in 2025

    Spanning the Gulf: Global Defence Technology 155 – Army Technology

    Spanning the Gulf: Exploring Cutting-Edge Global Defence Technology

    Trending Tags

    • Nintendo Switch
    • CES 2017
    • Playstation 4 Pro
    • Mark Zuckerberg
No Result
View All Result
  • Home
  • Business
  • Entertainment
    Placer County town of Loomis considers entertainment zone for downtown – CBS News

    Loomis Unveils Thrilling New Entertainment Zone to Revitalize Downtown

    CT Culture Corner: Robert Redford films to watch – CT Insider

    CT Culture Corner: Robert Redford films to watch – CT Insider

    Elmira’s New Entertainment Venue ‘Centertown Social’ Adding its Final Touches – WENY News

    Elmira’s New Entertainment Venue ‘Centertown Social’ Adding its Final Touches – WENY News

    Bella Thorne Shows Off Her Toned Abs in Crop Top – Yahoo

    Bella Thorne Shows Off Her Toned Abs in a Chic Crop Top

    Bricktown continues to thrive as OKC’s entertainment district – OKC VeloCity

    Bricktown Shines as Oklahoma City’s Premier Entertainment Hotspot

    This Haunting ‘60s Country Song Is Even More Tragic Than You Remember – Yahoo

    This Haunting ’60s Country Song Will Break Your Heart All Over Again

  • General
  • Health
  • News

    Cracking the Code: Why China’s Economic Challenges Aren’t Shaking Markets, Unlike America’s” – Bloomberg

    Trump’s Narrow Window to Spread the Truth About Harris

    Trump’s Narrow Window to Spread the Truth About Harris

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Trending Tags

    • Trump Inauguration
    • United Stated
    • White House
    • Market Stories
    • Election Results
  • Science
  • Sports
  • Technology
    ‘New frontier’: Austin leaders start discussions on air taxi technology – KXAN Austin

    Austin Leaders Ignite Exciting Conversations on the Future of Air Taxi Technology

    How a Gemma model helped discover a new potential cancer therapy pathway – blog.google

    How a Gemma Model Revealed a Breakthrough Pathway for Cancer Treatment

    Italian Technology in Manufacturing: Supporting North American Industries and Keeping Production Local – Thomasnet

    How Italian Technology is Revolutionizing North American Manufacturing and Boosting Local Production

    Guide to Proteomics Project Planning: Sample Preparation Strategies – Technology Networks

    Guide to Proteomics Project Planning: Sample Preparation Strategies – Technology Networks

    DLG−Agrifuture Concept Winners 2025 announced – Visionary Ideas in agricultural technology recognized – TheNewsMarket

    Meet the Visionary Innovators Revolutionizing Agricultural Technology in 2025

    Spanning the Gulf: Global Defence Technology 155 – Army Technology

    Spanning the Gulf: Exploring Cutting-Edge Global Defence Technology

    Trending Tags

    • Nintendo Switch
    • CES 2017
    • Playstation 4 Pro
    • Mark Zuckerberg
No Result
View All Result
Earth-News
No Result
View All Result
Home Science

Researchers Refute a Widespread Belief About Online Algorithms

November 20, 2023
in Science
Researchers Refute a Widespread Belief About Online Algorithms
Share on FacebookShare on Twitter

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.

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, where k is the number of agents. This is called the randomized k-server conjecture, and researchers have shown that it’s true for some spaces, or specific collections of points (the equivalent of houses that could call for plumbers). But it hasn’t been proved for all cases.

Like most researchers, Rabani and his co-authors — Sébastien Bubeck of Microsoft Research and Christian Coester of the University of Oxford — figured the conjecture was true. “I had no reason to doubt it,” Coester said.

But that started to change as they worked on another online problem. It had connections to the k-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 for the k-server problem was overly optimistic.

Rabani said it was Coester who first suggested that the randomized k-server conjecture might be false. “As soon as he said it, it all made sense.”

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. 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’s 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.

The choices reminded Rabani of the Robert Frost poem “The Road Not Taken,” in which a traveler contemplates two potential paths through a yellow wood. “We just apply the poem recursively,” he joked. “And then things go really bad.”

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

This work, which won a Best Paper Award at the 2023 Symposium on Theory of Computing, marks a “solidly theoretical” 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’t 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.

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 “highlights the power” of the technique the authors used, Gupta said.

Perhaps those future findings will defy researchers’ expectations as this one did, Rabani said. “This is one of the cases where it feels really good to be wrong.”

Quanta is conducting a series of surveys to better serve our audience. Take our computer science reader survey and you will be entered to win free Quanta merchandise.

>>> Read full article>>>
Copyright for syndicated content belongs to the linked Source : Quanta Magazine – https://www.quantamagazine.org/researchers-refute-a-widespread-belief-about-online-algorithms-20231120/

Tags: RefuteResearchersscience
Previous Post

NSF Director Panchanathan headlines the Canadian Science Policy Conference in Ottawa, signs international collaboration arrangement

Next Post

X’s CEO tells staff data will show efforts to fight hate, as advertisers flee

Ecological restoration in Poland: an experiment successfully transformed a mining landfill into a vegetal oasis – Noticias Ambientales

From Barren Mines to Vibrant Green Havens: Poland’s Incredible Ecological Comeback

October 19, 2025

Azillah Binti-Othman: Her Path to a Career in Radiation Science – International Atomic Energy Agency

October 19, 2025
Why foods like Dubai chocolate go viral – Popular Science

Uncovering the Unexpected Reasons Behind Dubai’s Viral Chocolate Craze

October 19, 2025
The Genius Costco Hot Dog Hack We Wish We’d Known About Sooner – Yahoo

The Genius Costco Hot Dog Hack You’ll Wish You Knew Sooner

October 19, 2025
‘New frontier’: Austin leaders start discussions on air taxi technology – KXAN Austin

Austin Leaders Ignite Exciting Conversations on the Future of Air Taxi Technology

October 19, 2025
Tomorrow’s Top 25 Today projects college football rankings entering Week 9 – CBS Sports

Tomorrow’s Top 25 College Football Rankings Unveiled Ahead of Week 9

October 19, 2025
Lisa Tertsch, Matthew Hauser become world triathlon champions after winning season finals – ABC News – Breaking News, Latest News and Videos

Lisa Tertsch, Matthew Hauser become world triathlon champions after winning season finals – ABC News – Breaking News, Latest News and Videos

October 19, 2025
Why Trump is giving Argentina a $20 billion lifeline to help its flailing economy – PBS

Why Trump Is Proposing a $20 Billion Lifeline to Save Argentina’s Faltering Economy

October 19, 2025
Placer County town of Loomis considers entertainment zone for downtown – CBS News

Loomis Unveils Thrilling New Entertainment Zone to Revitalize Downtown

October 19, 2025

Miriam Miedzinski-Ballin, trailblazer who made mental health part of first aid, dies at 48 – The Times of Israel

October 19, 2025

Categories

Archives

October 2025
M T W T F S S
 12345
6789101112
13141516171819
20212223242526
2728293031  
« Sep    
Earth-News.info

The Earth News is an independent English-language daily published Website from all around the World News

Browse by Category

  • Business (20,132)
  • Ecology (876)
  • Economy (897)
  • Entertainment (21,768)
  • General (17,691)
  • Health (9,938)
  • Lifestyle (910)
  • News (22,149)
  • People (898)
  • Politics (907)
  • Science (16,108)
  • Sports (21,397)
  • Technology (15,877)
  • World (880)

Recent News

Ecological restoration in Poland: an experiment successfully transformed a mining landfill into a vegetal oasis – Noticias Ambientales

From Barren Mines to Vibrant Green Havens: Poland’s Incredible Ecological Comeback

October 19, 2025

Azillah Binti-Othman: Her Path to a Career in Radiation Science – International Atomic Energy Agency

October 19, 2025
  • About
  • Advertise
  • Privacy & Policy
  • Contact

© 2023 earth-news.info

No Result
View All Result

© 2023 earth-news.info

No Result
View All Result

© 2023 earth-news.info

Go to mobile version