Martin Skutella

Philipp Warode

Proceedings of the Integer Programming and Combinatorial Optimization, 2025

Complexity of Injectivity and Verification of ReLU Neural Networks (Extended Abstract).

[BibT_eX]

[DOI]

Vincent Froese

Moritz Grillo

Proceedings of the Thirty Eighth Annual Conference on Learning Theory, 2025

Open Problem: Fixed-Parameter Tractability of Zonotope Problems.

[BibT_eX]

[DOI]

Proceedings of the Thirty Eighth Annual Conference on Learning Theory, 2025

2024

Complexity of Deciding Injectivity and Surjectivity of ReLU Neural Networks.

[BibT_eX]

[DOI]

Vincent Froese

Moritz Grillo

CoRR, 2024

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

Reduction of Potential-Based Flow Networks.

[BibT_eX]

[DOI]

Math. Oper. Res., 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

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

Towards Lower Bounds on the Depth of ReLU Neural Networks.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

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

[BibT_eX]

[DOI]

Christoph Hertrich

Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 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

Single Source Unsplittable Flows with Arc-Wise Lower and Upper Bounds.

[BibT_eX]

[DOI]

Sarah Morell

Proceedings of the Integer Programming and Combinatorial Optimization, 2020

Packing Under Convex Quadratic Constraints.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2020

2019

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

[BibT_eX]

[DOI]

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

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

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

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

[BibT_eX]

[DOI]

Dagstuhl Reports, 2015

A note on the ring loading problem.

[BibT_eX]

[DOI]

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

Robust randomized matchings.

[BibT_eX]

[DOI]

Jannik Matuschke

José A. Soto

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

The Simplex Algorithm is NP-mighty.

[BibT_eX]

[DOI]

Yann Disser

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

Randomization Helps Computing a Minimum Spanning Tree under Uncertainty.

[BibT_eX]

[DOI]

Nicole Megow

Julie Meißner

Proceedings of the Algorithms - ESA 2015, 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

Stochastic Scheduling on Unrelated Machines.

[BibT_eX]

[DOI]

Maxim Sviridenko

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

Paths to Stable Allocations.

[BibT_eX]

[DOI]

Ágnes Cseh

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

Graph Orientation and Flows over Time.

[BibT_eX]

[DOI]

Ashwin Arulselvan

Proceedings of the Algorithms and Computation - 25th International Symposium, 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 Recourse for Online MST and TSP.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 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

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

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

Earliest Arrival Flows in Networks with Multiple Sinks.

[BibT_eX]

[DOI]

Melanie Schmidt

Electron. Notes Discret. Math., 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

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

Scheduling periodic tasks in a hard real-time environment.

[BibT_eX]

[DOI]

Proceedings of the Scheduling, 14.02. - 19.02.2010, 2010

2009

Single-source k-splittable min-cost flows.

[BibT_eX]

[DOI]

Fernanda Salazar

Oper. Res. Lett., 2009

Earliest Arrival Flows with Multiple Sources.

[BibT_eX]

[DOI]

Nadine Baumann

Math. Oper. Res., 2009

Packet Routing: Complexity and Algorithms.

[BibT_eX]

[DOI]

Britta Peis

Andreas Wiese

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

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

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory, Second International Symposium, 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

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

[BibT_eX]

[DOI]

José R. Correa

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

Computing minimum cuts by randomized search heuristics.

[BibT_eX]

[DOI]

Frank Neumann

Joachim Reichel

Proceedings of the Genetic and Evolutionary Computation Conference, 2008

Flows with Unit Path Capacities and Related Packing and Covering Problems.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Optimization and Applications, 2008

An Introduction to Network Flows over Time.

[BibT_eX]

[DOI]

Proceedings of the Research Trends in Combinatorial Optimization, 2008

2007

Quickest Flows Over Time.

[BibT_eX]

[DOI]

Lisa Fleischer

SIAM J. Comput., 2007

Evolutionary algorithms and matroid optimization problems.

[BibT_eX]

[DOI]

Joachim Reichel

Proceedings of the Genetic and Evolutionary Computation Conference, 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

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

Multiline Addressing by Network Flow.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2006

Latency Constrained Aggregation in Sensor Networks.

[BibT_eX]

[DOI]

Luca Becchetti

Peter Korteweg

Leen Stougie

Andrea Vitaletti

Proceedings of the Algorithms, 2006

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

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

New Approaches for Virtual Private Network Design.

[BibT_eX]

[DOI]

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

Online Scheduling with Bounded Migration.

[BibT_eX]

[DOI]

Peter Sanders

Naveen Sivadasan

Proceedings of the Algorithms for Optimization with Incomplete Information, 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

Flows on Few Paths: Algorithms and Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2004

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

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

[BibT_eX]

[DOI]

Alexander Hall

Katharina Langkau

Proceedings of the Approximation, 2003

Multicommodity Flows over Time: Efficient Algorithms and Complexity.

[BibT_eX]

[DOI]

Alexander Hall

Steffen Hippler

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 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

Flows over time with load-dependent transit times.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

On the k-Splittable Flow Problem.

[BibT_eX]

[DOI]

Georg Baier

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

Cooperative facility location games.

[BibT_eX]

[DOI]

Michel X. Goemans

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

Approximating the single source unsplittable min-cost flow problem.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Preemptive Scheduling with Rejection.

[BibT_eX]

[DOI]

Han Hoogeveen

Proceedings of the 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

Semidefinite Relaxations for Parallel Machine Scheduling.

[BibT_eX]

[DOI]

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

1997

Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem.

[BibT_eX]

[DOI]

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 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