Frans Schalekamp

Short Biography

I received my PhD in Operations Research from Cornell University in 2007, and have worked both in academia and industry, on three continents. I worked on areas ranging from plant breeding and genetics, to logistics, but my passion is in teaching. My current position is Teaching Professor in the School of Operations Research at Cornell University, where I have taught a wide range of courses. To name a few of my favorites: ENGRI 11101 Intro to OR, MATH 2940 Linear Algebra, ORIE 3310 Optimization II, ORIE 4350 Game Theory and ORIE 4390 Optimization Modelling.

I am originally from the Netherlands, and got my undergraduate degree from the Vrije University in Amsterdam. My former academic positions were at the Institute for Theoretical Computer Science at Tsinghua University in Beijing, China, the Department of Mathematics at the College of William & Mary in Williamsburg VA and the Computer Science Department at Cornell University in Ithaca NY. In industry, I worked as a C++ developer for ORTEC Systems in Gouda, Netherlands, as a Research Scientist at NatureSourceGenetics in Ithaca NY, and a Senior Analyst at CarMax in Richmond VA.

My curriculum vitae is available here (pdf).

Research Interests

My research interests lie in optimization, both in practice and theory. I have worked on problems in bioinformatics, sensor networks and information science. My interest in theoretical aspects of optimization is focused in particular on designing approximation algorithms for NP-hard problems, and understanding limitations on finding good solutions to problems. Practical implementations and seeing how well methods do in practice is a further interest. I worked for nearly two years at a startup company in bioinformatics, NatureSourceGenetics, designing practical algorithms for finding good plant breeding strategies.

My publications are listed below.

Teaching

I am teaching ENGRI 1101 in fall 2026, and ORIE 3310 in spring 2027.

Teaching Evaluations

The following is a list of the courses I taught, ordered by semester and with links to teaching evaluations:

Awards

