Jochen Könemann

ACM Trans. Economics and Comput., 2023

Fast Combinatorial Algorithms for Efficient Sortation.

[BibT_eX]

[DOI]

CoRR, 2023

Sparse dynamic discretization discovery via arc-dependent time discretizations.

[BibT_eX]

[DOI]

Madison Van Dyk

CoRR, 2023

Dynamic discretization discovery under hard node storage constraints.

[BibT_eX]

[DOI]

Madison Van Dyk

CoRR, 2023

2022

Hitting Weighted Even Cycles in Planar Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., December, 2022

2021

Travelling on Graphs with Small Highway Dimension.

[BibT_eX]

[DOI]

Yann Disser

Max Klimm

Algorithmica, 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

2020

Computing the nucleolus of weighted cooperative matching games in polynomial time.

[BibT_eX]

[DOI]

Math. Program., 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

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

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

[BibT_eX]

[DOI]

Wai Shing Fung

Ian Post

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

On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree.

[BibT_eX]

[DOI]

Neil Olver

Math. Program., 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

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

[BibT_eX]

[DOI]

Karthekeyan Chandrasekaran

Kate Larson

David Steiner

Theory Comput. Syst., 2015

Efficient cost-sharing mechanisms for prize-collecting problems.

[BibT_eX]

[DOI]

Math. Program., 2015

Finding small stabilizers for unstable graphs.

[BibT_eX]

[DOI]

Adrian Bock

Britta Peis

Mohammad Taghi Hajiaghayi

Math. Program., 2015

Approximate Deadline-Scheduling with Precedence Constraints.

[BibT_eX]

[DOI]

Hossein Efsandiari

Proceedings of the Algorithms - ESA 2015, 2015

2014

Social exchange networks with distant bargaining.

[BibT_eX]

[DOI]

George Karakostas

Zuzanna Stamirowska

Theor. Comput. Sci., 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

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

2013

Hypergraphic LP Relaxations for Steiner Trees.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

SIAM J. Discret. Math., 2013

On generalizations of network design problems with degree bounds.

[BibT_eX]

[DOI]

Math. Program., 2013

The School Bus Problem on Trees.

[BibT_eX]

[DOI]

Algorithmica, 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

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

2011

A partition-based relaxation for Steiner trees.

[BibT_eX]

[DOI]

Kunlun Tan

Math. Program., 2011

A Unified Approach to Approximating Partial Covering Problems.

[BibT_eX]

[DOI]

Ojas Parekh

Danny Segev

Algorithmica, 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

On Column-Restricted and Priority Covering Integer Programs.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Elyot Grant

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

Distributed weighted vertex cover via maximal matchings.

[BibT_eX]

[DOI]

Fabrizio Grandoni

Alessandro Panconesi

ACM Trans. Algorithms, 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

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

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2007

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

[BibT_eX]

[DOI]

Naveen Garg

SIAM J. Comput., 2007

Cut problems in graphs with a budget constraint.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 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

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

Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem.

[BibT_eX]

[DOI]

Asaf Levin

Amitabh Sinha

Algorithmica, 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

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

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

Improved Approximations for Tour and Tree Covers.

[BibT_eX]

[DOI]

Algorithmica, 2004

Non-Clairvoyant Scheduling for Minimizing Mean Slowdown.

[BibT_eX]

[DOI]

Algorithmica, 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

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

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

A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees.

[BibT_eX]

[DOI]