max planck institut
informatik

# Spotlight: Released Wednesday, 25 May 2011

## Solving network design problems can be (NP-)hard, but you can come close

### Anke van Zuylen

Dr. Anke van Zuylen developed efficient algorithms that find solutions for hard network design problems, which are guaranteed to be close to optimal. Before her work, there were only efficient algorithms known that produce solutions that are good in expectation. Van Zuylen's algorithms are the first to remove the uncertainty about the quality of the solution.

Network design concerns finding cost efficient ways of setting up a network that satisfies given requirements. These problems arise for example when designing computer and telecommunication networks, when choosing facility locations, server placement, and so on. There are many issues that can play a role in these kinds of problems, such as robustness (we don't want a large portion of the network to become disconnected if one link in a network goes down), economic considerations (it makes no sense to connect a remote customer at high cost, if this customer is not going to pay much) and buy-at-bulk cost efficiencies.

Many of these problems are NP-hard; this means that the running time of the only algorithms that we know for optimally solving these problems grows exponentially with the size of the problem (and it is widely believed that this behavior is inherent to the problems). An approximation algorithm is an efficient algorithm for solving such a problem, i.e. an algorithm for which the running time grows polynomially rather than exponentially. The solution returned by an approximation algorithm is not necessarily optimal; however, it is guaranteed not to be too far from optimal.

Dr. Van Zuylen's research concentrates on designing and analyzing efficient algorithms for problems that are computationally hard. She focuses in particular on problems arising in network design and information science.

In her research, she worked on designing approximation algorithms for a large class of network design problems. The simplest of these is the problem in which we want to connect a known set of demand points to a single supply point, and we have a choice of either buying or renting links in the network. If we rent a link, any demand point that gets supplied through this link needs to pay for using it, and if we buy a link, we pay a single but higher cost for usage. Together with her coauthor, Dr. David P. Williamson, A. van Zuylen showed how to use the optimal solution of a certain linear programming relaxation of this problem to decide which links to buy or rent, and prove that this gives a solution that is not much more expensive than the optimal solution. The method they developed has been successfully used by other researchers for related problems.

A second application area on which Dr. Van Zuylen's research focuses is information science. We now have the ability to gather enormous amounts of data, and there are numerous challenges in organizing this data into usable information: Researchers are still working on developing better web search engines. In biology, microarray experiments supply information about expression levels of thousands of genes, and this data needs to be organized and analyzed. Internet resellers would like to give customized recommendations to users based on known preferences, user input, and previous purchases.

Dr. Van Zuylen has developed approximation algorithms for aggregating information from different sources: for example, ranking a list of candidates based on the different preference orders given by the members of a search committee, finding a good clustering of a set of genes based on the outcomes of different microarray experiments or clustering web pages based on similarity scores.

Besides developing algorithms with theoretical guarantees, Dr. Van Zuylen is interested in studying what these guarantees mean in practice, and comparing these algorithms to approaches which may not necessarily have theoretical guarantees.

Dr. Van Zuylen graduated in 2008 with a Ph.D. in Operations Research from Cornell University. Afterwards she stayed for two years as a postdoctoral researcher at the Institute for Theoretical Computer Science, in Bejing, China and has joined the Department for Algorithms and Complexity of the Max Planck Institute for Informatics (MPI-INF) in September of 2010. (http://www.mpi-inf.mpg.de/~anke/) She has received multiple awards for her research and teaching and is the winner of the Lise Meitner postdoctoral scholarship of MPI-INF for 2010. The Max Planck Institute for Informatics offers this scholarship to attract and support excellent female postdoctoral scientists in their careers. Besides a two-year research scholarship, Lise Meitner scholars receive an additional yearly budget for travel and work-related expenses.