Jochen Könemann

Comput. Oper. Res., 2024

Fast Combinatorial Algorithms for Efficient Sortation.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2024

2023

Scalable timing-aware network design via lagrangian decomposition.

[BibT_eX]

[DOI]

Eur. J. Oper. Res., August, 2023

A Framework for Computing the Nucleolus via Dynamic Programming.

[BibT_eX]

[DOI]

ACM Trans. Economics and Comput., 2023

Dynamic discretization discovery under hard node storage constraints.

[BibT_eX]

[DOI]

Madison Van Dyk

CoRR, 2023

2021

On the Complexity of Nucleolus Computation for Bipartite b-Matching Games.

[BibT_eX]

[DOI]

Felix Zhou

Proceedings of the Algorithmic Game Theory - 14th International Symposium, 2021

Hitting Weighted Even Cycles in Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

On the Approximability of the Stable Matching Problem with Ties of Constant Size up to the Integrality Gap.

[BibT_eX]

[DOI]

Natig Tofigzade

CoRR, 2020

A General Framework for Computing the Nucleolus via Dynamic Programming.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory - 13th International Symposium, 2020

Approximating Stable Matchings with Ties of Bounded Size.

[BibT_eX]

[DOI]

Natig Tofigzade

Proceedings of the Algorithmic Game Theory - 13th International Symposium, 2020

2019

Vehicle routing with subtours.

[BibT_eX]

[DOI]

Stephan Held

Karthekeyan Chandrasekaran

Jens Vygen

Discret. Optim., 2019

Additive stabilizers for unstable graphs.

[BibT_eX]

[DOI]

Discret. Optim., 2019

Travelling on Graphs with Small Highway Dimension.

[BibT_eX]

[DOI]

Yann Disser

Max Klimm

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2019

Computing the Nucleolus of Weighted Cooperative Matching Games in Polynomial Time.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2019

2018

Special Section on the Forty-Sixth Annual ACM Symposium on Theory of Computing (STOC 2014).

[BibT_eX]

[DOI]

Adam Smith

SIAM J. Comput., 2018

Approximating Weighted Tree Augmentation via Chvátal-Gomory Cuts.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

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

[BibT_eX]

[DOI]

CoRR, 2017

On the Integrality Gap of the Prize-Collecting Steiner Forest LP.

[BibT_eX]

[DOI]

Neil Olver

Chaitanya Swamy

Jens Vygen

Proceedings of the Approximation, 2017

2016

Lehman's Theorem and the Directed Steiner Tree Problem.

[BibT_eX]

[DOI]

Ahmad Abdi

Bertrand Guenin

SIAM J. Discret. Math., 2016

An elementary integrality proof of Rothblum's stable matching formulation.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2016

Stable Marriage with General Preferences.

[BibT_eX]

[DOI]

Linda Farczadi

Theory Comput. Syst., 2016

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

[BibT_eX]

[DOI]

CoRR, 2016

A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs .

[BibT_eX]

[DOI]

Zachary Friggstad

Mohammad Shadravan

Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Fast Approximation Algorithms for the Generalized Survivable Network Design Problem.

[BibT_eX]

[DOI]

Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

2015

Efficient cost-sharing mechanisms for prize-collecting problems.

[BibT_eX]

[DOI]

Math. Program., 2015