• ORIE Teaching Award, 2021, 2022, 2025
• Ralph S. Watts '72 Excellence in Teaching Award (College of Engineering Cornell), 2025
• Department of Mathematics Senior Faculty Award for excellent teaching, 2024
• Sonny Yau '72 Excellence in Teaching Award (College of Engineering Cornell), 2021
• Simon Prize for Excellence in the Teaching of Mathematics, 2014
• Cornell Graduate Fellowship, 2002
• MacMullen Operations Research Fellowship, 2001
• 1/2 MIT Presidential Fellowship, 2001 (declined)
• VVS Scriptieprijs 2001 (Award for best Master's thesis by Dutch Society for Operations Research and Statistics 2001) for thesis On Shuffling Cards (together with Anke van Zuylen)

Publications

Journal Articles

• Neil Olver, Frans Schalekamp, Suzanne van der Ster, Leen Stougie, Anke van Zuylen
  A duality based 2-approximation algorithm for maximum agreement forest
  Mathematical Programming (2022)
  online first, open access
  Springer
• Frans Schalekamp, András Sebő, Vera Traub and Anke van Zuylen
  Layers and Matroids for the Traveling Salesman's Paths
  Operations Research Letters 46(1) (2018)
  pp. 60-63
  Elsevier, pdf (old version on arxiv)
• Esteban Feuerstein, Alberto Marchetti-Spaccamela, Frans Schalekamp, Rene Sitters, Suzanne van der Ster, Leen Stougie, Anke van Zuylen
  Scheduling over Scenarios on Two Machines
  Journal of Scheduling 20(6) (2017)
  pp. 545-555
  Springer, pdf (old version on arxiv)
• Anke van Zuylen, James Bieron, Frans Schalekamp, Gexin Yu
  An Upper Bound on the Number of Circular Transpositions to Sort a Permutation
  Information Processing Letters 116(11) (2016)
  pp. 718-722
  Elsevier, pdf (old version on arxiv)
  PDF
• Khaled Almi'ani, Anastasios Viglas, Frans Schalekamp, Reza Abrishambaf
  Flow-Based Scheme for Time-Constrained Data Gathering in Wireless Sensor Networks
  International Journal of Wireless and Mobile Computing 10(1) (2016)
  pp. 1-12
  InderScience
• Jiawei Qian, Frans Schalekamp, David P. Williamson, Anke van Zuylen
  On the Integrality Gap of the Subtour LP for the 1,2-TSP
  Mathematical Programming Series B 150(1) (2015)
  pp. 131-151
  Springer, pdf (old version on arxiv)
  PDF
• Frans Schalekamp, Rene Sitters, Suzanne van der Ster, Leen Stougie, Victor Verdugo, Anke van Zuylen
  Split Scheduling with Uniform Setup Times
  Journal of Scheduling 18(2) (2015)
  pp. 119-129
  Springer, pdf (old version on arxiv)
  PDF
• Frans Schalekamp, David P. Williamson, Anke van Zuylen
  2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture
  Mathematics of Operations Research, 39(2) (2014)
  pp. 403-417
  INFORMS
• Anke van Zuylen, Frans Schalekamp, David P. Williamson
  Popular Ranking
  Discrete Applied Mathematics 165 (2014)
  pp. 312-316
  Elsevier
• Frans Schalekamp, Michael Yu, Anke van Zuylen
  Clustering with or without the Approximation
  Journal of Combinatorial Optimization, 25(3) (2013)
  pp. 393-429
  Springer, pdf (old version)
  PDF
• Frans Schalekamp, David B. Shmoys
  Algorithms for the universal and a priori TSP
  Operations Research Letters, 36(1) (2008)
  pp. 1-3
  Elsevier
• Anke van Zuylen, Frans Schalekamp
  The Achilles heel of the GSR-shuffle --- A note on New Age Solitaire
  Probability in the Engineering and Informational Sciences, 18(3) (2004)
  pp. 315-328
  Cambridge, pdf
  PDF
• Frans Schalekamp
  Simulation of the Matching Problem of Montmort
  Probability in the Engineering and Informational Sciences, 12(3) (1998)
  pp. 325-328
  Cambridge

Refereed Proceedings

• Igor Labutov, Frans Schalekamp, Kelvin Luu, Hod Lipson, Christoph Studer
  Optimally Discriminative Choice Sets in Discrete Choice Models: Application to Data-Driven Test Design
  KDD 2016
  ACM, kdd.org
• Frans Schalekamp, Anke van Zuylen, Suzanne van der Ster
  A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest
  ICALP 2016
  DROPS, arxiv (full version), java implementation of 2-approximation algorithm, and sample run of 2-approximation algorithm
• Esteban Feuerstein, Alberto Marchetti-Spaccamela, Frans Schalekamp, Rene Sitters, Suzanne van der Ster, Leen Stougie, Anke van Zuylen
  Scheduling over Scenarios on Two Machines
  COCOON 2014
  pp. 559-571
  Springer, pdf (full version on arxiv)
• Henry Lin, Frans Schalekamp
  Brief Announcement: On the Complexity of the Minimum Latency Scheduling Problem on the Euclidean Plane
  SPAA 2012
  pp. 80-81
  ACM
• Jiawei Qian, Frans Schalekamp, David P. Williamson, Anke van Zuylen
  On the Integrality Gap of the Subtour LP for the 1,2-TSP
  LATIN 2012
  pp. 606-617
  LNCS, pdf
  PDF
• Frans Schalekamp, David P. Williamson, Anke van Zuylen
  A proof of the Boyd-Carr conjecture
  SODA 2012
  pp. 1477-1486
  pdf, pdf
  PDF
• Anke van Zuylen, Frans Schalekamp, David P. Williamson
  Popular Ranking
  CTW 2011
  pp. 267-270
  pdf, pdf
  PDF
• Frans Schalekamp, Michael Yu, Anke van Zuylen
  Clustering with or without the Approximation
  COCOON 2010
  pp. 70-79
  LNCS, pdf
  PDF
• Frans Schalekamp, Anke van Zuylen
  Rank Aggregation: Together We're Strong
  ALENEX 2009
  pp. 38-51
  SIAM, SIAM pdf
  PDF

Manuscripts

• Henry Lin, Frans Schalekamp
  On the Complexity of the Minimum Latency Scheduling Problem on the Euclidean Plane
  arxiv
  pdf, arxiv
  PDF
• Frans Schalekamp
  Mapping from a Random Walk Perspective with Two Applications
  unpublished manuscript
• Frans Schalekamp, Anke van Zuylen
  Partitio et Emergo --- On computing eigenvalues of shuffle matrices
  unpublished manuscript
  pdf
  PDF

Theses

• Frans Schalekamp
  Some Results in Universal and A Priori Optimization (PhD Thesis)
  2007
  Advisor: David B. Shmoys
  Cornell
• Frans Schalekamp, Anke van Zuylen
  Over het schudden van kaarten (Master's Thesis, in Dutch)
  2000
  Advisor: Henk C. Tijms
  ps, large pdf

Web Presence

Reading and Teaching Notes

Here are some reading and teaching notes:

• lecture notes on the L-shaped Method
• reading notes for the new graph-TSP approximation algorithm by Sebő and Vygen, from their paper Shorter Tours by Nicer Ears
• lecture notes on the Probabilistic Tree Embedding (Fakcharoenphol, Rao, Talwar, 2003) (see also below)
• lecture notes on the Paging problem (Fiat, Karp, Luby, McGeoch, Sleator and Young, 1991).

Contact

fms9 (at) cornell . edu

Wiki

Anke and I started a wiki when we worked at Tsinghua University, because getting settled in Beijing turned out not to be a trivial task if you're not Chinese (and perhaps also if you are!) It was a work in progress, and parts of it will be outdated already, but it may still be useful, also for visitors of Tsinghua University. The original wiki is no longer accessible, but they are archived on archive.org: Information for Visitors, Working at iTcs and Living in Beijing.

FRT Tree Embedding

The following is a run of the tree embedding algorithm due to Fakcharoenphol, Rao, Talwar (2003). Select any individual picture to toggle a larger version.

(order of nodes = 3 2 13 11 15 8 14 4 5 6 12 7 10 9 1 0)

One of these pictures was used on the cover of the book The Design of Approximation Algorithms by David Williamson and David Shmoys:

This is the (not very clean) implementation I made some years ago in java. The implementation of the FRT algorithm is in Metric.java; FRTtreeTest.java hopefully gives an idea how to use it. The output is encapsulated postscript, with some information about the tree in LaTeX format below it. If you save the output to a file, you can get different levels by changing the number (1) on line 11 (if I remember correctly it is supposed a power of 2).