Jochen Koenemann

Professor & Chair
Department of Combinatorics & Optimization
University of Waterloo

Ph.D. Algorithms, Combinatorics & Optimization, Carnegie Mellon, 2003
Postdoc, La Sapienza University of Rome, 2003-2004

Email: jochen [at] uwaterloo.ca
Office: MC 5106
Phone: +1-519-888-4567 x32144

Research Interests: Approximation Algorithms, Algorithmic Game Theory, Combinatorial Optimization

CV: [pdf]

News

We organized a Hausdorff Summer School and Workshop on Combinatorial Optimization
IPCO'17 was in Waterloo! Have a look here.
We organized a Hausdorff Trimester on Combinatorial Optimization.
With colleagues B. Guenin & L. Tuncel, we recently completed our undergraduate textbook on optimization - check it out here!
Read articles on our collaboration with SickKids Hospital here, and here.
Recent program committees: EC'18, APPROX'17, IPCO'17, ESA'17 , SODA'17, WAOA'16 ,IPCO'16, SAGT'15, APPROX'14, EC'14, STOC'14, SODA'14,

Recent work

Approximating Stable Matchings with Ties of Bounded Size

JK, K. Pashkovich, N. Tofigzadeh

SAGT'20 [pdf]
A General Framework for Computing the Nucleolus via Dynamic Programming

JK, W.J. Toth

SAGT'20 [pdf]
Computing the Nucleolus of Weighted Cooperative Matching Games in Polynomial Time

JK, K. Pashkovich, W.J. Toth

IPCO 2019 [pdf], full version: Math Programming 183
Approximating Weighted Tree Augmentation via Chvátal-Gomory Cuts

S. Fiorini, M. Gross, J.K., L. Sanita

SODA 2018 [pdf]
On the Integrality Gap of the Prize-Collecting Steiner Forest LP

JK, N. Olver, K. Pashkovich, R. Ravi, C. Swamy, J. Vygen

Approx-Random 2017 [pdf]

Teaching

