Prof. Dr. Yann Disser
RG OptimizationDepartment of Mathematics
TU Darmstadt
Dolivostraße 15
64293 Darmstadt
 office:
 S410  244
 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 reconstructionTeaching

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

Discrete Optimization
SS 2017 (TU Darmstadt)
mixed integer linear programs, polyhedral combinatorics, computational complexity, branchandbound, cutting planes, decomposition techniques, heuristics, approximation algorithms 
Combinatorial Optimization
SS 2016 (TU Berlin), SS 2015 (Uni Augsburg)
shortest paths, dynamic programming, maximum flow, mincost maximum flow, maximum matching, NPcompleteness 
Seminars
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)
Publications
51 results2019
 Hiring Secretaries over Time: The Benefit of Concurrent Employment ( )
Mathematics of Operations Research, 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), 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), 2019.
2018
 The simplex algorithm is NPmighty ( )
ACM Transactions on Algorithms, 15(1):5(19), 2018.  The minimum feasible tileset problem ( )
Algorithmica, 2018.  A general lower bound for collaborative tree exploration ( )
Theoretical Computer Science, 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.  Collaborative delivery with energyconstrained mobile robots ( )
Theoretical Computer Science, 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.  Energyefficient delivery by heterogenous mobile agents ( )
In Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 10(14), 2017.  Robust and adaptive search ( )
In Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 26(14), 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.  Scheduling maintenance jobs in networks ( )
In Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC), pp. 19–30, 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.  Mapping simple polygons: The power of telling convex from reflex ( )
ACM Transactions on Algorithms, 11:33(16), 2015.  Fast collaborative graph exploration ( )
Information and Computation, 243:3749, 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.  Max shortest path for imprecise points ( )
In Proceedings of the 30th European Workshop on Computational Geometry (EuroCG), 2015.  Interval selection on unrelated machines ( )
In Proceedings of the 12th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 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 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
 Mapping simple polygons: How robots benefit from looking back ( )
Algorithmica, 65:4359, 2013.  Simple agents learn to find their way: an introduction on mapping polygons ( )
Discrete Applied Mathematics, 161:12871307, 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.  Mapping polygons with agents that measure angles ( )
In Proceedings of the 10th International Workshop on the Algorithmic Foundations of Robotics (WAFR), pp. 415425, 2012.  Degreeconstrained orientations of embedded graphs ( )
In Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC), pp. 506516, 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

Assistant Professor (tenure track)
TU Darmstadt, since 2016 
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