- 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 Optimization
Department of Mathematics
TU Darmstadt
Dolivostraße 15
64293 Darmstadt
- office:
- S4|10 - 221
- hours:
- monday 10 – 11 (by arrangement)
- tel.:
- (+49) 06151 / 16 – 25363
- e-mail:
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, NP-completeness
lecture notes
-
Discrete Optimization
SS 2024 (TU Darmstadt), SS 2020 (TU Darmstadt), SS 2017 (TU Darmstadt)
mixed integer linear programs, polyhedral combinatorics, computational complexity, branch-and-bound, 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), min-cost 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, k-server problems, primal-dual 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: Potential-Based 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
-
Online optimization of potential-based flow networks (since 07/2022)
DFG TRR 154, 3/4 position, 4 years
-
Competitive Analysis for Incremental Maximization (since 12/2019)
DFG individual grant, 1 position, 3 years -
Online Planning of Potential-Based 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 results
2024
- Unified Greedy Approximability beyond Submodular Maximization ()
SIAM Journal on Discrete Mathematics, 38(1):348-379, 2024. - Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows ()
SIAM Journal on Discrete Mathematics, 38(1):764-789, 2024. - A $(5/3+\varepsilon)$-Approximation Algorithm for Tricolored Non-crossing Euclidean TSP ()
In Proceedings of the 32nd Annual European Symposium on Algorithms (ESA), 2024. - Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree 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 Dial-a-Ride on the Line ()
Algorithmica, 85(5):1372–1414, 2023. - Point-to-point 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 dial-a-ride ()
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 Dial-a-Ride ()
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 energy-constrained 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 ACM-SIAM 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 Dial-a-Ride 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 energy-constrained 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. - Distance-preserving graph contractions ()
SIAM Journal on Discrete Mathematics, 33(3):1607–1636, 2019. - Approximate lumpability for Markovian agent-based 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 Dial-a-Ride 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 Dial-a-Ride 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 Graph-Theoretic 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 Energy-Constrained Robots ()
In Proceedings of the 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 139–153, 2019.
2018
- The simplex algorithm is NP-mighty ()
ACM Transactions on Algorithms, 15(1):5(19), 2018. - Distance-preserving 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):1477-1497, 2017. - Tight bounds for online TSP on the line ()
In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 994-1005, 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. - Energy-efficient 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
- Degree-constrained orientations of embedded graphs ()
Journal of Combinatorial Optimization, 3:758-773, 2016. - Undirected graph exploration with ${\Theta}(\log\log n)$ pebbles ()
In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 25-39, 2016. - Collaborative delivery with energy-constrained mobile robots ()
In Proceedings of the 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 258-274, 2016. - Scheduling transfers of resources over time: Towards car-sharing with flexible drop-offs ()
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:557-564, 2015. - Fast collaborative graph exploration ()
Information and Computation, 243:37-49, 2015. - Mapping simple polygons: The power of telling convex from reflex ()
ACM Transactions on Algorithms, 11:33(16), 2015. - The simplex algorithm is NP-mighty ()
In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 858-872, 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:106-113, 2014. - Packing a knapsack of unknown capacity ()
In Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS), pp. 276-287, 2014. - Rectilinear shortest path and rectilinear minimum spanning tree with neighborhoods ()
In Proceedings of the 3rd International Symposium on Combinatorial Optimization (ISCO), pp. 208-220, 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:1287-1307, 2013. - Mapping simple polygons: How robots benefit from looking back ()
Algorithmica, 65:43-59, 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 machine-dependent intervals ()
In Proceedings of the 13th International Algorithms and Data Structures Symposium (WADS), pp. 170-181, 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. 158-169, 2013. - Polygon-constrained 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. 67-82, 2013.
2012
- Reconstructing visibility graphs with simple robots ()
Theoretical Computer Science, 444:52-59, 2012. - Degree-constrained orientations of embedded graphs ()
In Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC), pp. 506-516, 2012. - Mapping polygons with agents that measure angles ()
In Proceedings of the 10th International Workshop on the Algorithmic Foundations of Robotics (WAFR), pp. 415-425, 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. 78-89, 2012.
2011
- Mapping polygons ()
PhD thesis, ETH Zurich, 2011. - A polygon is determined by its angles ()
Computational Geometry: Theory and Applications, 44:418-426, 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. 153-164, 2011.
2010
- Reconstructing a simple polygon from its angles ()
In Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 13-24, 2010. - How simple robots benefit from looking back ()
In Proceedings of the 7th International Conference on Algorithms and Complexity (CIAC), pp. 229-239, 2010.
2009
- Reconstructing visibility graphs with simple robots ()
In Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 87-99, 2009. - On the limitations of combinatorial visibilities ()
In Proceedings of the 25th European Workshop on Computational Geometry (EuroCG), pp. 207-210, 2009.
2008
Brief CV
-
Professor (W2)
TU Darmstadt, since 2021 (external offers W2, W3) -
Assistant Professor (tenure track)
TU Darmstadt, 2016-2021 (parental leave 08/2017 - 02/2018) -
PostDoc, Habilitation (Mathematics)
TU Berlin, 2012-2016 -
Visiting Professor
Augsburg University, summer 2015 -
PostDoc
ETH Zurich, 2011-2012 -
PhD (Theoretical Computer Science)
ETH Zurich, 2008-2011 -
MSc (Physics)
TU Darmstadt, 2006-2008 -
Diploma (Computer Science)
TU Darmstadt, 2003-2007; University of Saskatchewan, 2005-2006 -
BSc (Physics)
TU Darmstadt, 2003-2006; University of Saskatchewan, 2005-2006