Introduction to Combinatorics - Math 239 (S'12)
Introduction to Optimization - CO 250 (W'15,S'14,F'11,S'12,W'13,S'14)
Network Flows - CO 351 (W'07,S'08)
Deterministic OR Models - CO 370 (W'07,F'12, W'20)
Game Theory - CO 456 (F'09,F'14,F'18)
Combinatorial Optimization - CO 450/650 (F08,F09,F10,F17)
Introduction to Game Theory - CO456 (F'09,F'14)
Approximation Algorithms - CO754 (W'21)
Algorithmic Game Theory - CO 759 (F'12)
Selected Topics in Combinatorial Optimization (@Bonn) (S16)

Schedule

Publications (reverse chronologically)

2020	Approximating Stable Matchings with Ties of Bounded Size JK, K. Pashkovich, N. Tofigzadeh SAGT'20 [pdf] A General Framework for Computing the Nucleolus via Dynamic Programming JK, W.J. Toth SAGT'20 [pdf]
2019	Computing the Nucleolus of Weighted Cooperative Matching Games in Polynomial Time JK, K. Pashkovich, W.J. Toth [pdf]
2018	Approximating Weighted Tree Augmentation via Chvátal-Gomory Cuts S. Fiorini, M. Gross, J.K., L. Sanita SODA 2018 [pdf]
2017	On the Integrality Gap of the Prize-Collecting Steiner Forest LP JK, N. Olver, K. Pashkovich, R. Ravi, C. Swamy, J. Vygen Approx-Random 2017 [pdf]
2016	An Elementary Integrality Proof of Rothblum's Stable Matching Formulation. JK, K. Pashkovich, J. Toth arXiv:1605.04427 [pdf] Fast Approximation Algorithms for the Generalized Survivable Network Design Problem A. E. Feldmann, JK, K. Pashkovich, L. Sanità arXiv:1604.07049 [pdf] A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs. Z. Friggstad, JK, M. Shadravan SWAT 2016 -- [pdf] Lehman's Theorem and the Directed Steiner Tree Problem. A. Abdi, A.E. Feldmann, B. Guenin, JK, L. Sanità SIAM J. Discrete Math. 30(1): 141-153
2015	Approximate Deadline-Scheduling with Precedence Constraints. H. Efsandiari, M. T. Hajiaghayi, JK, H. Mahini, D. L. Malec, L. Sanità ESA 2015 A (1 + ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs A. Feldmann, I. Fung, JK, I. Post ICALP 2015 (CoRR abs/1502.04588)
2014	Stable Marriage with General Preferences L. Farczadi, K. Georgiou SAGT 2014 -- [pdf] On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree A. Feldmann, J.K., N. Olver, L. Sanità APPROX 2014 -- [pdf] Linear Programming Hierarchies Suffice for Directed Steiner Tree Z. Friggstad, Y. K. Ko, J.K., A. Louis, M. Shadrawan and M. Tulsiani IPCO 2014 Conference version: [pdf], full version: [pdf] Finding small stabilizers for unstable graphs A. Bock K. Chandrasekaran, J.K., B. Peis and L. Sanita IPCO 2014 Conference version: [pdf], full version: [pdf]
2013	An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree J.K., S. Sadeghian, L. Sanità Foundations of Computer Science, 2013. Full version: [arXiv:1302.2127] Network bargaining with general capacities L. Farczadi, K. Georgiou, J.K. European Symposium on Algorithms, 2013. Conference version: [pdf], full version: [arXiv:1306.4302] Better Approximation Algorithms for Technology Diffusion J.K., S. Sadeghian, L. Sanità European Symposium on Algorithms, 2013. [pdf] Social Exchange Networks with Distant Bargaining K. Georgiou, G. Karakostas, J.K., Z. Stamirowska International Computing and Combinatorics Conference, 2013. Conference version: [pdf] Journal version: Theoretical CS
2012	Network Bargaining: Using Approximate Blocking Sets to Stabilize Unstable Instances J.K., K. Larson, D. Steiner Symposium on Algorithmic Game Theory, 2012. Conference version: [pdf], full version: TCS 57(3) Weighted Capacitated, Priority, and Geometric Set Cover via Improved Quasi-Uniform Sampling T. Chan, E. Grant, J.K., M. Sharpe Symposium on Discrete Algorithms, 2012. [pdf]
2011	The School Bus Problem on Trees A. Bock, E. Grant, J.K., L. Sanita Symposium on Algorithms and Computation, 2011 Conference version: [pdf], full version: Algorithmica 67(1)
2010	Approximation algorithms for network design: A survey A. Gupta, J.K. Surveys in Operations Research and Management Science, 16(1) [doi:10.1016/j.sorms.2010.06.001] Integrality Gap of the Hypergraphic Relaxation of Steiner Trees D. Chakrabarty, J.K., D. Pritchard Operations Research Letters [doi:10.1016/j.orl.2010.09.004] On Generalizations of Network Design Problems with Degree Bounds N. Bansal, R. Khandekar , J.K., V. Nagarajan , B. Peis Integer Programming and Combinatorial Optimization (IPCO), 2010. conference version: [pdf], full version: Math Programming 141 (1-2) On Column Restricted and Priority Integer Covering Programs D. Chakrabarty, J.K., E. Grant Integer Programming and Combinatorial Optimization (IPCO), 2010. conference version: [pdf], full version: [arXiv:1003.1507] Hypergraphic LP Relaxations for Steiner Trees D. Chakrabarty, J.K., D. Pritchard Integer Programming and Combinatorial Optimization (IPCO), 2010. conference version: [pdf], full version: SIAM J. Discrete Math 27(1)
2009	A Partition-Based Relaxation For Steiner Trees J.K., D. Pritchard, K. Tan Mathematical Programming (A), 127(2), [doi:10.1007/s10107-009-0289-2].
2008	Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees J.K., O. Parekh, D. Pritchard Workshop on Approximation and Online Algorithms, 2008. conference version: [pdf], journal version: [pdf] On the Integrality Ratio for Tree Augmentation J. Cheriyan, J.K., H. Karloff, R. Khandekar [pdf]
2007	Uncrossing Partitions J.K., D. Pritchard. Technical report #CORR 2007-11, University of Waterloo. [pdf] An Efficient Cost-Sharing Mechanism for the Prize-Collecting Steiner Forest Problem A. Gupta, J.K., S. Leonardi, R.Ravi, G. Schäfer. Symposium on Discrete Algorithms, 2007. [pdf]
2006	A Unified Approach to Approximating Partial Covering Problems J.K., O. Parekh, D. Segev, European Symposium on Algorithms, 2006. [pdf], Full version appear in Algoritmica 59(4): [doi:10.1007/s00453-009-9317-0] Simple Cost Sharing Schemes for Multi-Commodity Rent-or-Buy and Stochastic Steiner Tree L. Fleischer, J.K., S. Leonardi, G. Schäfer. Symposium on Theory of Computing, 2006. [pdf], full version appears in SIAM Journal on Computing, 39(8): [10.1137/090767108] Cut Problems with a Budget Constraint R. Engelberg, J.K., S. Leonardi, Joseph Naor. Latin American Theoretical Informatics Symposium (LATIN), 2006. [pdf], full version appeared in Journal of Discrete Algorithms, 5(2): [pdf]
2005	Primal-Dual Based Distributed Algorithms for Vertex Cover with Semi-Hard Capacities F. Grandoni, J.K., A. Panconesi, M. Sozio. Symposium on Principles of Distributed Computing (PODC), 2005. [pdf] Distributed Weighted Vertex Cover via Maximal Matchings F. Grandoni, J.K., A. Panconesi. Computing and Combinatorics Conference (COCOON), 2005. [pdf] From Primal-Dual to Cost Shares and Back: A Stronger LP Relaxation for the Steiner Forest Problem J.K., S. Leonardi, G. Schäfer, S. v. Zwam. Colloquium on Automata, Languages and Programming (ICALP), 2005. [pdf], Journal version appeared SIAM Journal on Computing 37(5), pp. 1319--1341: [pdf] papers). Sharing the cost more efficiently: Improved Approximation for Multicommodity Rent-or-Buy L. Becchetti, J.K., S. Leonardi, M. Pal. Symposium on Discrete Algorithms, 2005. [pdf], Full version of the paper appeared in ACM Trans. on Algorithms 3(2): [pdf] A Group-Strategyproof Mechanism for Steiner Forests J.K., S. Leonardi, G. Schäfer. Symposium on Discrete Algorithms, 2005. [pdf]
2004	Approximating k-Hop Minimum-Divning Trees E. Althaus, S. Funke, S. Har-Peled, J.K., E. A. Ramos, M. Skutella. Operations Research Letters Vol. 33(2), Pages 115-120, 2004. [pdf]
2003	Quasi-Polynomial Time Approximation Algorithm for Low-Degree Minimum-Cost Steiner Trees J.K., R.Ravi. Foundations of Software Technology and Theoretical CompSci, 2003. [ps] Approximating the Degree-bounded Minimum-Diameter Spanning Tree Problem J.K., A. Levin, A. Sinha. Workshop on Approximation Algorithms for CombOpt Problems, 2003. [ps] Covering Graphs using Trees and Stars G. Even, N. Garg, J.K., R.Ravi, A. Sinha. Workshop on Approximation Algorithms for CombOpt Problems, 2003. [ps], Journal version appeared in Operations Research Letters Vol. 32(4), pp. 309-315: [pdf] Primal-dual algorithms come of age: Approximating MST's with nonuniform degree bounds J.K., R.Ravi. ACM Symposium on Theory of Computing, 2003. [ps], [pdf]; Journal version appeared SIAM Journal on Computing 34(3), pp. 763-773: [pdf] Non-Clairvoyant Scheduling for Mean Slowdown N.Bansal, K.Damdhere, J.K., A. Sinha. Symposium on Theoretical Aspects of Computer Science (STACS), 2003. [ps] A Combinatorial Algorithm for Computing a Maximum Independent Set in a t-perfect Graph F. Eisenbrand, S. Funke, N. Garg, J.K. ACM-SIAM Symposium on Discrete Algorithms, 2003. [ps]
pre 2003	Approximation algorithms for edge-dilation k-center problems J.K., Y. Li, A. Sinha, O. Parekh. Scandinavian Workshop on Algorithm Theory, 2002. [ps] Journal version: Operations Research Letters Vol. 32(5), pp. 491-495: [pdf] Improved Approximations for Tour and Tree Covers J.K., G. Konjevod, O. Parekh, A. Sinha. Workshop on Approximation Algorithms for CombOpt Problems, 2000. [ps]. A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Divning Trees J.K., R.Ravi. ACM Symposium on Theory of Computing, 2000. [ps] A journal version of the paper appears in SIAM Journal on Computing Vol. 31(6): [pdf] Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems N.Garg, J.K. IEEE Conference on Foundations of Computer Science, 1998. [ps], a journal version of the paper appears in SIAM Journal on Computing Vol. 37(2): [pdf] Exact Geometric Computation in LEDA C.Burnikel, J.K., K.Mehlhorn, S.Näher, S.Schirra, C.Uhrig. Proc. of the 11th ACM Symp. on Computational Geometry, 1995.

Theses

Approximation Algorithms for Minimum-Cost Low-Degree Subgraphs. PhD Thesis in Algorithms, Combinatorics, and Optimization, Carnegie Mellon University, 2003. [pdf]
Fast Combinatorial Algorithms for Packing and Covering Problems. Master's Thesis in Computer Science, Universität des Saarlandes, 1998. [ps]

Current students