### Page Content

### to Navigation

Project heads: | Nicole Megow (until March 2016) Martin Skutella |
---|---|

Researcher: | Julie Meißner |

Student research assistant: | Jacob Focke |

Duration: | June 2014 - May 2017 |

Support: | ECMath |

This research is carried out in the framework of Matheon supported by Einstein Foundation Berlin

## Description

Uncertainty in the input data is an omnipresent issue in most real world planning processes. Metropolitan infrastructure -its design, operation and maintenance- induces complex planning processes where data uncertainty lies, e. g. in processing durations, transit times, cost, market prices, customer demands, capacity, bandwidth, energy consumption, et cetera. Since decisions on the infrastructure are typically very cost-intensive and of long-term impact, there is an urgent need of best possible mathematical support in this decision making process.

The quality of solutions for optimization problems (e. g. in infrastructure networks) with uncertain input data crucially depends on the amount of uncertainty. More information, or even knowing the exact data, allows for significantly improved solutions. It is impossible to fully abolish/avoid uncertainty. Nevertheless, it is sometimes possible to obtain exact data, but it may involve certain exploration cost in time, money, energy, bandwidth, etc.

In telecommunication networks planning, for example, information on the existing infrastructure (copper lines, optical fiber etc.) or the transmission range might not be easily available. The challenging major task of this project is to develop a structural understanding and algorithmic methods on how to balance the cost for data exploration with the actual benefit for the quality of solution to the optimization problem under consideration.

## Recent Activities

- Experimental evluation of algorithms for Minimum Spanning Tree under Uncertainty, Code and Data (ZIP, 14,4 MB)
- Organization of the BIMoS Day on Combinatorial Optimization and Efficient Algorithms, November 2015
- Organization of Autumn School on Approximation Algorithms for Stochastic Optimization, September 2014

## Publications

Dürr, C., Erlebach, T., Megow, N. and Meißner, J.

**An Adversarial Model for Scheduling with Testing**.

In *Proceedings of Innovations in Theoretical Computer Science (ITCS)*, 2018.

full version on arXiv with title "Scheduling with Explorable Uncertainty". [pdf]

Focke, J., Megow, N. and Meißner, J.

**Minimum Spanning Tree under Uncertainty in Theory and Experiments**.

In *Proceedings of the Symposium on Experimental Algorithms (SEA)*, 2017.
[pdf]

Bjelde, A., Disser, Y., Hackfeld, J., Hansknecht, C., Lipmann, M., Meißner, J., Schewior, K., Schlöter, M. and Stougie, L.

**Tight bounds for online TSP on the line**.

In *Proceedings of the Symposium on Discrete Algorithms (SODA)*, pp. 994–1005, 2017.
[pdf]

Antoniadis, A., Hoeksma, R., Meißner, J., Verschae, J. and Wiese, A.

**A QPTAS for the General Scheduling Problem with Identical Release Dates**.

In *Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP)*, 2017.
[pdf]

Abed, F., Chen, L., Disser, Y., Groß, M., Megow, N., Meißner, J., Richter, A. and Rischke, R.

**Scheduling Maintenance Jobs in Networks**.

In *Proceedings of the International Conference on Algorithms and Complexity (CIAC)*, 2017.

full version on arXiv. [pdf]

Megow, N., Meißner, J. and Skutella, M.

**Randomization Helps Computing a Minimum Spanning Tree under Uncertainty**.

*SIAM Journal on Computing*, pp. 1217 - 1240, 2017.
[pdf]

Chen, L., Megow, N. and Schewior, K.

**An O(log m)-competitive algorithm for online machine minimization**.

In *Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, 2016.

Chen, L., Megow, N., Rischke, R. and Stougie, L.

**Stochastic and Robust Scheduling in the Cloud**.

In *Proceedings of the 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'15)*, pp. 175–186, 2015.

Megow, N., Meißner, J. and Skutella, M.

**Randomization Helps Computing a Minimum Spanning Tree Under Uncertainty**.

In *Proceedings of the European Symposium on Algorithms (ESA)*, 2015.
[pdf]

Matuschke, J., Skutella, M. and Soto, J.

**Robust randomized matchings**.

*Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015)*, pp. 1904-1915, 2015.

Megow, N. and Vredeveld, T.

**A Tight 2-Approximation for Preemptive Stochastic Scheduling**.

*Mathematics of Operations Research*, Vol. 39, pp. 1297-1310, 2014.
[pdf]

Welz, W.

**Robot Tour Planning with High Determination Costs**.

PhD thesis, TU Berlin, 2014.
[pdf]

Disser, Y., Megow, N., Klimm, M. and Stiller, S.

**Packing a Knapsack of Unknown Capacity**.

In *Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS)*, pp. 276–287, 2014.
[pdf]

Skutella, M., Sviridenko, M. and Uetz, M.

**Stochastic scheduling on unrelated machines**.

In **Mayr, E. W. and Portier, N. (ed.)**, *Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science*, Leibniz International Proceedings in Informatics, Vol. 25, pp. 639-650, Dagstuhl Publishing, 2014.