* . *
  • About
  • Advertise
  • Privacy & Policy
  • Contact
Thursday, July 3, 2025
Earth-News
  • Home
  • Business
  • Entertainment
    Neil Young Plays Rare Full-Band ‘Ambulance Blues’ With The Chrome Hearts – Yahoo

    Neil Young Stuns Fans with Rare Full-Band Performance of ‘Ambulance Blues’ Alongside The Chrome Hearts

    BTS Announce Their Big Return and Yes, They Already Have Some Major Plans in the Works – Yahoo

    BTS Announce Their Big Return and Yes, They Already Have Some Major Plans in the Works – Yahoo

    Nantucket Dance Festival opens July 8 – The Inquirer and Mirror

    Nantucket Dance Festival Launches with Thrilling Performances Beginning July 8

    A Secret Society, Ritualistic Killings, and a Century-Old Curse Netflix and YRF Entertainment’s ‘Mandala Murders’ Premieres July 25 – About Netflix

    A Secret Society, Ritualistic Killings, and a Century-Old Curse: Dive into the Chilling World of ‘Mandala Murders’ Premiering July 25

    Susquehanna Raises Penn Entertainment Inc. (PENN) Price Target. – Yahoo Finance

    Susquehanna Raises Price Target for Penn Entertainment Inc. (PENN)

    George Lopez is coming to Spokane – KXLY.com

    George Lopez is coming to Spokane – KXLY.com

  • 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
    Inspira Technologies Secures Landmark $22.5M Deal: Major Revenue Breakthrough After FDA Clearance – Stock Titan

    Inspira Technologies Secures Landmark $22.5M Deal: Major Revenue Breakthrough After FDA Clearance – Stock Titan

    Meiwu Technology Company Limited and Shenzhen Zhinuo – GlobeNewswire

    Meiwu Technology Company Limited and Shenzhen Zhinuo – GlobeNewswire

    Owls inspire new revolutionary noise reduction technology – KTEN

    Owls inspire new revolutionary noise reduction technology – KTEN

    New center coming to Mizzou will focus on energy research and technology – Columbia Missourian

    Mizzou Launches Innovative New Center Dedicated to Energy Research and Technology

    Mirrors in space and underwater curtains: can technology buy us enough time to save the Arctic ice caps? – The Guardian

    Can Technology Like Space Mirrors and Underwater Curtains Buy Us Time to Save the Arctic Ice Caps?

    Naples restaurant owner prepares for hurricane season with new flood technology – Fox4Now.com

    Naples restaurant owner prepares for hurricane season with new flood technology – Fox4Now.com

    Trending Tags

    • Nintendo Switch
    • CES 2017
    • Playstation 4 Pro
    • Mark Zuckerberg
No Result
View All Result
  • Home
  • Business
  • Entertainment
    Neil Young Plays Rare Full-Band ‘Ambulance Blues’ With The Chrome Hearts – Yahoo

    Neil Young Stuns Fans with Rare Full-Band Performance of ‘Ambulance Blues’ Alongside The Chrome Hearts

    BTS Announce Their Big Return and Yes, They Already Have Some Major Plans in the Works – Yahoo

    BTS Announce Their Big Return and Yes, They Already Have Some Major Plans in the Works – Yahoo

    Nantucket Dance Festival opens July 8 – The Inquirer and Mirror

    Nantucket Dance Festival Launches with Thrilling Performances Beginning July 8

    A Secret Society, Ritualistic Killings, and a Century-Old Curse Netflix and YRF Entertainment’s ‘Mandala Murders’ Premieres July 25 – About Netflix

    A Secret Society, Ritualistic Killings, and a Century-Old Curse: Dive into the Chilling World of ‘Mandala Murders’ Premiering July 25

    Susquehanna Raises Penn Entertainment Inc. (PENN) Price Target. – Yahoo Finance

    Susquehanna Raises Price Target for Penn Entertainment Inc. (PENN)

    George Lopez is coming to Spokane – KXLY.com

    George Lopez is coming to Spokane – KXLY.com

  • 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
    Inspira Technologies Secures Landmark $22.5M Deal: Major Revenue Breakthrough After FDA Clearance – Stock Titan

    Inspira Technologies Secures Landmark $22.5M Deal: Major Revenue Breakthrough After FDA Clearance – Stock Titan

    Meiwu Technology Company Limited and Shenzhen Zhinuo – GlobeNewswire

    Meiwu Technology Company Limited and Shenzhen Zhinuo – GlobeNewswire

    Owls inspire new revolutionary noise reduction technology – KTEN

    Owls inspire new revolutionary noise reduction technology – KTEN

    New center coming to Mizzou will focus on energy research and technology – Columbia Missourian

    Mizzou Launches Innovative New Center Dedicated to Energy Research and Technology

    Mirrors in space and underwater curtains: can technology buy us enough time to save the Arctic ice caps? – The Guardian

    Can Technology Like Space Mirrors and Underwater Curtains Buy Us Time to Save the Arctic Ice Caps?

    Naples restaurant owner prepares for hurricane season with new flood technology – Fox4Now.com

    Naples restaurant owner prepares for hurricane season with new flood technology – Fox4Now.com

    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

