Jochen Koenemann

About

Jochen Koenemann is Dean of the Faculty of Mathematics at the University of Waterloo (since July 2025) and a Professor in the Department of Combinatorics and Optimization. His research is in approximation algorithms, combinatorial optimization, and game theory, bridging theoretical computer science and operations research. He previously served as Chair of Combinatorics and Optimization for six years.

Research interests

• Approximation algorithms
• Combinatorial optimization
• Game theory / algorithmic game theory

Selected publications

Journal and conference papers from 2015 onward. The full list, including earlier work, is on DBLP.

2024

1. Journal Madison Van Dyk, Jochen Koenemann. Sparse dynamic discretization discovery via arc-dependent time discretizations. Computers & Operations Research 169, 106715. doi
2. Journal Jochen Koenemann, Justin Toth, Felix Zhou. On the complexity of nucleolus computation for bipartite b-matching games. Theoretical Computer Science 998, 114476. doi
3. Conference Madison Van Dyk, Kim Klause, Jochen Koenemann, Nicole Megow. Fast Combinatorial Algorithms for Efficient Sortation. IPCO 2024, 418–432. doi

2023

1. Journal Cristiana L. Lara, Jochen Koenemann, Yisu Nie, Cid C. de Souza. Scalable timing-aware network design via Lagrangian decomposition. European Journal of Operational Research 309(1), 152–169. doi
2. Journal Jochen Koenemann, Justin Toth. A Framework for Computing the Nucleolus via Dynamic Programming. ACM Transactions on Economics and Computation 11, 3:1–3:21. doi

2022

1. Journal Alexander Göke, Jochen Koenemann, Matthias Mnich, Hao Sun. Hitting Weighted Even Cycles in Planar Graphs. SIAM Journal on Discrete Mathematics 36(4), 2830–2862. doi

2021

1. Journal Yann Disser, Andreas Emil Feldmann, Max Klimm, Jochen Koenemann. Travelling on Graphs with Small Highway Dimension. Algorithmica 83(5), 1352–1370. doi
2. Conference Alexander Göke, Jochen Koenemann, Matthias Mnich, Hao Sun. Hitting Weighted Even Cycles in Planar Graphs. APPROX/RANDOM 2021, 25:1–25:23. doi
3. Conference Jochen Koenemann, Justin Toth, Felix Zhou. On the Complexity of Nucleolus Computation for Bipartite b-Matching Games. SAGT 2021, 171–185. doi

2020

1. Journal Jochen Koenemann, Kanstantsin Pashkovich, Justin Toth. Computing the nucleolus of weighted cooperative matching games in polynomial time. Mathematical Programming 183, 555–581. doi
2. Conference Jochen Koenemann, Kanstantsin Pashkovich, Natig Tofigzade. Approximating Stable Matchings with Ties of Bounded Size. SAGT 2020, 178–192. doi

2019

1. Journal Karthekeyan Chandrasekaran, Corinna Gottschalk, Jochen Koenemann, Britta Peis, Daniel Schmand, Andreas Wierz. Additive stabilizers for unstable graphs. Discrete Optimization 31, 56–78. doi
2. Journal Stephan Held, Jochen Koenemann, Jens Vygen. Vehicle routing with subtours. Discrete Optimization 33, 87–100. doi

2018

