Recent Ph.D. Graduate Van Zuylen Wins Research Competition Awards

  Anke van Zuylen in front of the Tsinghua University gate. 

At the 16th Annual European Symposium on Algorithms (ESA), held at Karlsruhe University, Germany in September, 2008, Anke van Zuylen's work was designated as the Best Student Paper in the Design and Analysis track. The following month, at the Annual Meeting of the Institute for Operations Research and the Management Sciences (INFORMS) in Washington, D.C., a different paper by Van Zuylen was one of two receiving Honorable Mention (effectively 3rd place) in the George Nicholson Student Paper Competition. Van Zuylen is currently a postdoctoral associate at the Institute for Theoretical Computer Science at Tsinghua University in Beijing, China.

Both papers deal with the construction and analysis of algorithms for several problems known to be computationally difficult, and are derived from van Zuylen's Ph.D. thesis. The ESA paper, Deterministic Sampling Algorithms for Network Design, covers problems that arise in the design of networks arising in supply chains, telecommunications, electronic circuits and other applications. The time needed to compute optimal solutions to such problems is known to grow exponentially with the number of components in the network, so the focus is on the development of algorithms that guarantee getting to within a known factor of optimality without excessive computation. Van Zuylen has identified a means of selecting a non-random sample problem from the full network problem, the approximate solution to which can be readily augmented to an approximate solution, having the guaranteed proximity to optimality, for the full problem. The problems for which such an approach is effective are those in which the designed network is expected to have a backbone structure, and the non-random sample identifies a good set of nodes that should be on the backbone. 

The INFORMS paper, Deterministic Pivoting Algorithms for Rank Aggregation and Other Ranking and Clustering Problems, examines the problem of establishing a full ranking of elements, such as web pages, from partial rankings such as those produced by individual search engines, or from incomplete and possibly inconsistent pair-wise comparisons of the elements. The objective is to find a full ranking that is as close as possible to the input information. With her Ph.D. advisor David Williamson, Van Zuylen developed algorithms which deliver rankings within a known factor (better than 2) of the optimum. Compared to previous approaches that are only able to guarantee performance on the average, these algorithms eliminate the need to take certain process steps at random. In the paper, similar approaches are used in algorithms that form clusters of similar elements in a population (such as web pages), maximizing the similarity of elements in the same cluster and minimizing the similarity between elements in different clusters. 

Van Zuylen and her husband Frans Schalekamp Ph.D. '07 are both at the Institute at Tsinghua, and will stay there for the coming year. Together, they have designed and taught a new course for the 30 top Tsinghua students in computer science, intended to give students a broad introduction to the field, including algorithms, Turing machines, circuits and logic, the internet, complexity, cryptography , algorithmic game theory, and mechanism design. Both came to Cornell from Vrije Universiteit, Amersterdam. Together they published a paper, Rank Aggregation: Together We Are Strong. Prior to coming to Cornell, Van Zuylen worked as a management consultant in The Hague. In Ithaca she volunteered at a center where she taught basic math and computer skills and worked with immigrants to improve English language skills.