Mathematics makes wireless networks more efficient

How many cellphone masts should be placed in order to reach everyone? If there are ten additional stations eligible for grants, where can these be placed best? PhD student Erik Jan van Leeuwen of the Centrum Wiskunde & Informatica(CWI) in Amsterdam described the problems with geometric models.

With the techniques he developed, it is possible to search the best possible solutions much more efficiently: sometimes tens of thousands of times faster than previous methods. In 2008 he received the Philips Wiskunde Prijs for PhD students. On June 16 he will receive his PhD-degree from the University of Amsterdam on his thesis ‘Optimization and Approximation on Systems of Geometric Objects’.

Many practical problems have a geometric component. "Not only the placement of cellphone masts or building a 'backbone' in sensor networks, but the emplacement of places on a map without overlapping names also falls under this category," says Van Leeuwen. "With the computer it’s not possible to calculate the best solutions quickly." The problems Van Leeuwen investigated are categorized as very complex NP-hard problems, just as the well know traveling salesman problem. "The hard thing is that the number of potential solutions that needs to be researched grows explosive in the number of antennas, for example," says van Leeuwen.

The researcher showed however that computers are capable to find almost optimal solutions quickly. Therefore he used shifting techniques, with which he delivered significant improvements on previous results. His method allows a very small error margin that is adjustable. The necessary calculations are thousands of times shorter than previous methods. In some cases could even be shown that no faster method exists to enter these error margins. The research is funded by the program Bsik BRICKS.