 David Weckbecker (PhD [thesis], 2019  2023)
 Farehe Soheil (2022  2023), PhD candidate @ HPI Potsdam
 Alexander V. Hopp (PhD [thesis], 2016  2020), Senior AI Research Scientist @ Merck
 Christina Karousatou (Postdoc, 2018  2020), Research Engineer @ WINGS ICT solutions
 Alexander Birx (PhD [thesis], 2017  2020), Actuary @ ALH Group
 Jan Hackfeld (PhD [thesis], 2014  2018), Chief Research Officer @ Lightcurve
Prof. Dr. Yann Disser
RG OptimizationDepartment of Mathematics
TU Darmstadt
Dolivostraße 15
64293 Darmstadt
 office:
 S410  221
 hours:
 monday 10 – 11 (by arrangement)
 tel.:
 (+49) 06151 / 16 – 25363
 email:
Research Interests
combinatorial optimization, online algorithms, graph exploration, theory of optimization, computational complexity, incremental algorithms, approximation algorithms, network flows, robust optimization, geometric reconstructionGroup Members
Teaching

Algorithmic Discrete Mathematics
SS 2024 (TU Darmstadt), SS 2022 (TU Darmstadt), SS 2021 (TU Darmstadt), SS 2019 (TU Darmstadt)
algorithms, asymptotic growth, sorting, basic graph theory, minimum spanning trees, shortest paths, maximum flows, bipartite matchings, NPcompleteness
lecture notes

Discrete Optimization
SS 2024 (TU Darmstadt), SS 2020 (TU Darmstadt), SS 2017 (TU Darmstadt)
mixed integer linear programs, polyhedral combinatorics, computational complexity, branchandbound, cutting planes, decomposition techniques, heuristics, approximation algorithms
lecture notes

Combinatorial Optimization
WS 2023/24 (TU Darmstadt), SS 2022 (TU Darmstadt), WS 2019/20 (TU Darmstadt), SS 2016 (TU Berlin), SS 2015 (Uni Augsburg)
shortest paths (advanced), maximum flows (advanced), mincost maximum flows, maximum matchings, complexity
lecture notes

Online Optimization
SS 2023 (TU Darmstadt), WS 2021/22 (TU Darmstadt), WS 2018/19 (TU Darmstadt), WS 2016/17 (TU Darmstadt), WS 2014/15 (TU Berlin)
introduction to online optimization, list access problem, paging, randomized online algorithms, Yao's principle, online scheduling, metrical task systems, kserver problems, primaldual method
lecture notes

Introduction to Optimization
WS 2022/23 (TU Darmstadt)
convex sets and functions, polyhedra, LP duality, simplex method, ellipsoid method, optimality criteria, quadratic programs
lecture notes (german)

Labs
Deep Learning Lab, SS 2023 (TU Darmstadt)
Algorithms Lab, WS 2009, WS 2010 (ETH Zurich)

Seminars
SS 2024: Complexity of the Simplex Method (TU Darmstadt)
SS 2023: PotentialBased Flows (TU Darmstadt)
SS 2022: The Probabilistic Method (TU Darmstadt)
WS 2021/22: Approximation Algorithms (TU Darmstadt)
SS 2021: Incremental Optimization (TU Darmstadt)
WS 2019/20: Graph Exploration (TU Darmstadt)
SS 2018: Approximation Algorithms (TU Darmstadt)
SS 2017: Conditional Complexity Bounds (TU Darmstadt)
WS 2015/16: Graph Exploration (TU Berlin)
SS 2015: Online Optimization (Uni Augsburg)
Projects

Competitive Analysis for Incremental Maximization (since 12/2019)
DFG individual grant, 1 position, 3 years 
Online optimization of potentialbased flow networks (since 07/2022)
DFG TRR 154, 3/4 position, 4 years

