KIT | KIT-Bibliothek | Impressum | Datenschutz

Exact distributional analysis of online algorithms with lookahead

Dunke, Fabian 1; Nickel, Stefan 1
1 Fakultät für Elektrotechnik und Informationstechnik – Institut für Theoretische Elektrotechnik und Systemoptimierung (ITE), Karlsruher Institut für Technologie (KIT)


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

Verlagsausgabe §
DOI: 10.5445/IR/1000120569
Veröffentlicht am 19.07.2021
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Operations Research (IOR)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2021
Sprache Englisch
Identifikator ISSN: 1614-2411, 1619-4500
KITopen-ID: 1000120569
Erschienen in 4OR
Verlag Springer
Band 19
Seiten 199-233
Bemerkung zur Veröffentlichung Correction: After publication in volume 19, issue, page 199–233 the author decided to opt for Open Choice and to make the article an Open Access publication.
Vorab online veröffentlicht am 21.05.2020
Schlagwörter Online optimization; Lookahead; Distributional analysis; Algorithm analysis
Nachgewiesen in Dimensions
Web of Science
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page