# Prof. Dr. Yann Disser

RG Optimization
Department of Mathematics
Dolivostraße 15
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 reconstruction

# Projects

• Competitive Analysis for Incremental Maximization (since 12/2019)
DFG individual grant, 1 position, 3 years
• Online Planning of Potential-Based Flows (since 03/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

67 results

## to appear

• Collaborative delivery on a fixed path with homogeneous energy-constrained agents (, , , and )
Theoretical Computer Science, .
[bibtex]
• Efficient Fully Dynamic Elimination Forests with Applications to Detecting Long Paths and Cycles (, , , , , , , , , and )
In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), .
[bibtex]

## 2021

• Travelling on Graphs with Small Highway Dimension (, , and )
Algorithmica, .
• An Improved Lower Bound for Competitive Graph Exploration (, , and )
Theoretical Computer Science, .

## 2020

• General Bounds for Incremental Maximization (, , and )
Mathematical Programming, .
• Hiring Secretaries over Time: The Benefit of Concurrent Employment (, , , , , , and )
Mathematics of Operations Research, 45(1):323–352, .
• Tight bounds for online TSP on the line (, , , , , , , and )
ACM Transactions on Algorithms, 17(1), .
• Tight analysis of the Smartstart algorithm for online Dial-a-Ride on the line ( and )
SIAM Journal on Discrete Mathematics, 34(2):1409–1443, .
• The Complexity of Computing a Robust Flow ( and )
Operations Research Letters, 48(1):18–23, .
• A general lower bound for collaborative tree exploration (, , , and )
Theoretical Computer Science, 811:70–78, .
• Collaborative delivery with energy-constrained mobile robots (, , , , , , and )
Theoretical Computer Science, 810:2–14, .
• Recoloring Interval Graphs with Limited Recourse Budget (, , , and )
In Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 17(23), .

## 2019

• Tight bounds for undirected graph exploration with pebbles and multiple agents (, and )
Journal of the ACM, 66(6):40(41), .
• Distance-preserving graph contractions (, , , , and )
SIAM Journal on Discrete Mathematics, 33(3):1607–1636, .
• Approximate lumpability for Markovian agent-based models using local symmetries (, , and )
Journal of Applied Probability, 56(3):647–671, .
• The minimum feasible tileset problem (, and )
Algorithmica, 81(3):1126–1151, .
• Scheduling maintenance jobs in networks (, , , , , , and )
Theoretical Computer Science, 754:107–121, .
• On Friedmann's Subexponential Lower Bound for Zadeh's Pivot Rule ( and )
In Proceedings of the 20th Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 168–180, .
• Tight analysis of the Smartstart algorithm for online Dial-a-Ride on the line ( and )
In Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 15(17), .
• Improved Bounds for Open Online Dial-a-Ride on the Line (, and )
In Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pp. 21(22), .
• Travelling on Graphs with Small Highway Dimension (, , and )
In Proceedings of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp. 175–189, .
• Evacuating Two Robots from a Disk: A Second Cut ( and )
In Proceedings of the 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 200–214, .
• Collaborative Delivery on a Fixed Path with Homogeneous Energy-Constrained Robots (, , , and )
In Proceedings of the 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 139–153, .

## 2018

• The simplex algorithm is NP-mighty ( and )
ACM Transactions on Algorithms, 15(1):5(19), .
• Distance-preserving graph contractions (, , , , and )
In Proceedings of the 9th Innovations in Theoretical Computer Science conference (ITCS), pp. 51(14), .

## 2017

• Geometric reconstruction problems ( and )
Chapter in Handbook of Discrete and Computational Geometry, Third Edition (J.E. Goodman, J. O'Rourke, C.D. Tóth, eds.), CRC Press LLC, .
• Packing a knapsack of unknown capacity (, , and )
SIAM Journal on Discrete Mathematics, 31(3):1477-1497, .
• Tight bounds for online TSP on the line (, , , , , , , and )
In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 994-1005, .
• General bounds for incremental maximization (, and )
In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 43(14), .
• Energy-efficient delivery by heterogenous mobile agents (, , , , , and )
In Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 10(14), .
• Robust and adaptive search ( and )
In Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 26(14), .
• Scheduling maintenance jobs in networks (, , , , , , and )
In Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC), pp. 19–30, .
• A general lower bound for collaborative tree exploration (, , , and )
In Proceedings of the 24th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 125–139, .