Online Planning of PotentialBased Flows (2020)
DFG TRR 154, 3/4 position, 6 months 
Competitive Analysis of the Elevator Problem (2017  2020)
DFG GSC 233, 1 scholarship, 3 years 
Complexity of Optimization Algorithms (2016  2019)
DFG GSC 233, 1 scholarship, 3 years 
LogiScale  BigData in Logistics: Multiscale and Combinatorial Optimization Methods (2016  2019)
EU EFRE project, 2 positions, 3 years, with Max Klimm and Martin Skutella 
Competitive Exploration of Large Networks (2014  2016)
DFG SPP 1736, 1 position, 3 years, with Max Klimm
Publications
84 results2024
 Unified Greedy Approximability beyond Submodular Maximization ( )
SIAM Journal on Discrete Mathematics, 38(1):348379, 2024.  Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows ( )
SIAM Journal on Discrete Mathematics, 38(1):764789, 2024.  A $(5/3+\varepsilon)$Approximation Algorithm for Tricolored Noncrossing Euclidean TSP ( )
In Proceedings of the 32nd Annual European Symposium on Algorithms (ESA), 2024.  Bicriterial Approximation for the Incremental PrizeCollecting SteinerTree Problem ( )
In Proceedings of the 32nd Annual European Symposium on Algorithms (ESA), 2024.
2023
 The Space Complexity of Undirected Graph Exploration ( )
Chapter in Algorithms for Big Data (H. Bast, C. Korzen, U. Meyer, M. Penschuck, eds.), Springer, 2023.  An exponential lower bound for Zadeh's pivot rule ( )
Mathematical Programming, 199(1):865–936, 2023.  Improved Bounds for Open Online DialaRide on the Line ( )
Algorithmica, 85(5):1372–1414, 2023.  Pointtopoint and milk run delivery scheduling: models, complexity results, and algorithms based on Benders decomposition ( )
Annals of Operations Research, 322(1):467–496, 2023.  Incremental Maximization via Continuization ( )
In Proceedings of the 50th International Colloquium on Automata, Languages and Programming (ICALP), pp. 47(17), 2023.  Exploration of graphs with excluded minors ( )
In Proceedings of the 31st European Symposium on Algorithms (ESA), pp. 11(15), 2023.  Breaking the Size Barrier: Universal Circuits meet Lookup Tables ( )
In Proceedings of the 29th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), pp. 3–37, 2023.  A unified worst case for classical simplex and policy iteration pivot rules ( )
In Proceedings of the 34th International Symposium on Algorithms and Computation (ISAAC), pp. 27(17), 2023.  Tight analysis of the lazy algorithm for open online dialaride ( )
In Proceedings of the 18th International Algorithms and Data Structures Symposium (WADS), pp. 43–64, 2023.
2022
 General Bounds for Incremental Maximization ( )
Mathematical Programming, 191(2):953–979, 2022.  Unified Greedy Approximability Beyond Submodular Maximization ( )
In Proceedings of the 7th International Symposium on Combinatorial Optimization (ISCO), pp. 299–311, 2022.  On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension ( )
In Proceedings of the 17th International Symposium on Parameterized and Exact Computation (IPEC), pp. 5(23), 2022.  An Improved Algorithm for Open Online DialaRide ( )
In Proceedings of the 20th Workshop on Approximation and Online Algorithms (WAOA), pp. 154–171, 2022.
2021
 Tight bounds for online TSP on the line ( )
ACM Transactions on Algorithms, 17(1):3:1–3:58, 2021.  Travelling on Graphs with Small Highway Dimension ( )
Algorithmica, 83(5):1352–1370, 2021.  An Improved Lower Bound for Competitive Graph Exploration ( )
Theoretical Computer Science, 868:65–86, 2021.  Collaborative delivery on a fixed path with homogeneous energyconstrained agents ( )
Theoretical Computer Science, 868:87–96, 2021.  Efficient Fully Dynamic Elimination Forests with Applications to Detecting Long Paths and Cycles ( )
In Proceedings of the 32nd Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pp. 796–809, 2021.  Fractionally Subadditive Maximization under an Incremental Knapsack Constraint ( )
In Proceedings of the 19th Workshop on Approximation and Online Algorithms (WAOA), pp. 206–223, 2021.
2020
 Hiring Secretaries over Time: The Benefit of Concurrent Employment ( )
