Featured Research

from universities, journals, and other organizations

University Of Iowa Professor Wins Again, Solves 40-Year-Old Mathematics Problem

Date:
October 15, 2001
Source:
University Of Iowa
Summary:
A University of Iowa researcher has helped solve an applied mathematics problem that had challenged computer scientists for 40 years, just one year after he helped find the solution to a 32-year-old problem.

A University of Iowa researcher has helped solve an applied mathematics problem that had challenged computer scientists for 40 years, just one year after he helped find the solution to a 32-year-old problem.

Related Articles


Kurt Anstreicher, professor of management sciences in the Henry B. Tippie College of Business, working with Nathan Brixius, who earned his doctoral degree in computer science from the UI College of Liberal Arts and Sciences in 2000, discovered how to link 34 computer components together on a 9-by-4 grid using the shortest-possible wiring scheme. The problem, formally know as "ste36a" and based on the design of a UNIVAC computer, was posed by researcher Leon Steinberg in 1961. The solution to the problem was scheduled to be presented at a Friday, Oct. 12 mathematics workshop held in Berlin, Germany.

Anstreicher says that because there are only 36 possible locations for components, with a total of 2,625 connections between them, the wiring problem may not seem very difficult. However, the number of possible solutions is about "5E40," or the number represented by the number 5 followed by 40 zeros. The algorithm that solved the problem considered about 1.8 billion sub-problems and required about 18 days running on a single 800-megahertz personal computer.

"This may sound like a lot, but it is in fact much less time than anyone would ever have thought possible," Anstreicher says. In the summer of 2000 Anstreicher, Brixius, and colleagues from Argonne National Lab used an average of 650 computers for a week to solve the "nug30" problem, posed in 1968. "People who work on such problems thought that the wiring problem would be harder to solve than nug30, but it turned out to be much easier," says Anstreicher. "We learned techniques in the course of solving nug30 that were very effective in speeding up the solution of Steinberg's problem."

Like the nug30 problem, the wiring problem is a "quadratic assignment problem," or QAP. Such problems arise in the field of location theory, and are known to be extremely difficult to solve. Other applications of QAPs include designing computer chips, and arranging departments within a hospital so as to minimize the total distance that patients must travel between them.

Brixius, a Cedar Falls native who works for Microsoft Corporation in Redmond, Wash., says the knowledge he gains from such projects helps him in his work developing project management and scheduling software. "Microsoft is not in the business of solving 40-year-old wiring problems, but there are underlying similarities between ste36a and many scheduling problems," says Brixius. "The techniques we used to solve Steinberg's problem can be adapted to help solve problems I encounter in my day-to-day work."

Looking to the future, Anstreicher says, "Problems like nug30 and ste36a were, until very recently, considered intractable. With continued improvements in algorithms and hardware, solving them could be commonplace in the not-too-distant future." Adds Brixius, "I am hopeful that our work will inspire further research that leads to even better methods for taking on difficult problems in this area."


Story Source:

The above story is based on materials provided by University Of Iowa. Note: Materials may be edited for content and length.


Cite This Page:

University Of Iowa. "University Of Iowa Professor Wins Again, Solves 40-Year-Old Mathematics Problem." ScienceDaily. ScienceDaily, 15 October 2001. <www.sciencedaily.com/releases/2001/10/011015055814.htm>.
University Of Iowa. (2001, October 15). University Of Iowa Professor Wins Again, Solves 40-Year-Old Mathematics Problem. ScienceDaily. Retrieved October 24, 2014 from www.sciencedaily.com/releases/2001/10/011015055814.htm
University Of Iowa. "University Of Iowa Professor Wins Again, Solves 40-Year-Old Mathematics Problem." ScienceDaily. www.sciencedaily.com/releases/2001/10/011015055814.htm (accessed October 24, 2014).

Share This



More Computers & Math News

Friday, October 24, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

The Best Apps to Organize Your Life

The Best Apps to Organize Your Life

Buzz60 (Oct. 23, 2014) — Need help organizing your bills, schedules and other things? Ko Im (@konakafe) has the best apps to help you stay on top of it all! Video provided by Buzz60
Powered by NewsLook.com
Nike And Apple Team Up To Create Wearable ... Something

Nike And Apple Team Up To Create Wearable ... Something

Newsy (Oct. 23, 2014) — For those looking for wearable tech that's significantly less nerdy than Google Glass, Nike CEO Mark Parker says don't worry, It's on the way. Video provided by Newsy
Powered by NewsLook.com
Chameleon Camouflage to Give Tanks Cloaking Capabilities

Chameleon Camouflage to Give Tanks Cloaking Capabilities

Reuters - Innovations Video Online (Oct. 22, 2014) — Inspired by the way a chameleon changes its colour to disguise itself; scientists in Poland want to replace traditional camouflage paint with thousands of electrochromic plates that will continuously change colour to blend with its surroundings. The first PL-01 concept tank prototype will be tested within a few years, with scientists predicting that a similar technology could even be woven into the fabric of a soldiers' clothing making them virtually invisible to the naked eye. Matthew Stock reports. Video provided by Reuters
Powered by NewsLook.com
Internet of Things Aims to Smarten Your Life

Internet of Things Aims to Smarten Your Life

AP (Oct. 22, 2014) — As more and more Bluetooth-enabled devices are reaching consumers, developers are busy connecting them together as part of the Internet of Things. (Oct. 22) Video provided by AP
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
 
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:  

Breaking News:

Strange & Offbeat Stories

 

Space & Time

Matter & Energy

Computers & Math

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:  

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile iPhone Android Web
Follow Facebook Twitter Google+
Subscribe RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins