Nicole Megow

Vijayaragunathan Ramamoorthi

CoRR, 2024

Accelerating Matroid Optimization through Fast Imprecise Oracles.

[BibT_eX]

[DOI]

CoRR, 2024

Santa Claus meets Makespan and Matroids: Algorithms and Reductions.

[BibT_eX]

[DOI]

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

Fast Combinatorial Algorithms for Efficient Sortation.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2024

Solution Discovery via Reconfiguration for Problems in P.

[BibT_eX]

[DOI]

Daniel Schmand

Sebastian Siebertz

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Competitive Query Minimization for Stable Matching with One-Sided Uncertainty.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2024

2023

Speed-robust scheduling: sand, bricks, and rocks.

[BibT_eX]

[DOI]

Math. Program., February, 2023

Scheduling (Dagstuhl Seminar 23061).

[BibT_eX]

[DOI]

Dagstuhl Reports, February, 2023

Online Throughput Maximization on Unrelated Machines: Commitment is No Burden.

[BibT_eX]

[DOI]

Franziska Eberle

ACM Trans. Algorithms, January, 2023

Recoverable Robust Optimization with Commitment.

[BibT_eX]

[DOI]

CoRR, 2023

Set Selection Under Explorable Stochastic Uncertainty via Covering Techniques.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2023

Configuration Balancing for Stochastic Requests.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2023

Sorting and Hypergraph Orientation under Uncertainty with Predictions.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary.

[BibT_eX]

[DOI]

Martin Rapp

Proceedings of the International Conference on Machine Learning, 2023

Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints.

[BibT_eX]

[DOI]

Alexandra Anna Lassota

Proceedings of the International Conference on Machine Learning, 2023

Matching Augmentation via Simultaneous Contractions.

[BibT_eX]

[DOI]

Mohit Garg

Felix Hommelsheim

Vijayaragunathan Ramamoorthi

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

On Solution Discovery via Reconfiguration.

[BibT_eX]

[DOI]

Frances A. Rosamond

Daniel Schmand

Sebastian Siebertz

Proceedings of the ECAI 2023 - 26th European Conference on Artificial Intelligence, September 30 - October 4, 2023, Kraków, Poland, 2023

2022

On Hop-Constrained Steiner Trees in Tree-Like Metrics.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2022

Throughput scheduling with equal additive laxity.

[BibT_eX]

[DOI]

Martin Böhm

Oper. Res. Lett., 2022

Online load balancing with general reassignment cost.

[BibT_eX]

[DOI]

Sebastian Berndt

Franziska Eberle

Oper. Res. Lett., 2022

Non-Clairvoyant Scheduling with Predictions Revisited.

[BibT_eX]

[DOI]

CoRR, 2022

Permutation Predictions for Non-Clairvoyant Scheduling.

[BibT_eX]

[DOI]

Proceedings of the SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11, 2022

A Universal Error Measure for Input Predictions Applied to Online Graph Problems.

[BibT_eX]

[DOI]

Giulia Bernardini

Leen Stougie

Michelle Sweering

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Double Coverage with Machine-Learned Advice.

[BibT_eX]

[DOI]

Bertrand Simon

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty.

[BibT_eX]

[DOI]

Thomas Erlebach

Murilo Santos de Lima

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

Robustification of Online Graph Exploration Methods.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

2021

Preface.

[BibT_eX]

[DOI]

Evripidis Bampis

Theory Comput. Syst., 2021

Optimal algorithms for scheduling under time-of-use tariffs.

[BibT_eX]

[DOI]

Ann. Oper. Res., 2021

Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time.

[BibT_eX]

[DOI]

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty.

[BibT_eX]

[DOI]

Evripidis Bampis

Christoph Dürr

Thomas Erlebach

Murilo Santos de Lima

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

2020

A general framework for handling commitment in online throughput maximization.

[BibT_eX]

[DOI]

Math. Program., 2020

Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments.

[BibT_eX]

[DOI]

Jacob Focke

Julie Meißner

ACM J. Exp. Algorithmics, 2020

