* . *
  • About
  • Advertise
  • Privacy & Policy
  • Contact
Friday, October 3, 2025
Earth-News
  • Home
  • Business
  • Entertainment
    Taylor Swift Releases New Album The Life of a Showgirl : Listen and Read the Full Credits – Yahoo

    Taylor Swift Releases New Album The Life of a Showgirl : Listen and Read the Full Credits – Yahoo

    Toni Braxton Is Turning Her Biggest Hits Into Lifetime Movies – Yahoo

    Toni Braxton Is Turning Her Biggest Hits Into Lifetime Movies – Yahoo

    Major airline to offer new in-flight entertainment options for passengers – PennLive.com

    Major airline to offer new in-flight entertainment options for passengers – PennLive.com

    Penn State-Themed Restaurant and Entertainment Spot Happy Valley Live Set to Open in State College – StateCollege.com

    Penn State-Themed Restaurant and Entertainment Spot Happy Valley Live Set to Open in State College – StateCollege.com

    The Police Made Chart History With This 1979 Hit Nearly 50 Years Ago – Yahoo

    How The Police Changed Music Forever with Their Iconic 1979 Hit Nearly 50 Years Ago

    Good Deed Entertainment Acquires Worldwide Rights To Liza Mandelup’s Documentary ‘Caterpillar’ – Deadline

    Good Deed Entertainment Lands Global Rights to Liza Mandelup’s Captivating Documentary ‘Caterpillar

  • 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
    Technology Is Becoming More Important Than Humans In CX – No Jitter

    Technology Is Becoming More Important Than Humans In CX – No Jitter

    A Tech Expo Shows What China Can Make, but Not Who’ll Buy It All – The New York Times

    Inside China’s Tech Expo: Cutting-Edge Innovations Face Uncertain Demand

    Steampunk Metal Oval Technology Sense Sunglasses Personality Handmade Chain Multicolor Sunglasses UV400 – The San Joaquin Valley Sun

    Steampunk Metal Oval Sunglasses with Handmade Multicolor Chain – Bold UV400 Protection and Unique Style

    STELLA Automotive AI Appoints Fred Seidelman as Chief Technology Officer – Yahoo Finance

    STELLA Automotive AI Appoints Fred Seidelman as New Chief Technology Officer

    Saving Energy and Money with Smart Technology – Terms of Service with Clare Duffy – Podcast on CNN Podcasts – CNN

    Saving Energy and Money with Smart Technology – Terms of Service with Clare Duffy – Podcast on CNN Podcasts – CNN

    Four Strategic Signals Technology Leaders Are Tuning In To – SPONSOR CONTENT FROM ARM – Harvard Business Review

    Four Essential Strategic Signals Every Technology Leader Should Watch

    Trending Tags

    • Nintendo Switch
    • CES 2017
    • Playstation 4 Pro
    • Mark Zuckerberg
