Jochen Könemann

According to our database1, Jochen Könemann authored at least 66 papers between 1995 and 2019.

Collaborative distances:



In proceedings 
PhD thesis 




Vehicle routing with subtours.
Discrete Optimization, 2019

Additive stabilizers for unstable graphs.
Discrete Optimization, 2019

Travelling on Graphs with Small Highway Dimension.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2019

Computing the Nucleolus of Weighted Cooperative Matching Games in Polynomial Time.
Proceedings of the Integer Programming and Combinatorial Optimization, 2019

Special Section on the Forty-Sixth Annual ACM Symposium on Theory of Computing (STOC 2014).
SIAM J. Comput., 2018

A (1+ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs.
SIAM J. Comput., 2018

Approximating Weighted Tree Augmentation via Chvátal-Gomory Cuts.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

A 3/2-Approximation Algorithm for Tree Augmentation via Chvátal-Gomory Cuts.
CoRR, 2017

On the Integrality Gap of the Prize-Collecting Steiner Forest LP.
Proceedings of the Approximation, 2017

Lehman's Theorem and the Directed Steiner Tree Problem.
SIAM J. Discrete Math., 2016

An elementary integrality proof of Rothblum's stable matching formulation.
Oper. Res. Lett., 2016

Stable Marriage with General Preferences.
Theory Comput. Syst., 2016

On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree.
Math. Program., 2016

The Power of Locality: An Elementary Integrality Proof of Rothblum's Stable Matching Formulation.
CoRR, 2016

A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs .
Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Fast Approximation Algorithms for the Generalized Survivable Network Design Problem.
Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

Network Bargaining: Using Approximate Blocking Sets to Stabilize Unstable Instances.
Theory Comput. Syst., 2015

Efficient cost-sharing mechanisms for prize-collecting problems.
Math. Program., 2015

Finding small stabilizers for unstable graphs.
Math. Program., 2015

Approximate Deadline-Scheduling with Precedence Constraints.
Proceedings of the Algorithms - ESA 2015, 2015

Social exchange networks with distant bargaining.
Theor. Comput. Sci., 2014

Multicommodity Flow in Trees: Packing via Covering and Iterated Relaxation.
Algorithmica, 2014

Stable Marriage with General Preferences - Extended Abstract.
Proceedings of the Algorithmic Game Theory - 7th International Symposium, 2014

Linear Programming Hierarchies Suffice for Directed Steiner Tree.
Proceedings of the Integer Programming and Combinatorial Optimization, 2014

Hypergraphic LP Relaxations for Steiner Trees.
SIAM J. Discrete Math., 2013

On generalizations of network design problems with degree bounds.
Math. Program., 2013

The School Bus Problem on Trees.
Algorithmica, 2013

An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Better Approximation Algorithms for Technology Diffusion.
Proceedings of the Algorithms - ESA 2013, 2013

Network Bargaining with General Capacities.
Proceedings of the Algorithms - ESA 2013, 2013

Efficient Algorithms for Solving Hypergraphic Steiner Tree Relaxations in Quasi-Bipartite Instances
CoRR, 2012

Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

A partition-based relaxation for Steiner trees.
Math. Program., 2011

A Unified Approach to Approximating Partial Covering Problems.
Algorithmica, 2011

Winning Strategies for a Matchstick Game.
Proceedings of the Algorithms Unplugged, 2011

Strict Cost Sharing Schemes for Steiner Forest.
SIAM J. Comput., 2010

Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound.
Oper. Res. Lett., 2010

On Column-Restricted and Priority Covering Integer Programs.
Proceedings of the Integer Programming and Combinatorial Optimization, 2010

Gewinnstrategie für ein Streichholzspiel.
Proceedings of the Taschenbuch der Algorithmen, 2008

Distributed weighted vertex cover via maximal matchings.
ACM Trans. Algorithms, 2008

A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game.
SIAM J. Comput., 2008

A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover.
SIAM J. Comput., 2008

On the integrality ratio for tree augmentation.
Oper. Res. Lett., 2008

Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees.
Proceedings of the Approximation and Online Algorithms, 6th International Workshop, 2008

Sharing the cost more efficiently: Improved approximation for multicommodity rent-or-buy.
ACM Trans. Algorithms, 2007

Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems.
SIAM J. Comput., 2007

Cut problems in graphs with a budget constraint.
J. Discrete Algorithms, 2007

An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds.
SIAM J. Comput., 2005

Approximating k-hop minimum-spanning trees.
Oper. Res. Lett., 2005

Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem.
Algorithmica, 2005

A group-strategyproof mechanism for Steiner forests.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Primal-dual based distributed algorithms for vertex cover with semi-hard capacities.
Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, 2005

From Primal-Dual to Cost Shares and Back: A Stronger LP Relaxation for the Steiner Forest Problem.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

An approximation algorithm for the edge-dilation k-center problem, .
Oper. Res. Lett., 2004

Min-max tree covers of graphs.
Oper. Res. Lett., 2004

Improved Approximations for Tour and Tree Covers.
Algorithmica, 2004

Non-Clairvoyant Scheduling for Minimizing Mean Slowdown.
Algorithmica, 2004

Primal-dual meets local search: approximating MST's with nonuniform degree bounds.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

A combinatorial algorithm for computing a maximum independent set in a t-perfect graph.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Covering Graphs Using Trees and Stars.
Proceedings of the Approximation, 2003

Quasi-polynomial Time Approximation Algorithm for Low-Degree Minimum-Cost Steiner Trees.
Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees.
SIAM J. Comput., 2002

Approximation Algorithms for Edge-Dilation k-Center Problems.
Proceedings of the Algorithm Theory, 2002

Exact Geometric Computation in LEDA.
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995