Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/288429 
Year of Publication: 
2020
Citation: 
[Journal:] 4OR [ISSN:] 1614-2411 [Volume:] 19 [Issue:] 2 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2020 [Pages:] 199-233
Publisher: 
Springer, Berlin, Heidelberg
Abstract: 
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).
Subjects: 
Online optimization
Lookahead
Distributional analysis
Algorithm analysis
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.