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. 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, the School of Operations Research & Information Engineering and the Computer Science Department at Cornell University in Ithaca NY. I was a Research Scientist at NatureSourceGenetics in Ithaca NY, and a Senior Analyst at CarMax in Richmond VA. Currently I am a Senior Lecturer in the School of Operations Research at Cornell University.
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 2024.
Teaching Evaluations
The following is a list of the courses I taught, ordered by semester and with links to teaching evaluations:
Cornell University
- Spring 2024
- Fall 2023
- Spring 2023
- Fall 2022
- Spring 2022
- Fall 2021
- Discrete Structures (CS 2800) (pdf) (co-taught with Alexandra Silva)
- Spring 2021
- Fall 2020
- Introduction to Game Theory (ORIE 4350) (pdf)
- Also: some poems about game theory from the final exam (pdf)
- Spring 2020
- Optimization II (ORIE 3310) (pdf), Optimization II (ORIE 5310) (pdf)
- Fall 2019
- Spring 2018
- Optimization II (ORIE 3310) (pdf), Optimization II (ORIE 5310) (pdf)
- Fall 2017
- Spring 2017
- Introduction to Analysis of Algorithms (CS 4820) (pdf) (co-taught with Bobby Kleinberg)
- Spring 2016
- Fall 2015
In 2021 I received both the ORIE Teaching Award (awarded by the students of ORIE) and the Sonny Yau '72 Excellence in Teaching Award (awarded by the College of Engineering).
In 2022 I again received the ORIE Teaching Award (awarded by the students of ORIE).
CUHK(SZ)
- Fall 2018
College of William and Mary
- Spring 2015
- Fall 2014
- Spring 2014
- Fall 2013
- Spring 2013
- Fall 2012
In 2014 I received the Simon Prize for Excellence in the Teaching of Mathematics.
Tsinghua University
At Tsinghua I taught Introduction to Computer Science (freshman, Fall 2008 and Fall 2009 and Advanced Algorithms (junior, Spring 2010) (both of these were joint efforts with Anke van Zuylen).
Teaching Evaluations:
- Spring 2010
- Advanced Algorithms (pdf; Chinese with rough English translations) or Advanced Algorithms (pdf; Chinese)
- Fall 2009
- Introduction to Computer Science (pdf; Chinese)
- Fall 2008
- Introduction to Computer Science (pdf; Chinese)
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) - 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) - 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) - 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) - 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 - 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 - Frans Schalekamp, David P. Williamson, Anke van Zuylen
A proof of the Boyd-Carr conjecture
SODA 2012
pp. 1477-1486
pdf, pdf - Anke van Zuylen, Frans Schalekamp, David P. Williamson
Popular Ranking
CTW 2011
pp. 267-270
pdf, pdf - Frans Schalekamp, Michael Yu, Anke van Zuylen
Clustering with or without the Approximation
COCOON 2010
pp. 70-79
LNCS, pdf - Frans Schalekamp, Anke van Zuylen
Rank Aggregation: Together We're Strong
ALENEX 2009
pp. 38-51
SIAM, SIAM pdf
Manuscripts
- Henry Lin, Frans Schalekamp
On the Complexity of the Minimum Latency Scheduling Problem on the Euclidean Plane
arxiv
pdf, arxiv - 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
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
Awards
- ORIE Teaching Award, 2022, 2021
- 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)
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 Probabilisitic 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) (click each individual picture for 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).
Photo Credits
I thank Anke van Zuylen, Ann Williamson, Nanxi Li, Yuhua Li, Soumyadip Ghosh, Kenneth Trinh, Cynthia Shao and Dall-e 2 for their photos and creations.