# Prof. Dr. Yann Disser

RG Optimization
Department of Mathematics
Dolivostraße 15
office:
S4|10 - 244
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

# Teaching

• Online Optimization
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
• Discrete Optimization
mixed integer linear programs, polyhedral combinatorics, computational complexity, branch-and-bound, cutting planes, decomposition techniques, heuristics, approximation algorithms
• Combinatorial Optimization
SS 2016 (TU Berlin), SS 2015 (Uni Augsburg)
shortest paths, dynamic programming, maximum flow, min-cost maximum flow, maximum matching, NP-completeness
• 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

45 results

## 2018

• Scheduling maintenance jobs in networks (, , , , , , and )
Theoretical Computer Science, .
[bibtex]
• 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, .
• Collaborative Delivery with Energy-Constrained Mobile Robots (, , , , , , and )
Theoretical Computer Science, .
[bibtex]
• 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, .
[bibtex]

## 2015

• Improving the ${H}_k$-Bound on the Price of Stability in Undirected Shapley Network Design Games (, , and )
Theoretical Computer Science, 562:557-564, .
• Fast Collaborative Graph Exploration (, , , and )
Information and Computation, 243:37-49, .
• Mapping simple polygons: The power of telling convex from reflex (, , , and )
ACM Transactions on Algorithms, 11:33(16), .
• 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, .
• Max Shortest Path for Imprecise Points (, and )
In Proceedings of the 30th European Workshop on Computational Geometry (EuroCG), .
[bibtex]
• Interval Selection on Unrelated Machines (, , , and )
In Proceedings of the 12th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), .
[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 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)
• 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)