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 5042
Phone: +1-519-888-4567 x32144
Research Interests: Approximation Algorithms, Algorithmic Game Theory, Combinatorial Optimization
- We will be organizing a Hausdorff Trimester on Combinatorial Optimization in the Fall of 2015. Check out the Summer School event as well, and consider applying!
- I am organizing a session of ISMP'15 in Pittsburgh.
- 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: SAGT'15, APPROX'14, EC'14, STOC'14, SODA'14, WINE'13, SAGT'13
- Fields workshop on "Flexible Network Design" in Toronto, Jul 29-Aug 2, 2013.
Winter'15: Introduction to Optimization - CO 250
- Introduction to Combinatorics - Math 239 (S'12)
- Introduction to Optimization - CO 250 (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)
- Game Theory - CO 456 (F'09)
- Combinatorial Optimization - CO 450/650 (F08,F09,F10)
- Introduction to Game Theory - CO456 (F'09,F'14)
- Algorithmic Game Theory - CO 759 (F'12)
Publications (reverse chronologically)
On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree
Linear Programming Hierarchies Suffice for Directed Steiner Tree
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]
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: [arXiv:1207.6683]
Approximation algorithms for network design: A survey
A. Gupta, J.K.[doi:10.1016/j.sorms.2010.06.001]
Integrality Gap of the Hypergraphic Relaxation of Steiner Trees
Operations Research Letters[doi:10.1016/j.orl.2010.09.004]
On Generalizations of Network Design Problems with Degree Bounds
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]
Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
Workshop on Approximation and Online Algorithms, 2008.conference version: [pdf], journal version: [pdf]
J.K., D. Pritchard.
Technical report #CORR 2007-11, University of Waterloo.[pdf]
A Unified Approach to Approximating Partial Covering Problems
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
Symposium on Theory of Computing, 2006.[pdf], full version appears in SIAM Journal on Computing, 39(8): [10.1137/090767108]
Primal-Dual Based Distributed Algorithms for Vertex Cover with Semi-Hard Capacities
Symposium on Principles of Distributed Computing (PODC), 2005.[pdf]
Distributed Weighted Vertex Cover via Maximal Matchings
Computing and Combinatorics Conference (COCOON), 2005.[pdf]
From Primal-Dual to Cost Shares and Back: A Stronger LP Relaxation for the Steiner Forest Problem
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
Symposium on Discrete Algorithms, 2005.[pdf], Full version of the paper appeared in ACM Trans. on Algorithms 3(2): [pdf]
Quasi-Polynomial Time Approximation Algorithm for Low-Degree Minimum-Cost Steiner Trees
Foundations of Software Technology and Theoretical CompSci, 2003.[ps]
Approximating the Degree-bounded Minimum-Diameter Spanning Tree Problem
Workshop on Approximation Algorithms for CombOpt Problems, 2003.[ps]
Covering Graphs using Trees and Stars
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
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
Symposium on Theoretical Aspects of Computer Science (STACS), 2003.[ps]
Approximation algorithms for edge-dilation k-center problems
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
Workshop on Approximation Algorithms for CombOpt Problems, 2000.[ps].
A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Divning Trees
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
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.
- 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]