### Inhalt des Dokuments

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

Citation key | AntoniadisHoeksmaMeissner+2017 |
---|---|

Author | Antoniadis, Antonios and Hoeksma, Ruben and Meißner, Julie and Verschae, José and Wiese, Andreas |

Title of Book | Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP) |

Year | 2017 |

ISBN | 978-3-95977-041-5 |

ISSN | 1868-8969 |

DOI | 10.4230/LIPIcs.ICALP.2017.31 |

Abstract | The General Scheduling Problem (GSP) generalizes scheduling problems with sum of cost objectives such as weighted flow time and weighted tardiness. Given a set of jobs with processing times, release dates, and job dependent cost functions, we seek to find a minimum cost preemptive schedule on a single machine. The best known algorithm for this problem and also for weighted flow time/tardiness is an O(loglog P)-approximation (where P denotes the range of the job processing times), while the best lower bound shows only strong NP-hardness. When release dates are identical there is also a gap: the problem remains strongly NP-hard and the best known approximation algorithm has a ratio of e+\epsilon (running in quasi-polynomial time). We reduce the latter gap by giving a QPTAS if the numbers in the input are quasi-polynomially bounded, ruling out the existence of an APX-hardness proof unless NP\subseteq DTIME(2^polylog(n)). Our techniques are based on the QPTAS known for the UFP-Cover problem, a particular case of GSP where we must pick a subset of intervals (jobs) on the real line with associated heights and costs. If an interval is selected, its height will help cover a given demand on any point contained within the interval. We reduce our problem to a generalization of UFP-Cover and use a sophisticated divide-and-conquer procedure with interdependent non-symmetric subproblems. We also present a pseudo-polynomial time approximation scheme for two variants of UFP-Cover. For the case of agreeable intervals we give an algorithm based on a new dynamic programming approach which might be useful for other problems of this type. The second one is a resource augmentation setting where we are allowed to slightly enlarge each interval. |