Martin Skutella

CoRR, 2024

2023

Towards Lower Bounds on the Depth of ReLU Neural Networks.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., June, 2023

A note on the quickest minimum cost transshipment problem.

[BibT_eX]

[DOI]

Oper. Res. Lett., May, 2023

On the robustness of potential-based flow networks.

[BibT_eX]

[DOI]

Math. Program., January, 2023

Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size.

[BibT_eX]

[DOI]

Christoph Hertrich

INFORMS J. Comput., 2023

An Introduction to Transshipments Over Time.

[BibT_eX]

[DOI]

CoRR, 2023

Total Completion Time Scheduling Under Scenarios.

[BibT_eX]

[DOI]

Leen Stougie

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

2022

Single source unsplittable flows with arc-wise lower and upper bounds.

[BibT_eX]

[DOI]

Sarah Morell

Math. Program., 2022

Packing under convex quadratic constraints.

[BibT_eX]

[DOI]

Math. Program., 2022

A Faster Algorithm for Quickest Transshipments via an Extended Discrete Newton Method.

[BibT_eX]

[DOI]

Miriam Schlöter

Khai Van Tran

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

Competitive Strategies for Symmetric Rendezvous on the Line.

[BibT_eX]

[DOI]

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

2021

A simple proof of the Moore-Hodgson Algorithm for minimizing the number of late jobs.

[BibT_eX]

[DOI]

Joseph Cheriyan

R. Ravi

Oper. Res. Lett., 2021

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

2019

The Simplex Algorithm Is NP-Mighty.

[BibT_eX]

[DOI]

Yann Disser

ACM Trans. Algorithms, 2019

Algorithmic results for potential-based flows: Easy and hard cases.

[BibT_eX]

[DOI]

Networks, 2019

Paths to stable allocations.

[BibT_eX]

[DOI]

Ágnes Cseh

Int. J. Game Theory, 2019

2018

On the complexity of instationary gas flows.

[BibT_eX]

[DOI]

Marc E. Pfetsch

Oper. Res. Lett., 2018

WAOA 2015 Special Issue on TOCS.

[BibT_eX]

[DOI]

Laura Sanità

Theory Comput. Syst., 2018

Preface.

[BibT_eX]

[DOI]

Quentin Louveaux

Math. Program., 2018

Robust Randomized Matchings.

[BibT_eX]

[DOI]

Jannik Matuschke

José A. Soto

Math. Oper. Res., 2018

Generalizing the Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling.

[BibT_eX]

[DOI]

Sven Jäger

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

Multi-Source Multi-Sink Nash Flows over Time.

[BibT_eX]

[DOI]

Leon Sering

Proceedings of the 18th Workshop on Algorithmic Approaches for Transportation Modelling, 2018

A Fully Polynomial Time Approximation Scheme for Packing While Traveling.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects of Cloud Computing - 4th International Symposium, 2018

2017

Randomization Helps Computing a Minimum Spanning Tree under Uncertainty.

[BibT_eX]

[DOI]

Nicole Megow

Julie Meißner

SIAM J. Comput., 2017

Protection of flows under targeted attacks.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2017

Fast and Memory-Efficient Algorithms for Evacuation Problems.

[BibT_eX]

[DOI]

Miriam Schlöter

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

2016

A Note on the Ring Loading Problem.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2016

The Power of Recourse for Online MST and TSP.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2016

Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures.

[BibT_eX]

[DOI]

Math. Oper. Res., 2016

Unrelated Machine Scheduling with Stochastic Processing Times.

[BibT_eX]

[DOI]

Maxim Sviridenko

Math. Oper. Res., 2016

PolySCIP.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Software - ICMS 2016, 2016

2015

A tight bound on the speed-up through storage for quickest multi-commodity flows.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2015

An incremental algorithm for the uncapacitated facility location problem.

[BibT_eX]

[DOI]

Ashwin Arulselvan

Olaf Maurer

Networks, 2015

Graph orientation and flows over time.

[BibT_eX]

[DOI]

Ashwin Arulselvan

Networks, 2015

Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 15412).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2015

Node-Balancing by Edge-Increments.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2015, 2015

Convex Quadratic Programming in Scheduling.

[BibT_eX]

[DOI]

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

2014

Earliest arrival flows in networks with multiple sinks.

[BibT_eX]

[DOI]

Melanie Schmidt

Discret. Appl. Math., 2014

Stochastic Scheduling on Unrelated Machines.

[BibT_eX]

[DOI]

Maxim Sviridenko

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

2013

In defense of the Simplex Algorithm's worst-case behavior.

[BibT_eX]

[DOI]

Yann Disser

CoRR, 2013

Stable Flows over Time.

[BibT_eX]

[DOI]

Ágnes Cseh

Jannik Matuschke

Algorithms, 2013

Algorithms and Linear Programming Relaxations for Scheduling Unrelated Parallel Machines.

[BibT_eX]

[DOI]

Proceedings of the Experimental Algorithms, 12th International Symposium, 2013

Task assignment, sequencing and path-planning in robotic welding cells.

[BibT_eX]

[DOI]

Proceedings of the 18th International Conference on Methods & Models in Automation & Robotics, 2013

2012

Universal Sequencing on an Unreliable Machine.

[BibT_eX]

[DOI]

Leah Epstein

Asaf Levin

SIAM J. Comput., 2012

Special issue of the ISMP 2012 in Berlin.

[BibT_eX]

[DOI]

Michael Hintermüller

Math. Program., 2012

The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders.

[BibT_eX]

[DOI]

José R. Correa

Math. Oper. Res., 2012

Maximum Multicommodity Flows over Time without Intermediate Storage.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2012, 2012

Flows over Time with Negative Transit Times and Arc Release Dates.

[BibT_eX]

Sandro Bosio

Jan-Philipp W. Kappmeier

Jannik Matuschke

Britta Peis

Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2012

2011

Preface.

[BibT_eX]

[DOI]

Christos Kaklamanis

Theor. Comput. Sci., 2011

A note on the generalized min-sum set cover problem.

[BibT_eX]

[DOI]

David P. Williamson

Oper. Res. Lett., 2011

Nash Equilibria and the Price of Anarchy for Flows over Time.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

Continuous and discrete flows over time - A general model based on measure theory.

[BibT_eX]

[DOI]

Ebrahim Nasrabadi

Math. Methods Oper. Res., 2011

Real-time Avionics Optimization.

[BibT_eX]

[DOI]

it Inf. Technol., 2011

Computing Minimum Cuts by Randomized Search Heuristics.

[BibT_eX]

[DOI]

Frank Neumann

Joachim Reichel

Algorithmica, 2011

Generalized Maximum Flows over Time.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 9th International Workshop, 2011

Minimum Spanning Trees - Sometimes Greed Pays Off.

[BibT_eX]

[DOI]

Katharina Skutella

Proceedings of the Algorithms Unplugged, 2011

2010

Length-bounded cuts and flows.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2010

On the dominant of the s-t-cut polytope: Vertices, facets, and adjacency.

[BibT_eX]

[DOI]

Alexia Weber

Math. Program., 2010

Evolutionary Algorithms and Matroid Optimization Problems.

[BibT_eX]

[DOI]

Joachim Reichel

Algorithmica, 2010

An FPTAS for Flows over Time with Aggregate Arc Capacities.

[BibT_eX]

[DOI]

Daniel Dressler

Proceedings of the Approximation and Online Algorithms - 8th International Workshop, 2010

Route Planning for Robot Systems.

[BibT_eX]

[DOI]

Wolfgang Welz

Proceedings of the Operations Research Proceedings 2010, 2010

Optimal Evacuation Solutions for Large-Scale Scenarios.

[BibT_eX]

[DOI]

Proceedings of the Operations Research Proceedings 2010, 2010

Packet Routing on the Grid.

[BibT_eX]

[DOI]

Britta Peis

Andreas Wiese

Proceedings of the LATIN 2010: Theoretical Informatics, 2010

Universal Sequencing on a Single Machine.

[BibT_eX]

[DOI]

Leah Epstein

Asaf Levin

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

Scheduling Periodic Tasks in a Hard Real-Time Environment.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

A Robust PTAS for Machine Covering and Packing.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2010

Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2010

2009

Latency-constrained aggregation in sensor networks.

[BibT_eX]

[DOI]

Luca Becchetti

ACM Trans. Algorithms, 2009

Single-source k-splittable min-cost flows.

[BibT_eX]

[DOI]

Fernanda Salazar

Oper. Res. Lett., 2009

Online Scheduling with Bounded Migration.

[BibT_eX]

[DOI]

Peter Sanders

Naveen Sivadasan

Math. Oper. Res., 2009

Earliest Arrival Flows with Multiple Sources.

[BibT_eX]

[DOI]

Nadine Baumann

Math. Oper. Res., 2009

Flows with unit path capacities and related packing and covering problems.

[BibT_eX]

[DOI]

J. Comb. Optim., 2009

Multiline Addressing by Network Flow.

[BibT_eX]

[DOI]

Algorithmica, 2009

Packet Routing: Complexity and Algorithms.

[BibT_eX]

[DOI]

Britta Peis

Andreas Wiese

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

On the size of weights in randomized search heuristics.

[BibT_eX]

[DOI]

Joachim Reichel

Proceedings of the Foundations of Genetic Algorithms, 2009

Traffic Networks and Flows over Time.

[BibT_eX]

[DOI]

Rolf H. Möhring

Proceedings of the Algorithmics of Large and Complex Networks - Design, 2009

A Robust PTAS for the Parallel Machine Covering Problem.

[BibT_eX]

[DOI]

Proceedings of the Models and Algorithms for Optimization in Logistics, 21.06., 2009

Real-Time Message Routing and Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

2008

Minimale aufspannende Bäume (Wenn das Naheliegende das Beste ist... ).

[BibT_eX]

[DOI]

Katharina Skutella

Proceedings of the Taschenbuch der Algorithmen, 2008

A short proof of the VPN Tree Routing Conjecture on ring networks.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2008

Maximum k -Splittable s , t -Flows.

[BibT_eX]

[DOI]

Ines Spenke

Theory Comput. Syst., 2008

An Introduction to Network Flows over Time.

[BibT_eX]

[DOI]

Proceedings of the Research Trends in Combinatorial Optimization, 2008

2007

Multicommodity flows over time: Efficient algorithms and complexity.

[BibT_eX]

[DOI]

Alexander Hall

Steffen Hippler

Theor. Comput. Sci., 2007

Quickest Flows Over Time.

[BibT_eX]

[DOI]

Lisa Fleischer

SIAM J. Comput., 2007

New Approaches for Virtual Private Network Design.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times.

[BibT_eX]

[DOI]

Alexander Hall

Katharina Langkau

Algorithmica, 2007

Convex Combinations of Single Source Unsplittable Flows.

[BibT_eX]

[DOI]

Fernanda Salazar

Proceedings of the Algorithms, 2007

2006

List Scheduling in Order of α-Points on a Single Machine.

[BibT_eX]

[DOI]

Proceedings of the Efficient Approximation and Online Algorithms, 2006

Flows on few paths: Algorithms and lower bounds.

[BibT_eX]

[DOI]

Networks, 2006

The Freeze-Tag Problem: How to Wake Up a Swarm ofRobots.

[BibT_eX]

[DOI]

Esther M. Arkin

Michael A. Bender

Sándor P. Fekete

Joseph S. B. Mitchell

Algorithmica, 2006

Length-Bounded Cuts and Flows.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Solving Evacuation Problems Efficiently--Earliest Arrival Flows with Multiple Sources.

[BibT_eX]

[DOI]

Nadine Baumann

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

Flows over Time with Load-Dependent Transit Times.

[BibT_eX]

[DOI]

SIAM J. Optim., 2005

Stochastic Machine Scheduling with Precedence Constraints.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

Approximating k-hop minimum-spanning trees.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2005

The k-Splittable Flow Problem.

[BibT_eX]

[DOI]

Georg Baier

Algorithmica, 2005

Approximation and Complexity of k-Splittable Flows.

[BibT_eX]

[DOI]

Ines Spenke

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

Length-Bounded and Dynamic k-Splittable Flows.

[BibT_eX]

[DOI]

Proceedings of the Operations Research Proceedings 2005, 2005

Computing earliest arrival flows with multiple sources.

[BibT_eX]

[DOI]

Nadine Baumann

Proceedings of the Algorithmic Aspects of Large and Complex Networks, 4.-9. September 2005, 2005

2004

Scheduling with AND/OR Precedence Constraints.

[BibT_eX]

[DOI]

Rolf H. Möhring

Frederik Stork

SIAM J. Comput., 2004

Cooperative facility location games.

[BibT_eX]

[DOI]

Michel X. Goemans

J. Algorithms, 2004

2003

Preemptive scheduling with rejection.

[BibT_eX]

[DOI]

Han Hoogeveen

Math. Program., 2003

The complexity of economic equilibria for house allocation markets.

[BibT_eX]

[DOI]

Sándor P. Fekete

Inf. Process. Lett., 2003

Minimum cost flows over time without intermediate storage.

[BibT_eX]

[DOI]

Lisa Fleischer

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

2002

Scheduling Unrelated Machines by Randomized Rounding.

[BibT_eX]

[DOI]

Andreas S. Schulz

SIAM J. Discret. Math., 2002

Single Machine Scheduling with Release Dates.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2002

Approximating the single source unsplittable min-cost flow problem.

[BibT_eX]

[DOI]

Math. Program., 2002

The freeze-tag problem: how to wake up a swarm of robots.

[BibT_eX]

[DOI]

Esther M. Arkin

Michael A. Bender

Sándor P. Fekete

Joseph S. B. Mitchell

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

The Quickest Multicommodity Flow Problem.

[BibT_eX]

[DOI]

Lisa Fleischer

Proceedings of the Integer Programming and Combinatorial Optimization, 2002

Time-Expanded Graphs for Flow-Dependent Transit Times.

[BibT_eX]

[DOI]

Katharina Langkau

Proceedings of the Algorithms, 2002

2001

Convex quadratic and semidefinite programming relaxations in scheduling.

[BibT_eX]

[DOI]

J. ACM, 2001

Scheduling precedence-constrained jobs with stochastic processing times on parallel machines.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

2000

A PTAS for Minimizing the Total Weighted Completion Time on Identical Parallel Machines.

[BibT_eX]

[DOI]

Math. Oper. Res., 2000

Forcing relations for AND/OR precedence constraints.

[BibT_eX]

[DOI]

Rolf H. Möhring

Frederik Stork

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999

A PTAS for Minimizing the Weighted Sum of Job Completion Times on Parallel Machines.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Convex Quadratic Programming Relaxations for Network Scheduling Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1999

1998

Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem.

[BibT_eX]

[DOI]

Math. Oper. Res., 1998

Semidefinite Relaxations for Parallel Machine Scheduling.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997

Random-Based Scheduling: New Approximations and LP Lower Bounds.

[BibT_eX]

[DOI]

Andreas S. Schulz

Proceedings of the Randomization and Approximation Techniques in Computer Science, 1997

Scheduling-LPs Bear Probabilities: Randomized Approximations for Min-Sum Criteria.

[BibT_eX]

[DOI]

Andreas S. Schulz

Proceedings of the Algorithms, 1997

Parallel Repetition of MIP(2, 1) Systems.

[BibT_eX]

[DOI]

Clemens Gröpl