# 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. I am currently a Visiting Assistant Professor 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 will be teaching ORIE 3310/5310/5311 in Spring 2018.

A summary of the courses I have taught previously is available here (pdf). Full teaching evaluations for the courses I taught can be found below.

#### Teaching Evaluations

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

##### Cornell University

- Fall 2017
- Spring 2017
- Introduction to Analysis of Algorithms (CS 4820) (pdf) (co-taught with Bobby Kleinberg)

- Spring 2016
- Fall 2015

##### 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

- 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

##### Work in Progress

- Neil Olver, Frans Schalekamp, Suzanne van der Ster, Leen Stougie and Anke van Zuylen

A 2-Approximation Algorithm for Maximum Agreement Forest

##### 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

- 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).