1. Journal Andreas Emil Feldmann, Wai Shing Fung, Jochen Koenemann, Ian Post. A (1+ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs. SIAM Journal on Computing 47(4), 1667–1704. doi
2. Conference Samuel Fiorini, Martin Groß, Jochen Koenemann, Laura Sanità. Approximating Weighted Tree Augmentation via Chvátal–Gomory Cuts. SODA 2018, 817–831. doi

2017

1. Conference Jochen Koenemann, Neil Olver, Kanstantsin Pashkovich, R. Ravi, Chaitanya Swamy, Jens Vygen. On the Integrality Gap of the Prize-Collecting Steiner Forest LP. APPROX/RANDOM 2017, 17:1–17:13. doi

2016

1. Journal Andreas Emil Feldmann, Jochen Koenemann, Neil Olver, Laura Sanità. On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree. Mathematical Programming 160, 379–406. doi
2. Journal Linda Farczadi, Konstantinos Georgiou, Jochen Koenemann. Stable Marriage with General Preferences. Theory of Computing Systems 59, 683–699. doi
3. Journal Jochen Koenemann, Kanstantsin Pashkovich, Justin Toth. An elementary integrality proof of Rothblum's stable matching formulation. Operations Research Letters 44, 754–756. doi
4. Journal Ahmad Abdi, Andreas Emil Feldmann, Bertrand Guenin, Jochen Koenemann, Laura Sanità. Lehman's Theorem and the Directed Steiner Tree Problem. SIAM Journal on Discrete Mathematics 30, 141–153. doi
5. Conference Zachary Friggstad, Jochen Koenemann, Mohammad Shadravan. A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs. SWAT 2016, 3:1–3:11. doi

2015

1. Journal Anupam Gupta, Jochen Koenemann, Stefano Leonardi, R. Ravi, Guido Schäfer. Efficient cost-sharing mechanisms for prize-collecting problems. Mathematical Programming 152, 147–188. doi
2. Journal Adrian Bock, Karthekeyan Chandrasekaran, Jochen Koenemann, Britta Peis, Laura Sanità. Finding small stabilizers for unstable graphs. Mathematical Programming 154, 173–196. doi
3. Journal Jochen Koenemann, Kate Larson, David Steiner. Network Bargaining: Using Approximate Blocking Sets to Stabilize Unstable Instances. Theory of Computing Systems 57, 655–672. doi

Latest updates

For recent updates, follow Jochen on LinkedIn.

Students & advising

Ph.D. students

• Madison Van Dyk (2020–2024) — Routing, Scheduling, and Sorting in Consolidated Networks
  Now: Research Scientist, Amazon.
• Hao Sun (2016–2022) — Hitting Weighted Even Cycles in Planar Graphs
  Now: Visiting Postdoctoral Fellow, Simons Institute, UC Berkeley.
• Linda Farczadi (2012–2015) — Matchings and Games on Networks
  Now: Data Scientist, Nestlé (Switzerland).
• Isaac Fung (2011–2015)
• David Pritchard (2006–2009) — Linear Programming Tools and Approximation Algorithms for Combinatorial Optimization joint with L. Tunçel
  Now: Software Engineer, Google.

Master's students

• Mathieu Rundstrom (2020–2024) — Two combinatorial problems from craniosynostosis
  Now: PhD student in C&O, University of Waterloo.
• Justin Toth (2015–2021) — Computing the Nucleolus of Matching and b-Matching Games
  Now: Senior/Staff Software Engineer, Verily.
• Ishan Bansal (2019–2020) — The Merge Algorithm for Capacitated Network Design
  Now: Research Scientist, Amazon.
• Marina Drygala (2019–2020) — Craniosynostosis Surgery: A Study of Rearrangement
  Now: PhD candidate, Computer Science, EPFL.
• Natig Tofigzadeh (2018–2020) — An Algorithm for Stable Matching with Approximation up to the Integrality Gap
  Now: Software Engineer, Clari.
• Mohammad Shadravan (2012–2014) — On the Integrality Gap of Directed Steiner Tree Problem
  Now: Postdoctoral Researcher, IEOR, Columbia University.
• Sina Sadeghian (2012–2013) — Node-Weighted Prize Collecting Steiner Tree and Applications joint with L. Sanità
  Now: Founding Partner & CEO, NuBinary (Toronto).
• Devanshu Pandey (2011–2013) — Vehicle Routing: A Survey of Approximation Algorithm Techniques
  Now: Solutions Architect, Databricks (Toronto).
• David Steiner (2009–2012) — Network Bargaining: Creating Stability using Blocking Sets M.Math (CS), joint with K. Larson
  Now: Senior Engineering Manager, Google.
• Malcolm Sharpe (2011–2012)
• Elyot Grant (2010–2011) — Covering Problems via Structural Approaches joint with T. Chan
  Now: CEO and Game Director, Lunarch Studios.
• Marcus Shea (2008–2010) — Iterative Rounding Approximation Algorithms in Network Design
  Now: Founder, 64 Market Making.
• James Pearson (2008–2009) — Exact, Approximate, and Online Algorithms for Optimization Problems Arising in DVD Assignment
• David Wheatley (2006–2007) — Crossmonotonic Cost-Sharing Methods for Network Design Games
  Now: Assistant Professor, Operations and Decision Sciences, Wilfrid Laurier University.
• Patrick Roh (2005–2006) — Minimum Crossing Problems on Graphs
  Now: Lecturer, Mathematics / C&O, University of Waterloo.
• Kunlun Tan (2004–2006) — On the Role of Partition Inequalities in Classical Algorithms for Steiner Problems in Graphs
  Now: Software Development Manager, Agilent Technologies.

Postdoctoral fellows

• Martin Groß (2016–2018) joint with L. Sanità & C. Swamy
  Now: Head of Forecasting & Optimization Science (EU Supply Chain), Amazon.
• Kanstantsin Pashkovich (2014–2016) joint with L. Sanità
  Now: Assistant Professor, C&O, University of Waterloo.
• Umang Bhaskar (2014–2015) joint with C. Swamy
  Now: Reader, School of Technology and Computer Science, TIFR Mumbai.
• Andreas Emil Feldmann (2012–2015) joint with C. Swamy & L. Sanità
  Now: Senior Lecturer, Computer Science, University of Sheffield.
• Ian Post (2012–2015) joint with C. Swamy
  Now: Software Engineer, Google.
• Zachary Friggstad (2011–2014) joint with C. Swamy
  Now: Associate Professor and Canada Research Chair in Combinatorial Optimization, University of Alberta.
• Konstantinos Georgiou (2010–2012) joint with B. Guenin and C. Swamy
  Now: Associate Professor, Mathematics, Toronto Metropolitan University.
• Yogeshwer Sharma (2010–2011) joint with C. Swamy
• Deeparnab Chakrabarty (2008–2010)
  Now: Associate Professor, Computer Science, Dartmouth College.
• Rohit Khandekar (2005–2006) joint with J. Cheriyan and J. Geelen

Service & editorial

Editorial

• Co-Editor, Mathematical Programming, Series A (2018–2020)
• Associate Editor, Journal of Computer and System Sciences (2015–2018)
• Associate Editor, Surveys in Operations Research (2014–2015)
• Guest Editor, SIAM Journal on Computing — Best Papers of STOC 2014

Steering & advisory

• IPCO Steering Committee (2018–2024)

Conference & workshop organization

• Co-organizer, BIRS workshop on Approximation Algorithms and the Hardness of Approximation — 2017, 2023, 2026
• Co-organizer, Hausdorff Trimester Program on Combinatorial Optimization (2015); Hausdorff Workshop and Summer School on Combinatorial Optimization (2018)
• Co-organizer, Workshop on Flexible Network Design (2013)
• Program Committee Chair, Workshop on Approximation and Online Algorithms (WAOA) — 2021 (with Britta Peis)
• Local Arrangements Chair, IPCO 2017
• Cluster Chair (Combinatorial Optimization), International Symposium on Mathematical Programming (ISMP) — 2012; Session Organizer, ISMP 2015

Program committees

• Integer Programming and Combinatorial Optimization (IPCO) — 2016, 2022
• ACM Symposium on Theory of Computing (STOC) — 2014
• ACM-SIAM Symposium on Discrete Algorithms (SODA) — 2014, 2017
• European Symposium on Algorithms (ESA) — 2005, 2012, 2017
• International Workshop on Approximation Algorithms (APPROX) — 2012, 2014, 2017
• International Symposium on Algorithmic Game Theory (SAGT) — 2013, 2015
• Workshop on Approximation and Online Algorithms (WAOA) — 2006, 2010, 2011, 2016
• ACM Conference on Economics and Computation (EC) — 2014
• Conference on Web and Internet Economics (WINE) — 2013
• International Symposium on Combinatorial Optimization (ISCO) — 2012
• Workshop on Combinatorial & Algorithmic Aspects of Networking (CAAN) — 2005

Refereeing

Regular reviewer for journals including Journal of the ACM, SIAM Journal on Computing, Mathematical Programming, Algorithmica, ACM Transactions on Algorithms, Operations Research, and Theoretical Computer Science; and for conferences including STOC, FOCS, SODA, ICALP, IPCO, ESA, APPROX, and FSTTCS.

Industry & collaborations

• Amazon Scholar (2019–2025) — global transportation optimization
• SickKids Hospital (2019) — craniosynostosis surgery planning collaboration

Awards

• Best Paper Award (Runner-Up), FICO Xpress — 2024
• Best Paper Award, Symposium on Algorithmic Game Theory — 2020
• NSERC Discovery Accelerator Supplement — 2012
• Ontario Early Researcher Award — 2007–2012
• IBM Corporation Faculty Award — 2005

Education

• PhD, Algorithms, Combinatorics, and Optimization — Carnegie Mellon University, 2003 (Advisor: R. Ravi)
• Diplom, Computer Science — Universität des Saarlandes, 1998 (Advisor: Naveen Garg)