Mathematics of Operations Research, 45(1):323–352, 2020.  Tight analysis of the Smartstart algorithm for online DialaRide on the line ( )
SIAM Journal on Discrete Mathematics, 34(2):1409–1443, 2020.  The Complexity of Computing a Robust Flow ( )
Operations Research Letters, 48(1):18–23, 2020.  A general lower bound for collaborative tree exploration ( )
Theoretical Computer Science, 811:70–78, 2020.  Collaborative delivery with energyconstrained mobile robots ( )
Theoretical Computer Science, 810:2–14, 2020.  Recoloring Interval Graphs with Limited Recourse Budget ( )
In Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 17(23), 2020.
2019
 Tight bounds for undirected graph exploration with pebbles and multiple agents ( )
Journal of the ACM, 66(6):40(41), 2019.  Distancepreserving graph contractions ( )
SIAM Journal on Discrete Mathematics, 33(3):1607–1636, 2019.  Approximate lumpability for Markovian agentbased models using local symmetries ( )
Journal of Applied Probability, 56(3):647–671, 2019.  The minimum feasible tileset problem ( )
Algorithmica, 81(3):1126–1151, 2019.  Scheduling maintenance jobs in networks ( )
Theoretical Computer Science, 754:107–121, 2019.  On Friedmann's Subexponential Lower Bound for Zadeh's Pivot Rule ( )
In Proceedings of the 20th Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 168–180, 2019.  Tight analysis of the Smartstart algorithm for online DialaRide on the line ( )
In Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 15(17), 2019.  Improved Bounds for Open Online DialaRide on the Line ( )
In Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pp. 21(22), 2019.  Travelling on Graphs with Small Highway Dimension ( )
In Proceedings of the 45th International Workshop on GraphTheoretic Concepts in Computer Science (WG), pp. 175–189, 2019.  Evacuating Two Robots from a Disk: A Second Cut ( )
In Proceedings of the 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 200–214, 2019.  Collaborative Delivery on a Fixed Path with Homogeneous EnergyConstrained Robots ( )
In Proceedings of the 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 139–153, 2019.
2018
 The simplex algorithm is NPmighty ( )
ACM Transactions on Algorithms, 15(1):5(19), 2018.  Distancepreserving graph contractions ( )
In Proceedings of the 9th Innovations in Theoretical Computer Science conference (ITCS), pp. 51(14), 2018.
2017
 Geometric reconstruction problems ( )
Chapter in Handbook of Discrete and Computational Geometry, Third Edition (J.E. Goodman, J. O'Rourke, C.D. Tóth, eds.), CRC Press LLC, 2017.  Packing a knapsack of unknown capacity ( )
SIAM Journal on Discrete Mathematics, 31(3):14771497, 2017.  Tight bounds for online TSP on the line ( )
In Proceedings of the 28th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pp. 9941005, 2017.  General bounds for incremental maximization ( )
In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 43(14), 2017.  Robust and adaptive search ( )
In Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 26(14), 2017.  Energyefficient delivery by heterogenous mobile agents ( )
In Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 10(14), 2017.  Scheduling maintenance jobs in networks ( )
In Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC), pp. 19–30, 2017.  A general lower bound for collaborative tree exploration ( )
In Proceedings of the 24th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 125–139, 2017.
2016
 Degreeconstrained orientations of embedded graphs ( )
Journal of Combinatorial Optimization, 3:758773, 2016.  Undirected graph exploration with ${\Theta}(\log\log n)$ pebbles ( )
In Proceedings of the 27th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pp. 2539, 2016.  Collaborative delivery with energyconstrained mobile robots ( )
In Proceedings of the 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 258274, 2016.  Scheduling transfers of resources over time: Towards carsharing with flexible dropoffs ( )
In Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN), pp. 220–234, 2016.
2015
 Improving the ${H}_k$Bound on the price of stability in undirected shapley network design games ( )
