Faculties
DE / EN

# Publications

• On the Robustness of Potential-Based Flow Networks (, , and )
Math. Program., .
DOI
• Combinatorial generation via permutation languages. III. Rectangulations ( and )
Discret. Comput. Geom., .
DOI
Extended abstract appeared in Proc. of SoCG 2021
• Improved Bounds for Stochastic Extensible Bin Packing under Distributional Assumptions ( and )
ISCO 2022 – Proc. 7th International Symposium on Combinatorial Optimization.
• On a Combinatorial Generation Problem of Knuth (, and )
SIAM J. Comput., 51(3):379-423, .
DOI
Extended abstract appeared in Proc. of SODA 2021
• Single source unsplittable flows with arc-wise lower and upper bounds ( and )
Math. Program., 192(1):477–496, .
DOI
Extended abstract appeared in Proc. of IPCO 2020
• Packing Under Convex Quadratic Constraints (, , and )
Math. Program., 192(1):361–386, .
DOI
Extended abstract appeared in Proc. of IPCO 2020
• PICOS: A Python interface to conic optimization solvers ( and )
J. Open Source Softw., 7(70):3915, .
DOI
• Using reinforcement learning to control traffic signals in a real-world scenario: An approach based on linear function approximation (, and )
IEEE Transactions on Intelligent Transportation Systems, 23(7):9126–9135, .
• The Effect of Speed Limits and Traffic Signal Control on Emissions (, and )
Procedia Computer Science, 201:568–573, .
• Efficient generation of elimination trees and graph associahedra (, and )
SODA 2022 – Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms, pp. 2128-2140.
DOI
• Competitive Algorithms for Symmetric Rendezvous on the Line (, , and )
SODA 2022 – Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms, pp. 329–347.
DOI
• A Faster Algorithm for Quickest Transshipments via an Extended Discrete Newton Method (, and )
SODA 2022 – Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms, pp. 90–102.
DOI
• Star Transposition Gray Codes for Multiset Permutations (, and )
STACS 2022 – Proc. 39th International Symposium on Theoretical Aspects of Computer Science, pp. 34:1–34:14.
DOI
• The Hamilton compression of highly symmetric graphs (, and )
MFCS 2022 – Proc. 47th International Symposium on Mathematical Foundations of Computer Science, pp. 54:1–54:14.
DOI
• All Your bases Are Belong to Us: Listing All Bases of a Matroid by Greedy Exchanges (, and )
FUN 2022 – Proc. 11th International Conference on Fun with Algorithms, pp. 22:1–22:28.
DOI
• Removing inessential points in $c-$ and $A-$optimal design ( and )
J. Stat. Plan. Inference, 213:233–252, .
DOI
• A simple proof of the Moore-Hodgson Algorithm for minimizing the number of late jobs (, and )
Oper. Res. Lett., 49(6):842–843, .
DOI
• Flows Over Time as Continuous Limits of Packet-Based Network Simulations (, , , , and )
Transportation Research Procedia, 52:123–130, .
DOI
• Reinforcement learning vs. rule-based adaptive traffic signal control: A Fourier basis linear function approximation for traffic signal control (, and )
AI Communications, 34(1):89–103, .
• Automated generation of traffic signals and lanes for MATSim based on OpenStreetMap ( and )
Procedia Computer Science, 184:745–752, .
• Towards Lower Bounds on the Depth of ReLU Neural Networks (, , and )
NeurIPS 2021 – Proc. 35th Conference on Neural Information Processing Systems, pp. 3336–3348.
• On a Combinatorial Generation Problem of Knuth (, and )
SODA 2021 – Proc. 32nd ACM-SIAM Symposium on Discrete Algorithms, pp. 735–743.
DOI
• Minimum-cost integer circulations in given homology classes (, and )
SODA 2021 – Proc. 32nd ACM-SIAM Symposium on Discrete Algorithms, pp. 2725–2739.
• Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size ( and )
AAAI 2021 – Proc. 35th AAAI Conference on Artificial Intelligence, pp. 7685–7693.
• Efficient Generation of Rectangulations via Permutation Languages ( and )
SoCG 2021 – Proc. 37th International Symposium on Computational Geometry, pp. 54:1–54:18.
DOI
• Restricted Adaptivity in Stochastic Scheduling ( and )
ESA 2021 – Proc. 29th European Symposium on Algorithms, pp. 79:1–79:14.
DOI
• Convergence of a Packet Routing Model to Flows Over Time (, and )
Proceedings of the 22nd ACM Conference on Economics and Computation, Association for Computing Machinery, pp. 797–816.
• Approximation in Deterministic and Stochastic Machine Scheduling ()
PhD thesis, TU Berlin, .
• Approximate and exact D-optimal designs for $2^k$ factorial experiments for Generalized Linear Models via SOCP ( and )
Stat. Pap., 61:2737–2767, .
DOI
• Single source unsplittable flows with arc-wise lower and upper bounds ( and )
IPCO 2020 – Proc. 21st Conference on Integer Programming and Combinatorial Optimization, pp. 294–306.
DOI
Full paper appeared in Math. Program. 2021
• Packing Under Convex Quadratic Constraints (, , and )
IPCO 2020 – Proc. 21st Conference on Integer Programming and Combinatorial Optimization, pp. 266–279.
DOI
Extended version appeared in Math. Program. 2021
• On the Two-Dimensional Knapsack Problem for Convex Polygons ( and )
ICALP 2020 – Proc. 47th International Colloquium on Automata, Languages and Programming, pp. 84:1–84:16.
DOI
• On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems (, , , and )
IPDPS 2020 – Proc. 34thIEEE International Parallel and Distributed Processing Symposium, pp. 1061–1070.
DOI
• A reinforcement learning approach with Fourier basis linear function approximation for traffic signal control (, and )
CEUR Workshop Proceedings, pp. 55–62.
[pdf]
• Nash Flows Over Time ()
PhD thesis, TU Berlin, .
• Some Aspects of Graph Sparsification in Theory and Practice ()
PhD thesis, TU Berlin, .
• The Simplex Algorithm is NP-Mighty ( and )
ACM Trans. Algorithms, 15(1):5:1–5:19, .
DOI
Extended abstract appeared in Proc. of SODA 2015
• Paths to stable allocations ( and )
Int. J. Game Theory, 48(3):835–862, .
DOI
• Algorithmic results for potential-based flows: Easy and hard cases (, , , and )
Networks, 73(3):306–324, .
DOI
• Maximizing the storage capacity of gas networks: a global MINLP approach (, , , , , , and )
Optim. Eng., 20:543–573, .
DOI
• An unexpected connection between Bayes $A-$optimal designs and the Group Lasso ( and )
Stat. Pap., 60(2):215–234, .
• Adaptive traffic signal control for real-world scenarios in agent-based transport simulations (, and )
Transportation Research Procedia, Elsevier BV, 37:481–488, .
• Optimization and simulation of fixed-time traffic signal control in real-world applications (, , and )
Procedia Computer Science, Elsevier BV, 151:826–833, .
DOI
• The Minimum Cost Query Problem on Matroids with Uncertainty Areas ( and )
ICALP 2019 – Proc. 46th International Colloquium on Automata, Languages and Programming, pp. 83:1–83:14.
DOI
• Effects of user adaption on traffic-responsive signal control in agent-based transport simulations ( and )
6th International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS), pp. 1–7.
• Multicriteria Linear Optimisation with Applications in Sustainable Manufacturing ()
PhD thesis, TU Berlin, .
• Robust Randomized Matchings (, and )
Math. Oper. Res., 43(2):675–692, .
DOI
Extended abstract appeared in Proc. of SODA 2015
• An algorithm based on Semidefinite Programming for finding minimax optimal designs (, and )
Comput. Stat. Data Anal., 119:99–117, .
DOI
• Robust allocation of operating rooms: A cutting plane approach to handle lognormal case durations (, , , , , and )
Eur. J. Oper. Res., 271(2):420–435, .
DOI
• The Cone of Flow Matrices: Approximation Hierarchies and Applications (, and )
Networks, 72(1):128–150, .
DOI
Extended abstract appeared in Proc. of INOC 2017
• On the complexity of instationary gas flows (, and )
Oper. Res. Lett., 46(3):286–290, .
DOI
• Implementing an adaptive traffic signal control algorithm in an agent-based transport simulation (, and )
Procedia Computer Science, Elsevier BV, 130:894–899, .
DOI
• Generalizing the Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling ( and )
STACS 2018 – Proc. 35th International Symposium on Theoretical Aspects of Computer Science, pp. 43:1–43:14.
DOI
• Multi-Source Multi-Sink Nash Flows over Time ( and )
ATMOS 2018 – Proc. 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, pp. 12:1–12:20.
DOI
• Diversity Maximization in Doubling Metrics (, and )
ISAAC 2018 – Proc. 29th International Symposium on Algorithms and Computation.
• A Fully Polynomial Time Approximation Scheme for Packing While Traveling (, , , and )
ALGOCLOUD 2018 – Proc. 4th International Symposium on Algorithmic Aspects of Cloud Computing, pp. 59–72.
DOI
• Approximation Hierarchies for the Cone of Flow Matrices (, and )
INOC 2017 – Proc. 8th International Network Optimization Conference, pp. 275 – 284.
DOI
• The Price of Fixed Assignments in Stochastic Extensible Bin Packing (, and )
WAOA 2018 – Proc. 16th Workshop on Approximation and Online Algorithms, pp. 327–347.
DOI
• Uncertainty Exploration : Algorithms, Competitive Analysis, and Computational Experiments ()
PhD thesis, TU Berlin, .
• Flows Over Time and Submodular Function Minimization ()
PhD thesis, TU Berlin, .
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty (, and )
SIAM J. Comput., 46(4):1217–1240, .
DOI
Extended abstract appeared in Proc. of ESA 2015
• Optimal duty rostering for toll enforcement inspectors (, , and )
Ann. Oper. Res., 252(2):383–406, .
DOI
• Protection of flows under targeted attacks (, , , and )
Oper. Res. Lett., 45(1):53–59, .
DOI
• The structure of user equilibria: Dynamic coevolutionary simulations vs. cyclically expanded networks ( and )
Procedia Computer Science, 109:648–655, .
• Fast and Memory-Efficient Algorithms for Evacuation Problems ( and )
SODA 2017 – Proc. 28th ACM-SIAM Symposium on Discrete Algorithms, pp. 821–840.
DOI
• Towards a robust and wide-area traffic signal control for inner-city areas ( and )
2017 5th IEEE International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS), pp. 804–809.
• Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures ( and )
Math. Oper. Res., 41(3):991–1021, .
DOI
• The Power of Recourse for Online MST and TSP (, , and )
SIAM J. Comput., 45(3):859–880, .
DOI
Extended abstract appeared in Proc. of ICALP 2012
• Unrelated Machine Scheduling with Stochastic Processing Times (, and )
Math. Oper. Res., 41(3):851–864, .
DOI
Extended abstract appeared in Proc. of STACS 2014
• A Note on the Ring Loading Problem ()
SIAM J. Discret. Math., 30(1):327–342, .
DOI
Extended abstract appeared in Proc. of SODA 2015
• A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective ()
Oper. Res. Lett., 44(5):676–679, .
DOI
• Braess's paradox in an agent-based transport model ( and )
Procedia Computer Science, 83:946–951, .
• PolySCIP (, , and )
ICMS 2016 – Proc. 5th International Congress on Mathematical Software, pp. 259–264.
DOI
• IPCO 2016 – Proc. 18th Conference on Integer Programming and Combinatorial Optimization (Quentin Louveaux, Martin Skutella, eds.), .
DOI
• Complexity and Algorithms in Matching Problems Under Preferences ()
PhD thesis, TU Berlin, .
[pdf]
• A tight bound on the speed-up through storage for quickest multi-commodity flows ( and )
Oper. Res. Lett., 43(1):93–95, .
DOI
• An incremental algorithm for the uncapacitated facility location problem (, and )
Networks, 65(4):306–311, .
DOI
• Graph orientation and flows over time (, and )
Networks, 66(3):196–209, .
DOI
Extended abstract appeared in Proc. of ISAAC 2014
• A note on the ring loading problem ()
SODA 2015 – Proc. 26th ACM-SIAM Symposium on Discrete Algorithms, pp. 37–46.
DOI
Full paper appeared in SIAM J. Discret. Math. 2016
• The Simplex Algorithm is NP-Mighty ( and )
SODA 2015 – Proc. 26th ACM-SIAM Symposium on Discrete Algorithms, pp. 858–872.
DOI
Full paper appeared in ACM Trans. Algorithms 2019
• Robust randomized matchings (, and )
SODA 2015 – Proc. 26th ACM-SIAM Symposium on Discrete Algorithms, pp. 1904–1915.
DOI
Full paper appeared in SIAM J. Comput. 2018
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty (, and )
ESA 2015 – Proc. 23rd European Symposium on Algorithms, pp. 878–890.
DOI
Full paper appeared in SIAM J. Comput. 2017
• Node-Balancing by Edge-Increments (, , and )
ESA 2015 – Proc. 23rd European Symposium on Algorithms, pp. 450–458.
DOI
• Convex Quadratic Programming in Scheduling ()
Chapter in Gems of Combinatorial Optimization and Graph Algorithms, .
DOI
• WAOA 2015 – Proc. 13th Workshop on Approximation and Online Algorithms (Laura Sanità, Martin Skutella, eds.), .
DOI
• Gems of Combinatorial Optimization and Graph Algorithms (Andreas S. Schulz, Martin Skutella, Sebastian Stiller, Dorothea Wagner, eds.), .
DOI
• Network Design with Facility Location ()
PhD thesis, TU Berlin, .
[pdf]
• Generalizations of Flows over Time with Applications in Evacuation Optimization ()
PhD thesis, TU Berlin, .
[pdf]
• Earliest arrival flows in networks with multiple sinks ( and )
Discret. Appl. Math., 164:320–327, .
DOI
• Stochastic Scheduling on Unrelated Machines (, and )
STACS 2014 – Proc. 31st International Symposium on Theoretical Aspects of Computer Science, pp. 639–650.
DOI
Full paper appeared in Math. Oper. Res. 2016
• Paths to Stable Allocations ( and )
SAGT 2014 – Proc. 7th International Symposium on Algorithmic Game Theory, pp. 61–73.
DOI
Full paper appeared in Int. J. Game Theory 2019
• Graph Orientation and Flows over Time (, and )
ISAAC 2014 – Proc. 25th International Symposium on Algorithms and Computation, pp. 741–752.
DOI
Full paper appeared in Networks 2015
• Approximation Algorithms for Complex Network Flow Over Time Problems ()
PhD thesis, TU Berlin, .
[pdf]
• Robot Tour Planning with High Determination Costs ()
PhD thesis, TU Berlin, .
[pdf]
• Stable Flows over Time (, and )
Algorithms, 6(3):532–545, .
DOI
• Algorithms and Linear Programming Relaxations for Scheduling Unrelated Parallel Machines ()
SEA 2013 – Proc. 12th International Symposium on Experimental Algorithms, pp. 1–3.
DOI
• Task assignment, sequencing and path-planning in robotic welding cells (, , , and )
MMAR 2013 – Proc. 18th International Conference on Methods and Models in Automation and Robotics, pp. 252–257.
DOI
• Network Flows and Network Design in Theory and Practice ()
PhD thesis, TU Berlin, .
[pdf]
• Benefits of Sexual Reproduction in Evolutionary Computation ()
PhD thesis, TU Berlin, .
[pdf]
• Universal Sequencing on an Unreliable Machine (, , , , , and )
SIAM J. Comput., 41(3):565–586, .
DOI
Extended abstract appeared in Proc. of IPCO 2010
• The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders (, and )
Math. Oper. Res., 37(2):379–398, .
DOI
Extended abstract appeared in Proc. of APPROX 2009
• The Power of Recourse for Online MST and TSP (, , and )
ICALP 2012 – Proc. 39th International Colloquium on Automata, Languages and Programming, pp. 689–700.
DOI
Full paper appeared in SIAM J. Comput. 2016
• Maximum Multicommodity Flows over Time without Intermediate Storage ( and )
ESA 2012 – Proc. 20th European Symposium on Algorithms, pp. 539–550.
DOI
• Flows over Time with Negative Transit Times and Arc Release Dates (, , , and )
CTW 2012 – Proc. 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp. 30–33.
• Routing Games over Time ()
PhD thesis, TU Berlin, .
[pdf]
• The Power of Recourse in Online Optimization ()
PhD thesis, TU Berlin, .
• Network Flow Problems Arising From Evacuation Planning ()
PhD thesis, TU Berlin, .
[pdf]
• Computing Minimum Cuts by Randomized Search Heuristics (, and )
Algorithmica, 59(3):323–342, .
DOI
Extended abstract appeared in Proc. of GECCO 2008
• A note on the generalized min-sum set cover problem ( and )
Oper. Res. Lett., 39(6):433–436, .
DOI
• Continuous and discrete flows over time - A general model based on measure theory (, and )
Math. Methods Oper. Res., 73(3):301–337, .
DOI
• Nash Equilibria and the Price of Anarchy for Flows over Time ( and )
Theory Comput. Syst., 49(1):71–97, .
DOI
Extended abstract appeared in Proc. of SAGT 2009
• Real-time Avionics Optimization (, , , and )
it – Inf. Technol., 53(6):274–279, .
DOI
• Generalized Maximum Flows over Time ( and )
WAOA 2011 – Proc. 9th Workshop on Approximation and Online Algorithms, pp. 247–260.
DOI
• Minimum Spanning Trees – Sometimes Greed Pays Off ( and )
Chapter in Algorithms Unplugged, .
DOI
• Packet Routing and Scheduling ()
PhD thesis, TU Berlin, .
• On the dominant of the $s$-$t$-cut polytope: Vertices, facets, and adjacency ( and )
Math. Program., 124(1-2):441–454, .
DOI
• Length-bounded cuts and flows (, , , , , , and )
ACM Trans. Algorithms, 7(1):4:1–4:27, .
DOI
Extended abstract appeared in Proc. of ICALP 2006
• Evolutionary Algorithms and Matroid Optimization Problems ( and )
Algorithmica, 57(1):187–206, .
DOI
Extended abstract appeared in Proc. of GECCO 2007
• Earliest Arrival Flows in Networks with Multiple Sinks ( and )
Electron. Notes Discret. Math., 36:607–614, .
DOI
• Universal Sequencing on a Single Machine (, , , , , and )
IPCO 2010 – Proc. 14th Conference on Integer Programming and Combinatorial Optimization, pp. 230–243.
DOI
Full paper appeared in SIAM J. Comput. 2012
• Scheduling Periodic Tasks in a Hard Real-Time Environment (, , , , and )
ICALP 2010 – Proc. 37th International Colloquium on Automata, Languages and Programming, pp. 299–311.
DOI
• A Robust PTAS for Machine Covering and Packing ( and )
ESA 2010 – Proc. 18th European Symposium on Algorithms, pp. 36–47.
DOI
• Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods (, , , , , , and )
ESA 2010 – Proc. 18th European Symposium on Algorithms, pp. 11–22.
DOI
• An FPTAS for Flows over Time with Aggregate Arc Capacities ( and )
WAOA 2010 – Proc. 8th Workshop on Approximation and Online Algorithms, pp. 106–117.
DOI
• Packet Routing on the Grid (, and )
LATIN 2010 – Proc. 9th Latin American Symposium on Theoretical Informatics, pp. 120–130.
DOI
• Route Planning for Robot Systems ( and )
OR 2010 – Proc. International Conference of the German Operations Research Society, pp. 307–312.
DOI
• Optimal Evacuation Solutions for Large-Scale Scenarios (, , , and )
OR 2010 – Proc. International Conference of the German Operations Research Society.
DOI
• Earliest Arrival Flows with Multiple Sources ( and )
Math. Oper. Res., 34(2):499–512, .
DOI
Extended abstract appeared in Proc. of FOCS 2006
• Online Scheduling with Bounded Migration (, and )
Math. Oper. Res., 34(2):481–498, .
DOI
Extended abstract appeared in Proc. of ICALP 2004
• Latency-constrained aggregation in sensor networks (, , , , and )
ACM Trans. Algorithms, 6(1):13:1–13:20, .
DOI
Extended abstract appeared in Proc. of ESA 2006
• Flows with unit path capacities and related packing and covering problems ( and )
J. Comb. Optim., 18(3):272–293, .
DOI
Extended abstract appeared in Proc. of COCOA 2008
• Multiline Addressing by Network Flow (, , and )
Algorithmica, 53(4):583–596, .
DOI
• Single-source $k$-splittable min-cost flows ( and )
Oper. Res. Lett., 37(2):71–74, .
DOI
• Real-Time Message Routing and Scheduling (, , and )
APPROX 2009 – Proc. 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 217–230.
DOI
• The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders (, and )
APPROX 2009 – Proc. 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 84–97.
DOI
Full paper appeared in Math. Oper. Res. 2012
• Nash Equilibria and the Price of Anarchy for Flows over Time ( and )
SAGT 2009 – Proc. 2nd International Symposium on Algorithmic Game Theory, pp. 323–334.
DOI
Full paper appeared in Theory Comput. Syst. 2011
• Packet Routing: Complexity and Algorithms (, and )
WAOA 2009 – Proc. 7th Workshop on Approximation and Online Algorithms, pp. 217–228.
DOI
• On the size of weights in randomized search heuristics ( and )
FOGA 2009 – Proc. 10th ACM SIGEVO International Workshop on Foundations of Genetic Algorithms, pp. 21–28.
DOI
• Traffic Networks and Flows over Time (, and )
Chapter in Algorithmics of Large and Complex Networks – Design, Analysis, and Simulation, .
DOI
• An Introduction to Network Flows Over Time ()
Chapter in Research Trends in Combinatorial Optimization (W. Cook, L. Lovász, J. Vygen, eds.), Springer, .
DOI
• Dynamic Flows in Time-Varying Networks ()
PhD thesis, TU Berlin / Amirkabir University of Technology, .
• A short proof of the VPN Tree Routing Conjecture on ring networks (, , and )
Oper. Res. Lett., 36(3):361–365, .
DOI
• Maximum $k$-Splittable $s,t$-Flows (, and )
Theory Comput. Syst., 43(1):56–66, .
DOI
Extended abstract appeared in Proc. of WAOA 2005
• Computing minimum cuts by randomized search heuristics (, and )
GECCO 2008 – Proc. Genetic and Evolutionary Computation Conference, pp. 779–786.
DOI
Full paper appeared in Algorithmica 2011
• Flows with unit path capacities and related packing and covering problems ( and )
COCOA 2008 – Proc. 2nd International Conference on Combinatorial Optimization and Applications, pp. 180–189.
DOI
Full paper appeared in J. Comb. Optim. 2009
• An Introduction to Network Flows over Time ()
Chapter in Research Trends in Combinatorial Optimization, Bonn Workshop on Combinatorial Optimization, November 3-7, 2008, Bonn, Germany, .
DOI
• Minimale aufspannende Bäume – Wenn das Naheliegende das Beste ist... ( and )
Chapter in Taschenbuch der Algorithmen, .
DOI
• WAOA 2008 – Proc. 6th Workshop on Approximation and Online Algorithms (Evripidis Bampis, Martin Skutella, eds.), .
DOI
• New Approaches for Virtual Private Network Design (, , and )
SIAM J. Comput., 37(3):706–721, .
DOI
Extended abstract appeared in Proc. of ICALP 2005
• Quickest Flows Over Time ( and )
SIAM J. Comput., 36(6):1600–1630, .
DOI
Extended abstracts of different parts appeared in Proc. of IPCO 2002 and SODA 2003
• An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times (, and )
Algorithmica, 47(3):299–321, .
DOI
Extended abstract appeared in Proc. of APPROX 2003
• Multicommodity flows over time: Efficient algorithms and complexity (, and )
Theor. Comput. Sci., 379(3):387–404, .
DOI
Extended abstract appeared in Proc. of ICALP 2003
• Convex Combinations of Single Source Unsplittable Flows (, and )
ESA 2007 – Proc. 15th European Symposium on Algorithms, pp. 395–406.
DOI
• WAOA 2007 – Proc. 5th Workshop on Approximation and Online Algorithms (Christos Kaklamanis, Martin Skutella, eds.), .
DOI
• Evacuation by Earliest Arrival Flows ()
PhD thesis, Universität Dortmund, .
• Path-Constrained Network Flows ()
PhD thesis, Universität Dortmund, .
• The Freeze-Tag Problem: How to Wake Up a Swarm of Robots (, , , and )
Algorithmica, 46(2):193–221, .
DOI
Extended abstract appeared in Proc. of SODA 2002
• Flows on few paths: Algorithms and lower bounds ( and )
Networks, 48(2):68–76, .
DOI
Extended abstract appeared in Proc. of ESA 2004
• Solving Evacuation Problems Efficiently–Earliest Arrival Flows with Multiple Sources ( and )
FOCS 2006 – Proc. 47th Symposium on Foundations of Computer Science, pp. 399–410.
DOI
Full paper appeared in Math. Oper. Res. 2009
• Length-Bounded Cuts and Flows (, , , , , , and )
ICALP 2006 – Proc. 33rd International Colloquium on Automata, Languages and Programming, pp. 679–690.
DOI
Full paper appeared in ACM Trans. Algorithms 2010
• Latency Constrained Aggregation in Sensor Networks (, , , , and )
ESA 2006 – Proc. 14th European Symposium on Algorithms, pp. 88–99.
DOI
Full paper appeared in ACM Trans. Algorithms 2009
• Multiline Addressing by Network Flow (, , and )
ESA 2006 – Proc. 14th European Symposium on Algorithms, pp. 744–755.
DOI
Full paper appeared in Algorithmica 2009
• List Scheduling in Order of $$\alpha$$-Points on a Single Machine ()
Chapter in Efficient Approximation and Online Algorithms – Recent Progress on Classical Combinatorial Optimization Problems and New Applications, .
DOI
• Flows over Time with Load-Dependent Transit Times ( and )
SIAM J. Optim., 15(4):1185–1202, .
DOI
Extended abstract appeared in Proc. of SODA 2002
• Stochastic Machine Scheduling with Precedence Constraints ( and )
SIAM J. Comput., 34(4):788–802, .
DOI
Extended abstract appeared in Proc. of SODA 2001
• The $k$-Splittable Flow Problem (, and )
Algorithmica, 42(3-4):231–248, .
DOI
Extended abstract appeared in Proc. of ESA 2002
• Approximating $k$-hop minimum-spanning trees (, , , , and )
Oper. Res. Lett., 33(2):115–120, .
DOI
• New Approaches for Virtual Private Network Design (, , and )
ICALP 2005 – Proc. 32nd International Colloquium on Automata, Languages and Programming, pp. 1151–1162.
DOI
Full paper appeared in SIAM J. Comput. 2007
• Approximation and Complexity of $k$-Splittable Flows (, and )
WAOA 2005 – Proc. 3rd Workshop on Approximation and Online Algorithms, pp. 244–257.
DOI
Full paper appeared in Theory Comput. Syst. 2008
• Length-Bounded and Dynamic $k$-Splittable Flows ( and )
OR 2005 – Proc. International Conference of the German Operations Research Society, pp. 297–302.
DOI
• Scheduling with AND/OR Precedence Constraints (, and )
SIAM J. Comput., 33(2):393–415, .
DOI
Extended abstract appeared in Proc. of SODA 2000
• Cooperative facility location games ( and )
J. Algorithms, 50(2):194–214, .
DOI
Extended abstract appeared in Proc. of SODA 2000
• Online Scheduling with Bounded Migration (, and )
ICALP 2004 – Proc. 31st International Colloquium on Automata, Languages and Programming, pp. 1111–1122.
DOI
Full paper appeared in Math. Oper. Res. 2009
• Flows on Few Paths: Algorithms and Lower Bounds ( and )
ESA 2004 – Proc. 12th European Symposium on Algorithms, pp. 520–531.
DOI
Full paper appeared in Networks 2006
• Preemptive scheduling with rejection (, and )
Math. Program., 94(2-3):361–374, .
DOI
Extended abstract appeared in Proc. of ESA 2000
• The complexity of economic equilibria for house allocation markets (, and )
Inf. Process. Lett., 88(5):219–223, .
DOI
• Minimum cost flows over time without intermediate storage ( and )
SODA 2003 – Proc. 14th ACM-SIAM Symposium on Discrete Algorithms, pp. 66–75.
[url]
Full paper appeared in SIAM J. Comput. 2007
• Multicommodity Flows over Time: Efficient Algorithms and Complexity (, and )
ICALP 2003 – Proc. 30th International Colloquium on Automata, Languages and Programming, pp. 397–409.
DOI
Full paper appeared in Theor. Comput. Sci. 2007
• An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times (, and )
APPROX 2003 – Proc. 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 71–82.
DOI
Full paper appeared in Algorithmica 2007
• Approximating the single source unsplittable min-cost flow problem ()
Math. Program., 91(3):493–514, .
DOI
Extended abstract appeared in Proc. of FOCS 2000
• The Power of $\alpha$-Points in Preemptive Single Machine Scheduling ( and )
J. Sched., 5:121–133, .
DOI
• Single Machine Scheduling with Release Dates (, , , and )
SIAM J. Discret. Math., 15(2):165–192, .
DOI
• Scheduling Unrelated Machines by Randomized Rounding ( and )
SIAM J. Discret. Math., 15(4):450–469, .
DOI
Extended abstract appeared in Proc. of ESA 1997
• The freeze-tag problem: how to wake up a swarm of robots (, , , and )
SODA 2002 – Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 568–577.
[url]
Full paper appeared in Algorithmica 2006
• Flows over time with load-dependent transit times ( and )
SODA 2002 – Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 174–183.
[url]
Full paper appeared in SIAM J. Optim. 2005
• The Quickest Multicommodity Flow Problem ( and )
IPCO 2002 – Proc. 9th Conference on Integer Programming and Combinatorial Optimization, pp. 36–53.
DOI
Full paper appeared in SIAM J. Comput. 2007
• Time-Expanded Graphs for Flow-Dependent Transit Times (, and )
ESA 2002 – Proc. 10th European Symposium on Algorithms, pp. 599–611.
DOI
• On the $k$-Splittable Flow Problem (, and )
ESA 2002 – Proc. 10th European Symposium on Algorithms, pp. 101–113.
DOI
Full paper appeared in Algorithmica 2005
• A PTAS for Minimizing the Total Weighted Completion Time on Identical Parallel Machines ( and )
Math. Oper. Res., 25(1):63–75, .
DOI
Extended abstract appeared in Proc. of STOC 1999
• Approximating the single source unsplittable min-cost flow problem ()
FOCS 2000 – Proc. 41st Symposium on Foundations of Computer Science, pp. 136–145.
DOI
Full paper appeared in Math. Program. 2002
• Cooperative facility location games ( and )
SODA 2000 – Proc. 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 76–85.
[url]
Full paper appeared in J. Algorithms 2004
• Forcing relations for AND/OR precedence constraints (, and )
SODA 2000 – Proc. 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 235–236.
[url]
Full paper appeared in SIAM J. Comput. 2004
• Preemptive Scheduling with Rejection (, and )
ESA 2000 – Proc. 8th European Symposium on Algorithms, pp. 268–277.
DOI
Full paper appeared in Math. Program. 2003
• A PTAS for Minimizing the Weighted Sum of Job Completion Times on Parallel Machines ( and )
STOC 1999 – Proc. 31st Symposium on Theory of Computing, pp. 400–407.
DOI
Full paper appeared in Math. Oper. Res. 2000
• Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates (, , , , , , , , , and )
FOCS 1999 – Proc. 40th Symposium on Foundations of Computer Science, pp. 32–44.
DOI
• Convex Quadratic Programming Relaxations for Network Scheduling Problems ()
ESA 1999 – Proc. 7th European Symposium on Algorithms, pp. 127–138.
DOI
Full paper appeared in J. ACM 2001
• Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem ()
Math. Oper. Res., 23(4):909–929, .
DOI
Extended abstract appeared in Proc. of SODA 1997
• Semidefinite Relaxations for Parallel Machine Scheduling ()
FOCS 1998 – Proc. 39th Symposium on Foundations of Computer Science, pp. 472–481.
DOI
Full paper appeared in J. ACM 2001
• Approximation and Randomization in Scheduling ()
PhD thesis, TU Berlin, .
[pdf]
• Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem ()
SODA 1997 – Proc. 8th ACM-SIAM Symposium on Discrete Algorithms, pp. 501–508.
[url]
Full paper appeared in Math. Oper. Res. 2000
• Scheduling-LPs Bear Probabilities: Randomized Approximations for Min-Sum Criteria ( and )
ESA 1997 – Proc. 5th European Symposium on Algorithms, pp. 416–429.
DOI
Full paper appeared in SIAM J. Discret. Math. 2002
• Random-Based Scheduling: New Approximations and LP Lower Bounds ( and )
RANDOM 1997 – Proc. 1st International Workshop on Randomization and Approximation Techniques in Computer Science, pp. 119–133.
DOI
Full paper appeared in J. Sched. 2002
• Parallel Repetition of MIP(2, 1) Systems ( and )
Chapter in Lectures on Proof Verification and Approximation Algorithms, .
DOI