No Result
View All Result
  • Home
  • Business
  • Entertainment
    Taylor Swift Releases New Album The Life of a Showgirl : Listen and Read the Full Credits – Yahoo

    Taylor Swift Releases New Album The Life of a Showgirl : Listen and Read the Full Credits – Yahoo

    Toni Braxton Is Turning Her Biggest Hits Into Lifetime Movies – Yahoo

    Toni Braxton Is Turning Her Biggest Hits Into Lifetime Movies – Yahoo

    Major airline to offer new in-flight entertainment options for passengers – PennLive.com

    Major airline to offer new in-flight entertainment options for passengers – PennLive.com

    Penn State-Themed Restaurant and Entertainment Spot Happy Valley Live Set to Open in State College – StateCollege.com

    Penn State-Themed Restaurant and Entertainment Spot Happy Valley Live Set to Open in State College – StateCollege.com

    The Police Made Chart History With This 1979 Hit Nearly 50 Years Ago – Yahoo

    How The Police Changed Music Forever with Their Iconic 1979 Hit Nearly 50 Years Ago

    Good Deed Entertainment Acquires Worldwide Rights To Liza Mandelup’s Documentary ‘Caterpillar’ – Deadline

    Good Deed Entertainment Lands Global Rights to Liza Mandelup’s Captivating Documentary ‘Caterpillar

  • 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
    Technology Is Becoming More Important Than Humans In CX – No Jitter

    Technology Is Becoming More Important Than Humans In CX – No Jitter

    A Tech Expo Shows What China Can Make, but Not Who’ll Buy It All – The New York Times

    Inside China’s Tech Expo: Cutting-Edge Innovations Face Uncertain Demand

    Steampunk Metal Oval Technology Sense Sunglasses Personality Handmade Chain Multicolor Sunglasses UV400 – The San Joaquin Valley Sun

    Steampunk Metal Oval Sunglasses with Handmade Multicolor Chain – Bold UV400 Protection and Unique Style

    STELLA Automotive AI Appoints Fred Seidelman as Chief Technology Officer – Yahoo Finance

    STELLA Automotive AI Appoints Fred Seidelman as New Chief Technology Officer

    Saving Energy and Money with Smart Technology – Terms of Service with Clare Duffy – Podcast on CNN Podcasts – CNN

    Saving Energy and Money with Smart Technology – Terms of Service with Clare Duffy – Podcast on CNN Podcasts – CNN

    Four Strategic Signals Technology Leaders Are Tuning In To – SPONSOR CONTENT FROM ARM – Harvard Business Review

    Four Essential Strategic Signals Every Technology Leader Should Watch

    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 Approach New Speed Limit for Seminal Problem

January 29, 2024
in Science
Researchers Approach New Speed Limit for Seminal Problem
Share on FacebookShare on Twitter

That’s not to say it’s easy work. It wasn’t until 1983 that the mathematician Hendrik Lenstra proved that the general problem was even solvable, providing the first algorithm that could do it. Lenstra thought about ILP geometrically. First, he turned the inequalities at the heart of ILP into a convex shape, such as any regular polygon. This shape represents the constraints of the individual problem you’re solving, whether it’s couch production or airline scheduling, so the shape’s interior corresponds to all possible values that could solve the inequalities, and thus the problem. Lenstra called this shape the convex body. The problem’s dimension influences the dimension of this shape: With two variables it takes the form of a flat polygon; in three dimensions it is a Platonic solid, and so on.

Lenstra next imagined all the integers as an infinite set of grid points, known in mathematics as a lattice. A two-dimensional version looks like a sea of dots, and in three dimensions it looks like the points where steel beams in a building connect. The dimension of the lattice also depends on the dimension of a given problem.

To solve a given ILP problem, Lenstra showed that you just look for where the possible solutions meet the set of integers: at the intersection of the convex body and the lattice. And he came up with an algorithm that could search this space exhaustively — but to be effective, it sometimes had to break the problem up into pieces of smaller dimensions, adding many steps to the runtime.

In the following years, several researchers explored how to make this algorithm run faster. In 1988, Ravi Kannan and László Lovász introduced a concept called the covering radius, borrowed from the study of error-correcting codes, to help the convex body and lattice intersect more efficiently. Roughly, the covering radius makes sure that the convex body always contains at least one integer point, no matter where you place it on the lattice. As a result, the size of the covering radius also determines how efficiently you can solve the ILP problem.

So it all came down to determining the size of the ideal covering radius. Unfortunately, this proved to be a hard problem on its own, and the best Kannan and Lovász could do was narrow down a possible value by searching for upper and lower bounds. They showed that the upper bound — the maximum size of the covering radius — scaled up linearly with the dimension. This was pretty fast, but not enough to significantly speed up the ILP runtime. Over the next 30 years, other researchers could only do slightly better.

What ultimately helped Reis and Rothvoss break through was an unrelated mathematical result that focused purely on lattices. In 2016, Oded Regev and Stephens-Davidowitz showed, in effect, how many lattice points could fit within a specific shape. Reis and Rothvoss applied this to other shapes, which allowed them to better estimate the number of lattice points contained in an ILP covering radius, lowering the upper bound. “The latest breakthrough came with the realization that you can actually do other kinds of shapes,” Regev said.