Neil Young Plays Rare Full-Band ‘Ambulance Blues’ With The Chrome Hearts – Yahoo

Neil Young Stuns Fans with Rare Full-Band Performance of ‘Ambulance Blues’ Alongside The Chrome Hearts

July 3, 2025
Registered nurse explains reasoning for health care workers strike against WellSpan Health – WGAL

Registered nurse explains reasoning for health care workers strike against WellSpan Health – WGAL

July 3, 2025
Judge blocks Trump asylum ban at southern border, says he exceeded authority – NBC News

Judge blocks Trump asylum ban at southern border, says he exceeded authority – NBC News

July 3, 2025

Stellantis Revives SRT: High-Performance Street and Racing Division Makes a Triumphant Return

July 3, 2025
Josh Hart Delivers Promise to Fans After Knicks’ Recent Move – Yahoo Sports

Josh Hart Delivers Promise to Fans After Knicks’ Recent Move – Yahoo Sports

July 3, 2025
LensToLens: Wetlands guard bird species from plateau to urban landscape – Xinhua

How Wetlands Safeguard Bird Species Across Plateaus and Urban Landscapes

July 3, 2025
Commentary: Vatican defends science from politics, ideology and misinformation – The Salt Lake Tribune

Vatican Takes a Bold Stand: Defending Science from Politics, Ideology, and Misinformation

July 2, 2025
Scientists Merged 3 Human Brains by Thought Alone – Popular Mechanics

Scientists Achieve Mind-Blowing Feat by Merging Three Human Brains Through Thought Alone

July 3, 2025
Retired woman shares inside look at lifestyle after moving into unconventional tiny home: ‘The best decision I’ve ever made’ – The Cool Down

Retired Woman Reveals Life-Changing Joys of Living in an Unconventional Tiny Home: “The Best Decision I’ve Ever Made

July 2, 2025
​​World Rural Development Day: Refugee-Led Farming Projects That Are Feeding the World – USA for UNHCR

​​World Rural Development Day: Refugee-Led Farming Projects That Are Feeding the World – USA for UNHCR

July 2, 2025

Categories

Archives

July 2025
MTWTFSS
 123456
78910111213
14151617181920
21222324252627
28293031 
« Jun    
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 (702)
  • Economy (728)
  • Entertainment (21,617)
  • General (15,684)
  • Health (9,768)
  • Lifestyle (732)
  • News (22,149)
  • People (729)
  • Politics (736)
  • Science (15,946)
  • Sports (21,226)
  • Technology (15,712)
  • World (709)

Recent News

Neil Young Plays Rare Full-Band ‘Ambulance Blues’ With The Chrome Hearts – Yahoo

Neil Young Stuns Fans with Rare Full-Band Performance of ‘Ambulance Blues’ Alongside The Chrome Hearts

July 3, 2025
Registered nurse explains reasoning for health care workers strike against WellSpan Health – WGAL

Registered nurse explains reasoning for health care workers strike against WellSpan Health – WGAL

July 3, 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