A (1+ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs.

[BibT_eX]

[DOI]

Wai Shing Fung

Mohammad Taghi Hajiaghayi

Ian Post

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Approximate Deadline-Scheduling with Precedence Constraints.

[BibT_eX]

[DOI]

Hossein Efsandiari

Proceedings of the Algorithms - ESA 2015, 2015

2014

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

[BibT_eX]

[DOI]

Ojas Parekh

Algorithmica, 2014

Stable Marriage with General Preferences - Extended Abstract.

[BibT_eX]

[DOI]

Linda Farczadi

Karthekeyan Chandrasekaran

Proceedings of the Algorithmic Game Theory - 7th International Symposium, 2014

Linear Programming Hierarchies Suffice for Directed Steiner Tree.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2014

Finding Small Stabilizers for Unstable Graphs.

[BibT_eX]

[DOI]

Adrian Bock

Britta Peis

Proceedings of the Integer Programming and Combinatorial Optimization, 2014

On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree.

[BibT_eX]

[DOI]

Neil Olver

Proceedings of the Approximation, 2014

2013

An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree.

[BibT_eX]

[DOI]

Sina Sadeghian Sadeghabad

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Better Approximation Algorithms for Technology Diffusion.

[BibT_eX]

[DOI]

Sina Sadeghian Sadeghabad

Proceedings of the Algorithms - ESA 2013, 2013

Network Bargaining with General Capacities.

[BibT_eX]

[DOI]

Linda Farczadi

Proceedings of the Algorithms - ESA 2013, 2013

Social Exchange Networks with Distant Bargaining.

[BibT_eX]

[DOI]

George Karakostas

Zuzanna Stamirowska

Proceedings of the Computing and Combinatorics, 19th International Conference, 2013

2012

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

[BibT_eX]

[DOI]

Isaac Fung

Malcolm Sharpe

CoRR, 2012

Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Network Bargaining: Using Approximate Blocking Sets to Stabilize Unstable Instances.

[BibT_eX]

[DOI]

Kate Larson

David Steiner

Proceedings of the Algorithmic Game Theory - 5th International Symposium, 2012

2011

A partition-based relaxation for Steiner trees.

[BibT_eX]

[DOI]

Kunlun Tan

Math. Program., 2011

The School Bus Problem on Trees.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

Winning Strategies for a Matchstick Game.

[BibT_eX]

[DOI]

Proceedings of the Algorithms Unplugged, 2011

2010

Strict Cost Sharing Schemes for Steiner Forest.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Oper. Res. Lett., 2010

Hypergraphic LP Relaxations for Steiner Trees.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

On Column-Restricted and Priority Covering Integer Programs.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Elyot Grant

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

On Generalizations of Network Design Problems with Degree Bounds.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

2008

Gewinnstrategie für ein Streichholzspiel.

[BibT_eX]

[DOI]

Proceedings of the Taschenbuch der Algorithmen, 2008

A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game.

[BibT_eX]

[DOI]

Stefano Leonardi

Guido Schäfer

Stefan H. M. van Zwam

SIAM J. Comput., 2008

A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

On the integrality ratio for tree augmentation.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2008

Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees.

[BibT_eX]

[DOI]

Ojas Parekh

Proceedings of the Approximation and Online Algorithms, 6th International Workshop, 2008

2007

An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem.

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006

Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Cut Problems in Graphs with a Budget Constraint.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2006: Theoretical Informatics, 2006

A Unified Approach to Approximating Partial Covering Problems.

[BibT_eX]

[DOI]

Ojas Parekh

Danny Segev

Proceedings of the Algorithms, 2006

2005

Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

Approximating k-hop minimum-spanning trees.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2005

A group-strategyproof mechanism for Steiner forests.

[BibT_eX]

[DOI]

Stefano Leonardi

Guido Schäfer

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Primal-dual based distributed algorithms for vertex cover with semi-hard capacities.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Stefano Leonardi

Guido Schäfer

Stefan H. M. van Zwam

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Distributed Weighted Vertex Cover via Maximal Matchings.

[BibT_eX]

[DOI]

Fabrizio Grandoni

Alessandro Panconesi

Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2004

An approximation algorithm for the edge-dilation k-center problem, .

[BibT_eX]

[DOI]

Oper. Res. Lett., 2004

Min-max tree covers of graphs.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2004

2003

Primal-dual meets local search: approximating MST's with nonuniform degree bounds.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Non-clairvoyant Scheduling for Minimizing Mean Slowdown.

[BibT_eX]

[DOI]

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

A combinatorial algorithm for computing a maximum independent set in a t-perfect graph.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem.

[BibT_eX]

[DOI]

Asaf Levin

Amitabh Sinha

Proceedings of the Approximation, 2003

Covering Graphs Using Trees and Stars.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2003

Quasi-polynomial Time Approximation Algorithm for Low-Degree Minimum-Cost Steiner Trees.

[BibT_eX]

[DOI]

Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

2002

Approximation Algorithms for Edge-Dilation k-Center Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2002

2000

A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Improved approximations for tour and tree covers.

[BibT_eX]

[DOI]

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1998

Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems.

[BibT_eX]

[DOI]

Naveen Garg