Homepage

Anke van Zuylen

Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Campus E1 4, Room 311c
66123 Saarbrücken
Germany

Email: Get my email address via email
Phone: +49 681 9325 135
Fax: +49 681 9325 199

Research Interests

My research interests are in combinatorial optimization problems arising in information science, network design and mechanism design. In particular, I am interested in developing algorithms that have good theoretical properties, using techniques from mathematical programming such as linear programming and the primal-dual method. Besides developing algorithms with theoretical guarantees, I am interested in studying what these guarantees mean in practice, and comparing these algorithms to approaches which may not necessarily have theoretical guarantees.
You can listen to a short podcast about one of my recent papers here.

Publications

A Proof of the Boyd-Carr Conjecture with Frans Schalekamp and David P. Williamson. To appear in SODA 2012.
Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem with Katarzyna Paluch and Khaled Elbassioni. To appear in STACS 2012.
On the Integrality Gap of the Subtour LP for the 1,2-TSP with Jiawei Qian, Frans Schalekamp and David P. Williamson. To appear in LATIN 2012.
An improved monotone algorithm for scheduling related machines with precedence constraints. To appear in Operations Research Letters.
Simpler 3/4-approximation algorithms for MAX SAT. WAOA 2011.
Improved Approximation Algorithms for Bipartite Correlation Clustering with Nir Ailon, Noa Avigdor-Elgrabli and Edo Liberty. ESA 2011.
Popular ranking with Frans Schalekamp and David P. Williamson. CTW 2011.
Clustering with or without the approximation with Frans Schalekamp and Michael Yu. Full version to appear in Journal of Combinatorial Optimization. Preliminary version appeared in COCOON 2010.
Multiplying Pessimistic Estimators: Deterministic Approximation of Max TSP and Maximum Triangle Packing. COCOON 2010.
Deterministic pivoting algorithms for constrained ranking and clustering problems with David P. Williamson. Mathematics of Operations Research, Vol. 34, No. 3, August 2009, pp. 594-620. Journal version combining
- part of the results in Deterministic pivoting algorithms for constrained ranking and clustering problems with Rajneesh Hegde, Kamal Jain and David P. Williamson. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007,
- and the results in Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems with David P. Williamson. 5th Workshop on Approximation and Online Algorithms (WAOA), 2007.
Deterministic Sampling Algorithms for Network Design. Algorithmica 60(1): 110-151 (2011), Special Issue on European Symposium on Algorithms.
- Journal version of Deterministic Sampling Algorithms for Network Design. European Symposium on Algorithms (ESA), 2008. Winner of Best Student Paper Award (Track A).
- Generalizes and extends A simpler and better derandomization of an approximation algorithm for Single Source Rent-or-Buy with David P. Williamson. Operations Research Letters, Volume 35, Issue 6, Pages 707-712.
Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments. Journal version, Theoretical Computer Science, Volume 412, Issue 23, 20 May 2011, Pages 2556-2561. Preliminary version appeared in Conference on Theory and Applications of Models of Computation (TAMC), 2009.
Rank Aggregation: Together We Are Strong with Frans Schalekamp. Workshop on Algorithm Engineering and Experiments (ALENEX), 2009.
Maximizing influence in a competitive social network: a follower's perspective
Tim Carnes, Chandrashekhar Nagarajan, Stefan M. Wild, Anke van Zuylen
ICEC '07 Proceedings of the ninth international conference on Electronic commerce, 2007

frames are not supported
The Achilles' Heel of the GSR Shuffle: A Note On New Age Solitaire with Frans Schalekamp. Probability in the Engineering and Informational Sciences, Volume 18 , Issue 3 (July 2004)
Partitio et Emergo: A Note on Computation of Eigenvalues of a Shuffle Matrix with Frans Schalekamp. unpublished manuscript.
Master's thesis: Over het schudden van kaarten (In Dutch) with Frans Schalekamp. August 2000 - winner of VVS+OR-Thesis Award 2001 for best Dutch Master's thesis in Operations Research.

Teaching & Advising

Open Topics for Student Theses

Implementation: Experimental comparison of two approximation algorithms for the maximum asymmetric traveling salesman problem. (Master/strong Bachelor)
Theory: Improving our understanding of the subtour LP relaxation for the traveling salesman problem. Can we extend the results in this paper to triangle free 2-matchings? Can we project the polyhedron for graphical 2-matchings to variables defined on the original graph? (Master/Ph.D.)

Past Courses

Saarland University
- Summer 2011: Optimization I
  - Core course in Master Program Computer Science, taught together with Khaled Elbassioni.
  - Teaching evaluations.
- Summer 2011: Together with Christine Rizkallah, I organized the ADFOCS summer school.
Tsinghua University
- Fall 2008 and 2009: Introduction to Computer Science.
  - New course for elite group of freshmen, developed and taught together with Frans Schalekamp.
  - Summary of the course (from Fall 2008).
  - Teaching evaluations 2008, and 2009.
- Spring 2010: Advanced Algorithms.
  - Course roughly based on Michel Goemans's course, taught together with Frans Schalekamp.
  - A quarter of the course time was devoted to student presentations, using ideas from a paper by Havill and Ludwig and materials available at the Technically Speaking website of Denison University .
  - Teaching evaluations 2010.
Cornell University
- Optimization I,
- Optimization II, teaching evaluations: Optimization II Spring 2006, Optimization II Spring 2007 and Optimization II Spring 2008. Undergraduate Outstanding Teaching Assistant Award in 2008.
- Engineering Probability and Statistics II,
- Introductory Engineering Stochastic Processes I,
- Basic Engineering Probability and Statistics, and
- Engineering Applications of Operations Research.

Education and Recent Positions

September 2010 - present:
Postdoctoral researcher, Algorithms and Complexity at the Max-Planck-Institut für Informatik
August 2008-2010:
Postdoctoral researcher, Institute for Theoretical Computer Science, Tsinghua University, Beijing, China.
January 2004 - May 2008:
Ph.D. in Operations Research. Cornell University, Ithaca, NY
Thesis: God Does Not Play Dice... And Neither Should Approximation Algorithms (supervisor: Prof. Dr. David P. Williamson)
September 1994 - August 2001:
Master's in Operations Research and Econometrics. Vrije Universiteit, Amsterdam, Netherlands
Thesis: Over het schudden van kaarten (supervisor: Prof Dr. Henk C. Tijms)

On Spelling and Alphabetizing My Name

My last name is "van Zuylen". "Van" means "of, coming from" and is a very common prefix in Dutch last names. It is ignored when alphabetizing, so my name should be alphabetized under "Z", not under "v".