Current students

 

 

IPCO2017

 

HIM Summer School

 



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

Recent work

Teaching

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
SODA 2018 [pdf]
2017
On the Integrality Gap of the Prize-Collecting Steiner Forest LP
Approx-Random 2017 [pdf]
2016
An Elementary Integrality Proof of Rothblum's Stable Matching Formulation.
arXiv:1605.04427 [pdf]
Fast Approximation Algorithms for the Generalized Survivable Network Design Problem
arXiv:1604.07049 [pdf]
A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs.
SWAT 2016 -- [pdf]
2015
Approximate Deadline-Scheduling with Precedence Constraints.
A (1 + ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
A. Feldmann, I. Fung, JK, I. Post
2014
Stable Marriage with General Preferences
SAGT 2014 -- [pdf]
On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree
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
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.
[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