Jochen Könemann

122 papers A* 13A 5B 19Misc 2Journal 70Unranked 11
YearRankTypeTitle / Venue / Authors
2024 B conf
Fast Combinatorial Algorithms for Efficient Sortation.
IPCO
Madison Van Dyk, Kim Klause, Jochen Könemann, Nicole Megow
2024 J jnl
On the complexity of nucleolus computation for bipartite b-matching games.
Theor. Comput. Sci.
Jochen Könemann, Justin Toth, Felix Zhou
2024 J jnl
Sparse dynamic discretization discovery via arc-dependent time discretizations.
Comput. Oper. Res.
Madison Van Dyk, Jochen Könemann
2023 J jnl
A Framework for Computing the Nucleolus via Dynamic Programming.
ACM Trans. Economics and Comput.
Jochen Könemann, Justin Toth
2023 J jnl
Dynamic discretization discovery under hard node storage constraints.
CoRR
Madison Van Dyk, Jochen Könemann
2023 J jnl
Fast Combinatorial Algorithms for Efficient Sortation.
CoRR
Madison Van Dyk, Kim Klause, Jochen Könemann, Nicole Megow
2023 J jnl
Scalable timing-aware network design via lagrangian decomposition.
Eur. J. Oper. Res.
Cristiana L. Lara, Jochen Könemann, Yisu Nie, Cid C. de Souza
2023 J jnl
Sparse dynamic discretization discovery via arc-dependent time discretizations.
CoRR
Madison Van Dyk, Jochen Könemann
2022 J jnl
Hitting Weighted Even Cycles in Planar Graphs.
SIAM J. Discret. Math.
Alexander Göke, Jochen Könemann, Matthias Mnich, Hao Sun
2021 B ed.
Approximation and Online Algorithms - 19th International Workshop, WAOA 2021, Lisbon, Portugal, September 6-10, 2021, Revised Selected Papers
WAOA
Jochen Könemann, Britta Peis
2021 — conf
Hitting Weighted Even Cycles in Planar Graphs.
APPROX-RANDOM
Alexander Göke, Jochen Könemann, Matthias Mnich, Hao Sun
2021 J jnl
Hitting Weighted Even Cycles in Planar Graphs.
CoRR
Alexander Göke, Jochen Könemann, Matthias Mnich, Hao Sun
2021 B conf
On the Complexity of Nucleolus Computation for Bipartite b-Matching Games.
SAGT
Jochen Könemann, Justin Toth, Felix Zhou
2021 J jnl
On the Complexity of Nucleolus Computation for Bipartite b-Matching Games.
CoRR
Jochen Könemann, Justin Toth, Felix Zhou
2021 J jnl
Travelling on Graphs with Small Highway Dimension.
Algorithmica
Yann Disser, Andreas Emil Feldmann, Max Klimm, Jochen Könemann
2020 J jnl
A General Framework for Computing the Nucleolus Via Dynamic Programming.
CoRR
Jochen Könemann, Justin Toth
2020 B conf
A General Framework for Computing the Nucleolus via Dynamic Programming.
SAGT
Jochen Könemann, Justin Toth
2020 B conf
Approximating Stable Matchings with Ties of Bounded Size.
SAGT
Jochen Könemann, Kanstantsin Pashkovich, Natig Tofigzade
2020 J jnl
Computing the nucleolus of weighted cooperative matching games in polynomial time.
Math. Program.
Jochen Könemann, Kanstantsin Pashkovich, Justin Toth
2020 J jnl
On the Approximability of the Stable Matching Problem with Ties of Constant Size up to the Integrality Gap.
CoRR
Jochen Könemann, Kanstantsin Pashkovich, Natig Tofigzade
2019 J jnl
Additive stabilizers for unstable graphs.
Discret. Optim.
Karthekeyan Chandrasekaran, Corinna Gottschalk, Jochen Könemann, Britta Peis, Daniel Schmand, Andreas Wierz
2019 B conf
Computing the Nucleolus of Weighted Cooperative Matching Games in Polynomial Time.
IPCO
Jochen Könemann, Kanstantsin Pashkovich, Justin Toth
2019 B conf
Travelling on Graphs with Small Highway Dimension.
WG
Yann Disser, Andreas Emil Feldmann, Max Klimm, Jochen Könemann
2019 J jnl
Travelling on Graphs with Small Highway Dimension.
CoRR
Yann Disser, Andreas Emil Feldmann, Max Klimm, Jochen Könemann
2019 J jnl
Vehicle routing with subtours.
Discret. Optim.
Stephan Held, Jochen Könemann, Jens Vygen
2018 J jnl
A (1+ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs.
SIAM J. Comput.
Andreas Emil Feldmann, Wai Shing Fung, Jochen Könemann, Ian Post
2018 A* conf
Approximating Weighted Tree Augmentation via Chvátal-Gomory Cuts.
SODA
Samuel Fiorini, Martin Groß, Jochen Könemann, Laura Sanità
2018 J jnl
Computing the Nucleolus of Weighted Cooperative Matching Games in Polynomial Time.
CoRR
Jochen Könemann, Kanstantsin Pashkovich, Justin Toth
2018 J jnl
Special Section on the Forty-Sixth Annual ACM Symposium on Theory of Computing (STOC 2014).
SIAM J. Comput.
Adam Smith, Jochen Könemann
2018 J jnl
Vehicle Routing with Subtours.
CoRR
Stephan Held, Jochen Könemann, Jens Vygen
2017 J jnl
A 3/2-Approximation Algorithm for Tree Augmentation via Chvátal-Gomory Cuts.
CoRR
Samuel Fiorini, Martin Groß, Jochen Könemann, Laura Sanità
2017 B ed.
Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings
IPCO
Friedrich Eisenbrand, Jochen Könemann
2017 — conf
On the Integrality Gap of the Prize-Collecting Steiner Forest LP.
APPROX-RANDOM
Jochen Könemann, Neil Olver, Kanstantsin Pashkovich, R. Ravi, Chaitanya Swamy, Jens Vygen
2017 J jnl
On the Integrality Gap of the Prize-Collecting Steiner Forest LP.
CoRR
Jochen Könemann, Neil Olver, Kanstantsin Pashkovich, R. Ravi, Chaitanya Swamy, Jens Vygen
2016 — conf
A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs .
SWAT
Zachary Friggstad, Jochen Könemann, Mohammad Shadravan
2016 J jnl
A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs.
CoRR
Zachary Friggstad, Jochen Könemann, Mohammad Shadravan
2016 J jnl
Additive Stabilizers for Unstable Graphs.
CoRR
Karthekeyan Chandrasekaran, Corinna Gottschalk, Jochen Könemann, Britta Peis, Daniel Schmand, Andreas Wierz
2016 J jnl
An elementary integrality proof of Rothblum's stable matching formulation.
Oper. Res. Lett.
Jochen Könemann, Kanstantsin Pashkovich, Justin Toth
2016 B conf
Fast Approximation Algorithms for the Generalized Survivable Network Design Problem.
ISAAC
Andreas Emil Feldmann, Jochen Könemann, Kanstantsin Pashkovich, Laura Sanità
2016 J jnl
Fast Approximation Algorithms for the Generalized Survivable Network Design Problem.
CoRR
Andreas Emil Feldmann, Jochen Könemann, Kanstantsin Pashkovich, Laura Sanità
2016 J jnl
Lehman's Theorem and the Directed Steiner Tree Problem.
SIAM J. Discret. Math.
Ahmad Abdi, Andreas Emil Feldmann, Bertrand Guenin, Jochen Könemann, Laura Sanità
2016 J jnl
On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree.
Math. Program.
Andreas Emil Feldmann, Jochen Könemann, Neil Olver, Laura Sanità
2016 J jnl
Stable Marriage with General Preferences.
Theory Comput. Syst.
Linda Farczadi, Konstantinos Georgiou, Jochen Könemann
2016 J jnl
The Power of Locality: An Elementary Integrality Proof of Rothblum's Stable Matching Formulation.
CoRR
Jochen Könemann, Kanstantsin Pashkovich, Justin Toth
2015 J jnl
A (1 + ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs.
CoRR
Andreas Emil Feldmann, Wai Shing Fung, Jochen Könemann, Ian Post
2015 — conf
A (1+ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs.
ICALP (1)
Andreas Emil Feldmann, Wai Shing Fung, Jochen Könemann, Ian Post
2015 A conf
Approximate Deadline-Scheduling with Precedence Constraints.
ESA
Hossein Efsandiari, Mohammad Taghi Hajiaghayi, Jochen Könemann, Hamid Mahini, David L. Malec, Laura Sanità
2015 J jnl
Approximate Deadline-Scheduling with Precedence Constraints.
CoRR
Hossein Esfandiari, Mohammad Taghi Hajiaghayi, Jochen Könemann, Hamid Mahini, David L. Malec, Laura Sanità
2015 J jnl
Efficient cost-sharing mechanisms for prize-collecting problems.
Math. Program.
Anupam Gupta, Jochen Könemann, Stefano Leonardi, R. Ravi, Guido Schäfer
2015 J jnl
Finding small stabilizers for unstable graphs.
Math. Program.
Adrian Bock, Karthekeyan Chandrasekaran, Jochen Könemann, Britta Peis, Laura Sanità
2015 J jnl
Network Bargaining: Using Approximate Blocking Sets to Stabilize Unstable Instances.
Theory Comput. Syst.
Jochen Könemann, Kate Larson, David Steiner
2014 B conf
Finding Small Stabilizers for Unstable Graphs.
IPCO
Adrian Bock, Karthekeyan Chandrasekaran, Jochen Könemann, Britta Peis, Laura Sanità
2014 B conf
Linear Programming Hierarchies Suffice for Directed Steiner Tree.
IPCO
Zachary Friggstad, Jochen Könemann, Young Kun-Ko, Anand Louis, Mohammad Shadravan, Madhur Tulsiani
2014 J jnl
Multicommodity Flow in Trees: Packing via Covering and Iterated Relaxation.
Algorithmica
Jochen Könemann, Ojas Parekh, David Pritchard
2014 — conf
On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree.
APPROX-RANDOM
Andreas Emil Feldmann, Jochen Könemann, Neil Olver, Laura Sanità
2014 J jnl
Social exchange networks with distant bargaining.
Theor. Comput. Sci.
Konstantinos Georgiou, George Karakostas, Jochen Könemann, Zuzanna Stamirowska
2014 B conf
Stable Marriage with General Preferences - Extended Abstract.
SAGT
Linda Farczadi, Konstantinos Georgiou, Jochen Könemann
2014 J jnl
Stable marriage with general preferences.
CoRR
Linda Farczadi, Konstantinos Georgiou, Jochen Könemann
2013 J jnl
An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree
CoRR
Jochen Könemann, Sina Sadeghian Sadeghabad, Laura Sanità
2013 A* conf
An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree.
FOCS
Jochen Könemann, Sina Sadeghian Sadeghabad, Laura Sanità
2013 A conf
Better Approximation Algorithms for Technology Diffusion.
ESA
Jochen Könemann, Sina Sadeghian Sadeghabad, Laura Sanità
2013 J jnl
Hypergraphic LP Relaxations for Steiner Trees.
SIAM J. Discret. Math.
Deeparnab Chakrabarty, Jochen Könemann, David Pritchard
2013 A conf
Network Bargaining with General Capacities.
ESA
Linda Farczadi, Konstantinos Georgiou, Jochen Könemann
2013 J jnl
Network bargaining with general capacities.
CoRR
Linda Farczadi, Konstantinos Georgiou, Jochen Könemann
2013 J jnl
On generalizations of network design problems with degree bounds.
Math. Program.
Nikhil Bansal, Rohit Khandekar, Jochen Könemann, Viswanath Nagarajan, Britta Peis
2013 Misc conf
Social Exchange Networks with Distant Bargaining.
COCOON
Konstantinos Georgiou, George Karakostas, Jochen Könemann, Zuzanna Stamirowska
2013 J jnl
The School Bus Problem on Trees.
Algorithmica
Adrian Bock, Elyot Grant, Jochen Könemann, Laura Sanità
2012 J jnl
Efficient Algorithms for Solving Hypergraphic Steiner Tree Relaxations in Quasi-Bipartite Instances
CoRR
Isaac Fung, Konstantinos Georgiou, Jochen Könemann, Malcolm Sharpe
2012 J jnl
Network Bargaining: Using Approximate Blocking Sets to Stabilize Unstable Instances
CoRR
Jochen Könemann, Kate Larson, David Steiner
2012 B conf
Network Bargaining: Using Approximate Blocking Sets to Stabilize Unstable Instances.
SAGT
Jochen Könemann, Kate Larson, David Steiner
2012 A* conf
Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling.
SODA
Timothy M. Chan, Elyot Grant, Jochen Könemann, Malcolm Sharpe
2011 J jnl
A Unified Approach to Approximating Partial Covering Problems.
Algorithmica
Jochen Könemann, Ojas Parekh, Danny Segev
2011 J jnl
A partition-based relaxation for Steiner trees.
Math. Program.
Jochen Könemann, David Pritchard, Kunlun Tan
2011 B conf
The School Bus Problem on Trees.
ISAAC
Adrian Bock, Elyot Grant, Jochen Könemann, Laura Sanità
2011 — ch.
Winning Strategies for a Matchstick Game.
Algorithms Unplugged
Jochen Könemann
2010 B conf
Hypergraphic LP Relaxations for Steiner Trees.
IPCO
Deeparnab Chakrabarty, Jochen Könemann, David Pritchard
2010 J jnl
Integrality Gap of the Hypergraphic Relaxation of Steiner Trees: a short proof of a 1.55 upper bound
CoRR
Deeparnab Chakrabarty, Jochen Könemann, David Pritchard
2010 J jnl
Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound.
Oper. Res. Lett.
Deeparnab Chakrabarty, Jochen Könemann, David Pritchard
2010 B conf
On Column-Restricted and Priority Covering Integer Programs.
IPCO
Deeparnab Chakrabarty, Elyot Grant, Jochen Könemann
2010 J jnl
On Column-restricted and Priority Covering Integer Programs
CoRR
Deeparnab Chakrabarty, Elyot Grant, Jochen Könemann
2010 J jnl
On Generalizations of Network Design Problems with Degree Bounds
CoRR
Nikhil Bansal, Rohit Khandekar, Jochen Könemann, Viswanath Nagarajan, Britta Peis
2010 B conf
On Generalizations of Network Design Problems with Degree Bounds.
IPCO
Nikhil Bansal, Rohit Khandekar, Jochen Könemann, Viswanath Nagarajan, Britta Peis
2010 J jnl
Strict Cost Sharing Schemes for Steiner Forest.
SIAM J. Comput.
Lisa Fleischer, Jochen Könemann, Stefano Leonardi, Guido Schäfer
2009 J jnl
Hypergraphic LP Relaxations for Steiner Trees
CoRR
Deeparnab Chakrabarty, Jochen Könemann, David Pritchard
2008 J jnl
A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game.
SIAM J. Comput.
Jochen Könemann, Stefano Leonardi, Guido Schäfer, Stefan H. M. van Zwam
2008 J jnl
A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover.
SIAM J. Comput.
Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi, Mauro Sozio
2008 J jnl
Distributed weighted vertex cover via maximal matchings.
ACM Trans. Algorithms
Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi
2008 — ch.
Gewinnstrategie für ein Streichholzspiel.
Taschenbuch der Algorithmen
Jochen Könemann
2008 B conf
Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees.
WAOA
Jochen Könemann, Ojas Parekh, David Pritchard
2008 J jnl
On the integrality ratio for tree augmentation.
Oper. Res. Lett.
Joseph Cheriyan, Howard J. Karloff, Rohit Khandekar, Jochen Könemann
2007 J jnl
A Partition-Based Relaxation For Steiner Trees
CoRR
Jochen Könemann, David Pritchard, Kunlun Tan
2007 A* conf
An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem.
SODA
Anupam Gupta, Jochen Könemann, Stefano Leonardi, R. Ravi, Guido Schäfer
2007 J jnl
Cut problems in graphs with a budget constraint.
J. Discrete Algorithms
Roee Engelberg, Jochen Könemann, Stefano Leonardi, Joseph Naor
2007 J jnl
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems.
SIAM J. Comput.
Naveen Garg, Jochen Könemann
2007 J jnl
Sharing the cost more efficiently: Improved approximation for multicommodity rent-or-buy.
ACM Trans. Algorithms
Luca Becchetti, Jochen Könemann, Stefano Leonardi, Martin Pál
2006 A conf
A Unified Approach to Approximating Partial Covering Problems.
ESA
Jochen Könemann, Ojas Parekh, Danny Segev
2006 B conf
Cut Problems in Graphs with a Budget Constraint.
LATIN
Roee Engelberg, Jochen Könemann, Stefano Leonardi, Joseph Naor
2006 A* conf
Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree.
STOC
Lisa Fleischer, Jochen Könemann, Stefano Leonardi, Guido Schäfer
2005 A* conf
A group-strategyproof mechanism for Steiner forests.
SODA
Jochen Könemann, Stefano Leonardi, Guido Schäfer
2005 J jnl
Approximating
Oper. Res. Lett.
Ernst Althaus, Stefan Funke, Sariel Har-Peled, Jochen Könemann, Edgar A. Ramos, Martin Skutella
2005 J jnl
Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem.
Algorithmica
Jochen Könemann, Asaf Levin, Amitabh Sinha
2005 Misc conf
Distributed Weighted Vertex Cover via Maximal Matchings.
COCOON
Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi
2005 A* conf
From Primal-Dual to Cost Shares and Back: A Stronger LP Relaxation for the Steiner Forest Problem.
ICALP
Jochen Könemann, Stefano Leonardi, Guido Schäfer, Stefan H. M. van Zwam
2005 J jnl
Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds.
SIAM J. Comput.
Jochen Könemann, R. Ravi
2005 A* conf
Primal-dual based distributed algorithms for vertex cover with semi-hard capacities.
PODC
Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi, Mauro Sozio
2005 A* conf
Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy.
SODA
Luca Becchetti, Jochen Könemann, Stefano Leonardi, Martin Pál
2004 J jnl
An approximation algorithm for the edge-dilation
Oper. Res. Lett.
Jochen Könemann, Yanjun Li, Ojas Parekh, Amitabh Sinha
2004 J jnl
Improved Approximations for Tour and Tree Covers.
Algorithmica
Jochen Könemann, Goran Konjevod, Ojas Parekh, Amitabh Sinha
2004 J jnl
Min-max tree covers of graphs.
Oper. Res. Lett.
Guy Even, Naveen Garg, Jochen Könemann, R. Ravi, Amitabh Sinha
2004 J jnl
Non-Clairvoyant Scheduling for Minimizing Mean Slowdown.
Algorithmica
Nikhil Bansal, Kedar Dhamdhere, Jochen Könemann, Amitabh Sinha
2003 A* conf
A combinatorial algorithm for computing a maximum independent set in a t-perfect graph.
SODA
Friedrich Eisenbrand, Stefan Funke, Naveen Garg, Jochen Könemann
2003 — conf
Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem.
RANDOM-APPROX
Jochen Könemann, Asaf Levin, Amitabh Sinha
2003 — conf
Covering Graphs Using Trees and Stars.
RANDOM-APPROX
Guy Even, Naveen Garg, Jochen Könemann, R. Ravi, Amitabh Sinha
2003 A conf
Non-clairvoyant Scheduling for Minimizing Mean Slowdown.
STACS
Nikhil Bansal, Kedar Dhamdhere, Jochen Könemann, Amitabh Sinha
2003 A* conf
Primal-dual meets local search: approximating MST's with nonuniform degree bounds.
STOC
Jochen Könemann, R. Ravi
2003 — conf
Quasi-polynomial Time Approximation Algorithm for Low-Degree Minimum-Cost Steiner Trees.
FSTTCS
Jochen Könemann, R. Ravi
2002 J jnl
A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees.
SIAM J. Comput.
Jochen Könemann, R. Ravi
2002 — conf
Approximation Algorithms for Edge-Dilation k-Center Problems.
SWAT
Jochen Könemann, Yanjun Li, Ojas Parekh, Amitabh Sinha
2000 A* conf
A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees.
STOC
Jochen Könemann, R. Ravi
2000 — conf
Improved approximations for tour and tree covers.
APPROX
Jochen Könemann, Goran Konjevod, Ojas Parekh, Amitabh Sinha
1998 A* conf
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems.
FOCS
Naveen Garg, Jochen Könemann
1995 — conf
Exact Geometric Computation in LEDA.
SCG
Christoph Burnikel, Jochen Könemann, Kurt Mehlhorn, Stefan Näher, Stefan Schirra, Christian Uhrig