This new tightened upper bound was a vast improvement, allowing Reis and Rothvoss to achieve a dramatic speedup of the overall ILP algorithm. Their work brings the runtime to (log n)O(n), where n is the number of variables and O(n)means it scales linearly with n. (This expression is considered “almost” the same as the run time of the binary problem.)

“It’s a triumph at the intersection of math, computer science and geometry,” said Daniel Dadush of the national research institute CWI in the Netherlands, who helped pioneer the algorithm Reis and Rothvoss used to measure the ILP runtime.

For now, the new algorithm hasn’t actually been used to solve any logistical problems, since it would take too much work updating today’s programs to make use of it. But for Rothvoss, that’s beside the point. “It’s about the theoretical understanding of a problem that has fundamental applications,” he said.

As to whether the computational efficiency of ILP could be further improved, researchers are still hopeful that they’ll keep approaching the ideal runtime — but not anytime soon. “That would require a fundamentally new idea,” Vempala said.

>>> Read full article>>>
Copyright for syndicated content belongs to the linked Source : Quanta Magazine – https://www.quantamagazine.org/researchers-approach-new-speed-limit-for-seminal-problem-20240129/

Tags: ApproachResearchersscience
Previous Post

Phoenix water protest marred by clashes with police

Next Post

Transforming Fertilizer Production: True Mechanism of Ammonia Catalysis Revealed

FIRST LOOK: Official match ball of FIFA World Cup ‘26 – Yahoo Sports

Get an Exclusive First Look at the Official Match Ball of FIFA World Cup 2026!

October 3, 2025
Arts economy grows, but funding lags on Long Island – Long Island Business News

Long Island’s Arts Economy Thrives Despite Ongoing Funding Challenges

October 3, 2025
Taylor Swift Releases New Album The Life of a Showgirl : Listen and Read the Full Credits – Yahoo

Taylor Swift Releases New Album The Life of a Showgirl : Listen and Read the Full Credits – Yahoo

October 3, 2025
HIV pioneer Dr. William Valenti retires, leaving lasting impact on health community – 13wham.com

HIV Pioneer Dr. William Valenti Retires, Leaving an Enduring Impact on the Health Community

October 3, 2025
As the shutdown drags on, the threat of permanent cuts is mired in politics – NPR

As the Shutdown Continues, the Risk of Lasting Cuts Grows Amid Political Stalemate

October 3, 2025
West Seattle Ecology Fair 2025, report #2: Heat waves aren’t just a source of discomfort – West Seattle Blog…

West Seattle Ecology Fair 2025: Uncovering the Hidden Impacts of Heat Waves Beyond Our Comfort

October 3, 2025
Roam The Huntington after dark at an atmospheric ‘Strange Science’ night – NBC Los Angeles

Uncover the Secrets of The Huntington After Dark at the Enchanting ‘Strange Science’ Night

October 3, 2025
Viral apple cider vinegar weight loss study retracted for flawed science – ScienceDaily

Viral apple cider vinegar weight loss study retracted for flawed science – ScienceDaily

October 3, 2025
A love letter to the garden – The Inquirer and Mirror

A Heartfelt Ode to the Garden: Celebrating Nature’s Timeless Beauty

October 3, 2025
Technology Is Becoming More Important Than Humans In CX – No Jitter

Technology Is Becoming More Important Than Humans In CX – No Jitter

October 3, 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 (848)
  • Economy (869)
  • Entertainment (21,743)
  • General (17,380)
  • Health (9,912)
  • Lifestyle (881)
  • News (22,149)
  • People (870)
  • Politics (880)
  • Science (16,079)
  • Sports (21,369)
  • Technology (15,852)
  • World (852)

Recent News

FIRST LOOK: Official match ball of FIFA World Cup ‘26 – Yahoo Sports

Get an Exclusive First Look at the Official Match Ball of FIFA World Cup 2026!

October 3, 2025
Arts economy grows, but funding lags on Long Island – Long Island Business News

Long Island’s Arts Economy Thrives Despite Ongoing Funding Challenges

October 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