## 2016

• Degree-constrained orientations of embedded graphs ( and )
Journal of Combinatorial Optimization, 3:758-773, .
• Undirected graph exploration with ${\Theta}(\log\log n)$ pebbles (, and )
In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 25-39, .
• Collaborative delivery with energy-constrained mobile robots (, , , , , , and )
In Proceedings of the 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 258-274, .
• Scheduling transfers of resources over time: Towards car-sharing with flexible drop-offs (, , and )
In Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN), pp. 220–234, .

## 2015

• Improving the ${H}_k$-Bound on the price of stability in undirected shapley network design games (, , and )
Theoretical Computer Science, 562:557-564, .
• Mapping simple polygons: The power of telling convex from reflex (, , , and )
ACM Transactions on Algorithms, 11:33(16), .
• Fast collaborative graph exploration (, , , and )
Information and Computation, 243:37-49, .
• The simplex algorithm is NP-mighty ( and )
In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 858-872, .
• Scheduling bidirectional traffic on a path (, and )
In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 406–418, .
• Interval selection on unrelated machines (, , , and )
In Proceedings of the 12th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), .
[bibtex]
• Max shortest path for imprecise points (, and )
In Proceedings of the 30th European Workshop on Computational Geometry (EuroCG), .
[bibtex]

## 2014

• Mapping a polygon with holes using a compass (, , and )
Theoretical Computer Science, 553:106-113, .
• Packing a knapsack of unknown capacity (, , and )
In Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS), pp. 276-287, .
• Rectilinear shortest path and rectilinear minimum spanning tree with neighborhoods (, , and )
In Proceedings of the 3rd International Symposium on Combinatorial Optimization (ISCO), pp. 208-220, .
• The minimum feasible tileset problem (, and )
In Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA), pp. 144–155, .

## 2013

• Simple agents learn to find their way: an introduction on mapping polygons (, , , and )
Discrete Applied Mathematics, 161:1287-1307, .
• Mapping simple polygons: How robots benefit from looking back (, , , and )
Algorithmica, 65:43-59, .
• Fast collaborative graph exploration (, , , and )
In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), pp. 520–532, .
• Interval selection with machine-dependent intervals (, , and )
In Proceedings of the 13th International Algorithms and Data Structures Symposium (WADS), pp. 170-181, .
• Improving the ${H}_k$-bound on the price of stability in undirected Shapley network design games (, , and )
In Proceedings of the 8th International Conference on Algorithms and Complexity (CIAC), pp. 158-169, .
• Polygon-constrained motion planning problems (, , , , and )
In Proceedings of the 9th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS), pp. 67-82, .

## 2012

• Reconstructing visibility graphs with simple robots (, , , , and )
Theoretical Computer Science, 444:52-59, .
• Mapping a polygon with holes using a compass (, , and )
In Proceedings of the 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS), pp. 78-89, .
• Mapping polygons with agents that measure angles (, and )
In Proceedings of the 10th International Workshop on the Algorithmic Foundations of Robotics (WAFR), pp. 415-425, .
• Degree-constrained orientations of embedded graphs ( and )
In Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC), pp. 506-516, .

## 2011

• Mapping polygons ()
PhD thesis, ETH Zurich, .
• A polygon is determined by its angles (, and )
Computational Geometry: Theory and Applications, 44:418-426, .
• Telling convex from reflex allows to map a polygon (, , , and )
In Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 153-164, .

## 2010

• Reconstructing a simple polygon from its angles (, and )
In Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 13-24, .
• How simple robots benefit from looking back (, , , and )
In Proceedings of the 7th International Conference on Algorithms and Complexity (CIAC), pp. 229-239, .

## 2009

• Reconstructing visibility graphs with simple robots (, , , , and )
In Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 87-99, .
• On the limitations of combinatorial visibilities (, , , , and )
In Proceedings of the 25th European Workshop on Computational Geometry (EuroCG), pp. 207-210, .
[bibtex]

## 2008

• Local realism, detection efficiencies, and probability polytopes (, , and )
Physical Review A, 73:032116(8), .
• Multi-criteria shortest paths in time-dependent train networks (, and )
In Proceedings of the 7th International Workshop on Experimental Algorithms (WEA), pp. 347-361, .

# Brief CV

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