Tobias Mömke

Victor Verdugo

Math. Program., July, 2024

Multithread interval scheduling with flexible machine availabilities: Complexity and efficient algorithms.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2024

Approximating TSP Variants Using a Bridge Lemma.

[BibT_eX]

[DOI]

CoRR, 2024

2023

Approximating Maximum Edge 2-Coloring by Normalizing Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 21st International Workshop, 2023

Capacitated Vehicle Routing in Graphic Metrics.

[BibT_eX]

[DOI]

Hang Zhou

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Online Knapsack with Removal and Recourse.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 34th International Workshop, 2023

2022

Randomized Online Computation with High Probability Guarantees.

[BibT_eX]

[DOI]

Algorithmica, 2022

A PTAS for unsplittable flow on a path.

[BibT_eX]

[DOI]

Fabrizio Grandoni

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Unsplittable Flow on a Path: The Game!.

[BibT_eX]

[DOI]

Fabrizio Grandoni

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

A 3-Approximation Algorithm for Maximum Independent Set of Rectangles.

[BibT_eX]

[DOI]

Madhusudhan Reddy Pittu

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time.

[BibT_eX]

[DOI]

Vincent Cohen-Addad

Victor Verdugo

Proceedings of the Integer Programming and Combinatorial Optimization, 2022

Coworking Scheduling with Network Flows.

[BibT_eX]

[DOI]

Proceedings of the 10th International Network Optimization Conference, 2022

2021

A 4-Approximation Algorithm for Maximum Independent Set of Rectangles.

[BibT_eX]

[DOI]

Madhusudhan Reddy Pittu

CoRR, 2021

Faster (1+ε)-Approximation for Unsplittable Flow on a Path via Resource Augmentation and Back.

[BibT_eX]

[DOI]

Fabrizio Grandoni

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020

Managing Fleets of LEO Satellites: Nonlinear, Optimal, Efficient, Scalable, Usable, and Robust.

[BibT_eX]

[DOI]

IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2020

Robust Reoptimization of Steiner Trees.

[BibT_eX]

[DOI]

Keshav Goyal

Algorithmica, 2020

Breaking the Barrier of 2 for the Storage Allocation Problem.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2018

Semidefinite and linear programming integrality gaps for scheduling identical machines.

[BibT_eX]

[DOI]

Math. Program., 2018

Improved integrality gap upper bounds for traveling salesperson problems with distances one and two.

[BibT_eX]

[DOI]

Matthias Mnich

Eur. J. Oper. Res., 2018

A (5/3 + ε)-approximation for unsplittable flow on a path: placing small tasks into boxes.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Approximating Airports and Railways.

[BibT_eX]

[DOI]

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

A QPTAS for Gapless MEC.

[BibT_eX]

[DOI]

Shilpa Garg

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

A Modern View on Stability of Approximation.

[BibT_eX]

[DOI]

Ralf Klasing

Proceedings of the Adventures Between Lower Bounds and Higher Altitudes, 2018

2017

Improved analysis of the online set cover problem with advice.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

Online algorithms with advice: The tape model.

[BibT_eX]

[DOI]

Inf. Comput., 2017

Complexity and Approximability of Parameterized MAX-CSPs.

[BibT_eX]

[DOI]

Algorithmica, 2017

To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Maximum Scatter TSP in Doubling Metrics.

[BibT_eX]

[DOI]

László Kozma

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

Removing and Adding Edges for the Traveling Salesman Problem.

[BibT_eX]

[DOI]

Ola Svensson

J. ACM, 2016

Airports and Railways: Facility Location Meets Network Design.

[BibT_eX]

[DOI]

Anna Adamaszek

Antonios Antoniadis

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

The Complexity of Paging Against a Probabilistic Adversary.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2016: Theory and Practice of Computer Science, 2016

2015

An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2015

A PTAS for Euclidean Maximum Scatter TSP.

[BibT_eX]

[DOI]

László Kozma

CoRR, 2015

New Approximation Schemes for Unsplittable Flow on a Path.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

A (2+\epsilon ) ( 2 + ϵ ) -Approximation Algorithm for the Storage Allocation Problem.

[BibT_eX]

[DOI]

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

2014

Randomized Online Algorithms with High Probability Guarantees.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

2013

Improved approximations for TSP with simple precedence constraints.

[BibT_eX]

[DOI]

Monika Steinová

J. Discrete Algorithms, 2013

A Competitive Ratio Approximation Scheme for the k-Server Problem in Fixed Finite Metrics

[BibT_eX]

[DOI]

CoRR, 2013

Improved integrality gap upper bounds for TSP with distances one and two.

[BibT_eX]

[DOI]

Matthias Mnich

CoRR, 2013

2012

Steiner tree reoptimization in graphs with sharpened triangle inequality.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2012

Size complexity of rotating and sweeping automata.

[BibT_eX]

[DOI]

Christos A. Kapoutsis

Richard Královic

J. Comput. Syst. Sci., 2012

On the Advice Complexity of the Set Cover Problem.

[BibT_eX]

[DOI]

Dennis Komm

Richard Královic

Proceedings of the Computer Science - Theory and Applications, 2012

2011

Reoptimization of the Shortest Common Superstring Problem.

[BibT_eX]

[DOI]

Davide Bilò

Algorithmica, 2011

Structural Properties of Hard Metric TSP Inputs - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2011: Theory and Practice of Computer Science, 2011

Approximating Graphic TSP by Matchings.

[BibT_eX]

[DOI]

Ola Svensson

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Improved Approximations for Hard Optimization Problems via Problem Instance Classification.

[BibT_eX]

[DOI]

Juraj Hromkovic

Proceedings of the Rainbow of Computer Science, 2011

2010

Improved Approximations for TSP with Simple Precedence Constraints.

[BibT_eX]

[DOI]

Ralf Klasing

Monika Steinová

Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

The Steiner Tree Reoptimization Problem with Sharpened Triangle Inequality.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

2009

Algorithmic Approaches for Solving Hard Problems: Approximation and Complexity.

[BibT_eX]

[DOI]

PhD thesis, 2009

Reoptimization of Steiner trees: Changing the terminal set.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

On the power of randomization for job shop scheduling with k-units length tasks.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 2009

On the Advice Complexity of Online Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

2008

Reoptimization of Steiner Trees.

[BibT_eX]

[DOI]

Davide Bilò

Proceedings of the Algorithm Theory, 2008

On the Hardness of Reoptimization.

[BibT_eX]

[DOI]

Juraj Hromkovic

Peter Widmayer

Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

2007

Job Shop Scheduling with Unit Length Tasks: Bounds and Algorithms.

[BibT_eX]

[DOI]

Algorithmic Oper. Res., 2007

An Exponential Gap Between LasVegas and Deterministic Sweeping Finite Automata.

[BibT_eX]

[DOI]

Christos A. Kapoutsis

Richard Královic

Proceedings of the Stochastic Algorithms: Foundations and Applications, 2007

Efficient Algorithms for the Spoonerism Problem.

[BibT_eX]

[DOI]