Theoretical Computer Science, 562:557564, 2015.  Fast collaborative graph exploration ( )
Information and Computation, 243:3749, 2015.  Mapping simple polygons: The power of telling convex from reflex ( )
ACM Transactions on Algorithms, 11:33(16), 2015.  The simplex algorithm is NPmighty ( )
In Proceedings of the 26th ACMSIAM Symposium on Discrete Algorithms (SODA), pp. 858872, 2015.  Scheduling bidirectional traffic on a path ( )
In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 406–418, 2015.  Interval selection on unrelated machines ( )
In Proceedings of the 12th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 2015.  Max shortest path for imprecise points ( )
In Proceedings of the 30th European Workshop on Computational Geometry (EuroCG), 2015.
2014
 Mapping a polygon with holes using a compass ( )
Theoretical Computer Science, 553:106113, 2014.  Packing a knapsack of unknown capacity ( )
In Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS), pp. 276287, 2014.  Rectilinear shortest path and rectilinear minimum spanning tree with neighborhoods ( )
In Proceedings of the 3rd International Symposium on Combinatorial Optimization (ISCO), pp. 208220, 2014.  The minimum feasible tileset problem ( )
In Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA), pp. 144–155, 2014.
2013
 Simple agents learn to find their way: an introduction on mapping polygons ( )
Discrete Applied Mathematics, 161:12871307, 2013.  Mapping simple polygons: How robots benefit from looking back ( )
Algorithmica, 65:4359, 2013.  Fast collaborative graph exploration ( )
In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), pp. 520–532, 2013.  Interval selection with machinedependent intervals ( )
In Proceedings of the 13th International Algorithms and Data Structures Symposium (WADS), pp. 170181, 2013.  Improving the ${H}_k$bound on the price of stability in undirected Shapley network design games ( )
In Proceedings of the 8th International Conference on Algorithms and Complexity (CIAC), pp. 158169, 2013.  Polygonconstrained motion planning problems ( )
In Proceedings of the 9th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS), pp. 6782, 2013.
2012
 Reconstructing visibility graphs with simple robots ( )
Theoretical Computer Science, 444:5259, 2012.  Degreeconstrained orientations of embedded graphs ( )
In Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC), pp. 506516, 2012.  Mapping polygons with agents that measure angles ( )
In Proceedings of the 10th International Workshop on the Algorithmic Foundations of Robotics (WAFR), pp. 415425, 2012.  Mapping a polygon with holes using a compass ( )
In Proceedings of the 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS), pp. 7889, 2012.
2011
 Mapping polygons ( )
PhD thesis, ETH Zurich, 2011.  A polygon is determined by its angles ( )
Computational Geometry: Theory and Applications, 44:418426, 2011.  Telling convex from reflex allows to map a polygon ( )
In Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 153164, 2011.
2010
 Reconstructing a simple polygon from its angles ( )
In Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 1324, 2010.  How simple robots benefit from looking back ( )
In Proceedings of the 7th International Conference on Algorithms and Complexity (CIAC), pp. 229239, 2010.
2009
 Reconstructing visibility graphs with simple robots ( )
In Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 8799, 2009.  On the limitations of combinatorial visibilities ( )
In Proceedings of the 25th European Workshop on Computational Geometry (EuroCG), pp. 207210, 2009.
2008
Brief CV

Professor (W2)
TU Darmstadt, since 2021 (external offers W2, W3) 
Assistant Professor (tenure track)
TU Darmstadt, 20162021 (parental leave 08/2017  02/2018) 
PostDoc, Habilitation (Mathematics)
TU Berlin, 20122016 
Visiting Professor
Augsburg University, summer 2015 
PostDoc
ETH Zurich, 20112012 
PhD (Theoretical Computer Science)
ETH Zurich, 20082011 
MSc (Physics)
TU Darmstadt, 20062008 
Diploma (Computer Science)
TU Darmstadt, 20032007; University of Saskatchewan, 20052006 
BSc (Physics)
TU Darmstadt, 20032006; University of Saskatchewan, 20052006