Current students

Postdocs*

(*with C. Swamy)



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

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

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

CV: [pdf]

News

Recent work

Teaching

Spring'14: Introduction to Optimization - CO 250

Schedule

Publications (reverse chronologically)

2014
Linear Programming Hierarchies Suffice for Directed Steiner Tree
Z. Friggstad, Y. K. Ko, J.K., A. Louis, M. Shadrawan and M. Tulsiani
IPCO 2014 (to appear)
Finding small stabilizers for unstable graphs
IPCO 2014 (to appear)
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: [arXiv:1207.6683]
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.
[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]
Hypergraphic LP Relaxations for Steiner Trees
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
Workshop on Approximation and Online Algorithms, 2008.
conference version: [pdf], journal version: [pdf]
On the Integrality Ratio for Tree Augmentation
[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
Symposium on Discrete Algorithms, 2007.
[pdf]
2006
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]
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
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
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
Symposium on Discrete Algorithms, 2005.
[pdf]
2004
Approximating k-Hop Minimum-Divning Trees
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
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
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
Symposium on Theoretical Aspects of Computer Science (STACS), 2003.
[ps]
A Combinatorial Algorithm for Computing a Maximum Independent Set in a t-perfect Graph
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
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