Scheduling (Dagstuhl Seminar 20081).

[BibT_eX]

[DOI]

David B. Shmoys

Ola Svensson

Dagstuhl Reports, 2020

Untrusted Predictions Improve Trustable Query Policies.

[BibT_eX]

[DOI]

CoRR, 2020

Speed-Robust Scheduling.

[BibT_eX]

[DOI]

CoRR, 2020

Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time.

[BibT_eX]

[DOI]

CoRR, 2020

Online Minimum Cost Matching on the Line with Recourse.

[BibT_eX]

[DOI]

Lukas Nölke

CoRR, 2020

An Adversarial Model for Scheduling with Testing.

[BibT_eX]

[DOI]

Algorithmica, 2020

Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics.

[BibT_eX]

[DOI]

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems.

[BibT_eX]

[DOI]

Proceedings of the 2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2020

Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice.

[BibT_eX]

[DOI]

Proceedings of the Workshop on Next Generation Real-Time Embedded Systems, 2020

Optimally Handling Commitment Issues in Online Throughput Maximization.

[BibT_eX]

[DOI]

Franziska Eberle

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Online Minimum Cost Matching with Recourse on the Line.

[BibT_eX]

[DOI]

Lukas Nölke

Proceedings of the Approximation, 2020

2019

Scheduling maintenance jobs in networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2019

On index policies for stochastic minsum scheduling.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2019

Scheduling Self-Suspending Tasks: New and Old Results (Artifact).

[BibT_eX]

[DOI]

Georg von der Brüggen

Dagstuhl Artifacts Ser., 2019

Scheduling Self-Suspending Tasks: New and Old Results.

[BibT_eX]

[DOI]

Georg von der Brüggen

Proceedings of the 31st Euromicro Conference on Real-Time Systems, 2019

2018

Dual Techniques for Scheduling on a Machine with Varying Speed.

[BibT_eX]

[DOI]

José Verschae

SIAM J. Discret. Math., 2018

An O(log m)-Competitive Algorithm for Online Machine Minimization.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

Scheduling (Dagstuhl Seminar 18101).

[BibT_eX]

[DOI]

Magnús M. Halldórsson

Clifford Stein

Dagstuhl Reports, 2018

Scheduling with Explorable Uncertainty.

[BibT_eX]

[DOI]

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017

Packing a Knapsack of Unknown Capacity.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2017

Randomization Helps Computing a Minimum Spanning Tree under Uncertainty.

[BibT_eX]

[DOI]

Julie Meißner

Martin Skutella

SIAM J. Comput., 2017

2016

Universal Sequencing on an Unreliable Machine.

[BibT_eX]

[DOI]

Julián Mestre

Encyclopedia of Algorithms, 2016

Special Issue: APPROX-RANDOM 2015: Guest Editors' Foreword.

[BibT_eX]

[DOI]

Mary Wootters

Theory Comput., 2016

A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

The Power of Recourse for Online MST and TSP.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Scheduling (Dagstuhl Seminar 16081).

[BibT_eX]

[DOI]

Nikhil Bansal

Clifford Stein

Dagstuhl Reports, 2016

The Power of Migration in Online Machine Minimization.

[BibT_eX]

[DOI]

Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, 2016

An O(log <i>m</i>)-Competitive Algorithm for Online Machine Minimization.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

Clique partitioning with value-monotone submodular cost.

[BibT_eX]

[DOI]

José R. Correa

Discret. Optim., 2015

An O(m^2 log m)-Competitive Algorithm for Online Machine Minimization.

[BibT_eX]

[DOI]

CoRR, 2015

Optimal Algorithms and a PTAS for Cost-Aware Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Stochastic and Robust Scheduling in the Cloud.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

Robustness and Approximation for Universal Sequencing.

[BibT_eX]

[DOI]

Proceedings of the Gems of Combinatorial Optimization and Graph Algorithms, 2015

2014

A Tight 2-Approximation for Preemptive Stochastic Scheduling.

[BibT_eX]

[DOI]

Math. Oper. Res., 2014

Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width.

