Herzlich willkommen

Tailoring Individual Algorithms for On-Line Problems

ISBN: 978-3-86359-871-6

Schreiben Sie die erste Kundenmeinung

Verfügbarkeit: sofort lieferbar, 3-4 Tage

39,00 €
inkl. 7% MwSt., zzgl. Versandkosten

Quick Overview

In our time it is important to solve optimization problems which get the needed data only over time. This thesis provides a framework to learn optimization algorithms just from a problem formulation without additional knowledge but with room to improve is more structure of the problem at hand is provided. Central points of this work are how structure can be defined and how to measure performance of learned algorithms.

Tailoring Individual Algorithms for On-Line Problems

Double click on above image to view full picture

Zoom Out
Zoom In

More Views


In the current world a plethora of algorithms are responsible for the calculation the best possible decisions. Generally it is not possible to arrive at an optimal solution due to two factors: First, the computational complexity is too high to calculate an optimal solution in an acceptable time and second, often the needed information is not available, but is only revealed sequentially (on-line problem) such that algorithms also only are able to make the next decision sequentially. Such algorithms are called on-line algorithms in contrast to off-line algorithms that always have all information available. Even though, the same or similar on-line algorithms occur in the real world their solution quality is bounded downwards, if one applies currently known on-line algorithms. This thesis discusses the general approach of tailoring algorithms for all on-line problems. Naturally, the question arises whether a problem formulation, that allows for an algorithm to be learned, can be deduced from an on-line problem formulation as well as whether such an algorithm can actually be produced. Moreover, learned algorithms are currently black boxes and is not known how they can be compared reasonably with other algorithms. This thesis shows how an on-line problem formulation can be converted to a Markov decision problem (MDP) that can be used to learn an algorithm for the problem at hand. In addition, it’s shown at the example of the two different on-line problems of paging and vertex coloring that this approach is useful for practical problem sizes. Moreover, Algorithm problem formulations that reduce computational cost drastically are developed for both mentioned problems. Consequently, a method for the comparison of learned algorithms with other algorithms - learned or predefined - is developed. The thesis attaches great importance to the reproducibility of results. For that purpose, a framework developed within the scope of this thesis project was published. It can easily be extended and integrated in other programs. With the methods developed and discussed in this body of work it is possible to tailor individual algorithms for on-line problems without deeper knowledge of the on-line problem at hand. Furthermore, it provides a method to evaluate the quality of solutions of a learned on-line algorithm.

Additional Information

Autor Schönitz, Sebastian
ISBN/Artikelnr. 978-3-86359-871-6
Gewicht 0.521 kg
Erscheinungsdatum 28.07.2020
Lieferzeit 3-4 Tage