Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/288429 
Erscheinungsjahr: 
2020
Quellenangabe: 
[Journal:] 4OR [ISSN:] 1614-2411 [Volume:] 19 [Issue:] 2 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2020 [Pages:] 199-233
Verlag: 
Springer, Berlin, Heidelberg
Zusammenfassung: 
In online optimization, input data is revealed sequentially. Optimization problems in practice often exhibit this type of information disclosure as opposed to standard offline optimization where all information is known in advance. We analyze the performance of algorithms for online optimization with lookahead using a holistic distributional approach. To this end, we first introduce the performance measurement method of counting distribution functions. Then, we derive analytical expressions for the counting distribution functions of the objective value and the performance ratio in elementary cases of the online bin packing and the online traveling salesman problem. For bin packing, we also establish a relation between algorithm processing and the Catalan numbers. The paper shows that an exact analysis is strongly interconnected to the combinatorial structure of the problem and algorithm under consideration. Results further indicate that the value of lookahead heavily relies on the problem itself. The analysis also shows that exact distributional analysis could be used in order to discover key effects and identify related root causes in relatively simple problem settings. These insights can then be transferred to the analysis of more complex settings where the introduced performance measurement approach has to be used on an approximative basis (e.g., in a simulation-based optimization).
Schlagwörter: 
Online optimization
Lookahead
Distributional analysis
Algorithm analysis
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Dokumentversion: 
Published Version

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.