[BibT_eX]

[DOI]

Elisabeth Günther

Felix G. König

J. Comb. Optim., 2014

New Results on Online Resource Minimization.

[BibT_eX]

[DOI]

CoRR, 2014

2013

Competitive-Ratio Approximation Schemes for Minimizing the Makespan in the Online-List Model

[BibT_eX]

[DOI]

Andreas Wiese

CoRR, 2013

A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Polynomial-Time Exact Schedulability Tests for Harmonic Real-Time Tasks.

[BibT_eX]

[DOI]

Vincenzo Bonifaci

Andreas Wiese

Proceedings of the IEEE 34th Real-Time Systems Symposium, 2013

Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints.

[BibT_eX]

[DOI]

Julián Mestre

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

Online graph exploration: New results on old and new algorithms.

[BibT_eX]

[DOI]

Kurt Mehlhorn

Pascal Schweitzer

Theor. Comput. Sci., 2012

A note on sorting buffers offline.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2012

Scheduling Real-Time Mixed-Criticality Jobs.

[BibT_eX]

[DOI]

Leen Stougie

IEEE Trans. Computers, 2012

Algorithms and complexity for periodic real-time scheduling.

[BibT_eX]

[DOI]

Vincenzo Bonifaci

Ho-Leung Chan

ACM Trans. Algorithms, 2012

Universal Sequencing on an Unreliable Machine.

[BibT_eX]

[DOI]

Leah Epstein

Asaf Levin

SIAM J. Comput., 2012

On Eulerian extensions and their application to no-wait flowshop scheduling.

[BibT_eX]

[DOI]

Wiebke Höhn

Tobias Jacobs

J. Sched., 2012

Scheduling on a machine with varying speed: Minimizing cost and energy via dual schedules

[BibT_eX]

[DOI]

José Verschae

CoRR, 2012

2011

Decision Support and Optimization in Shutdown and Turnaround Scheduling.

[BibT_eX]

[DOI]

Rolf H. Möhring

Jens Schulz

INFORMS J. Comput., 2011

Meeting Deadlines: How Much Speed Suffices?

[BibT_eX]

[DOI]

S. Anand

Naveen Garg

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

The Sorting Buffer Problem is NP-hard

[BibT_eX]

[DOI]

CoRR, 2010

Universal Sequencing on a Single Machine.

[BibT_eX]

[DOI]

Leah Epstein

Asaf Levin

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

2009

Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width.

[BibT_eX]

[DOI]

Elisabeth Günther

Felix G. König

Proceedings of the Approximation and Online Algorithms, 7th International Workshop, 2009

Cardinality Constrained Graph Partitioning into Cliques with Submodular Costs.

[BibT_eX]

[DOI]

Proceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2009

2008

Optimizing the landside operation of a container terminal.

[BibT_eX]

[DOI]

OR Spectr., 2008

2007

Coping with Incomplete Information in Scheduling - Stochastic and Online Models.

[BibT_eX]

[DOI]

Proceedings of the Operations Research, 2007

2006

How to whack moles.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2006

Models and Algorithms for Stochastic Online Scheduling.

[BibT_eX]

[DOI]

Marc Uetz

Math. Oper. Res., 2006

Approximation in Preemptive Stochastic Online Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2006

2005

The Online Target Date Assignment Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms, Third International Workshop, 2005

2004

On-line scheduling to minimize average completion time revisited.

[BibT_eX]

[DOI]

Andreas S. Schulz

Oper. Res. Lett., 2004

Stochastic Online Scheduling on Parallel Machines.

[BibT_eX]

[DOI]

Marc Uetz

Proceedings of the Approximation and Online Algorithms, Second International Workshop, 2004

2003

Scheduling to Minimize Average Completion Time Revisited: Deterministic On-Line Algorithms.

[BibT_eX]

[DOI]

Andreas S. Schulz

Proceedings of the Approximation and Online Algorithms, First International Workshop, 2003

How to Whack Moles.

[BibT_eX]

[DOI]

Sven Oliver Krumke