Artikel
Exact distributional analysis of online algorithms with lookahead
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).
- Sprache
-
Englisch
- Erschienen in
-
Journal: 4OR ; ISSN: 1614-2411 ; Volume: 19 ; Year: 2020 ; Issue: 2 ; Pages: 199-233 ; Berlin, Heidelberg: Springer
- Klassifikation
-
Management
- Thema
-
Online optimization
Lookahead
Distributional analysis
Algorithm analysis
- Ereignis
-
Geistige Schöpfung
- (wer)
-
Dunke, Fabian
Nickel, Stefan
- Ereignis
-
Veröffentlichung
- (wer)
-
Springer
- (wo)
-
Berlin, Heidelberg
- (wann)
-
2020
- DOI
-
doi:10.1007/s10288-020-00442-1
- Letzte Aktualisierung
-
10.03.2025, 11:42 MEZ
Datenpartner
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
Objekttyp
- Artikel
Beteiligte
- Dunke, Fabian
- Nickel, Stefan
- Springer
Entstanden
- 2020
Ähnliche Objekte (12)
Exact exponential algorithms
Exact algorithms for constraint satisfaction problems
Adaptive analysis of on-line algorithms
Packing grid figures : exact algorithms and heuristics
A Survey on Exact Algorithms of SAT
Exact algorithms for NP hard problems on networks : design, analysis and implementation
Exact algorithms for NP hard problems on networks : design, analysis, and implementation
Distributional analysis of entities
NP-hard networking problems : exact and approximate algorithms
Algorithms and statistical methods for exact motif discovery
Minimum genus and maximum planar subgraph : exact genus and maximum planar subgraph : exact algorithms and general limits of approximation algorithms
Exact algorithms for network design problems using graph orientations
Exact exponential algorithms
Exact algorithms for constraint satisfaction problems
Adaptive analysis of on-line algorithms
Packing grid figures : exact algorithms and heuristics
A Survey on Exact Algorithms of SAT
Exact algorithms for NP hard problems on networks : design, analysis and implementation
Exact algorithms for NP hard problems on networks : design, analysis, and implementation
Distributional analysis of entities
NP-hard networking problems : exact and approximate algorithms
Algorithms and statistical methods for exact motif discovery
Minimum genus and maximum planar subgraph : exact genus and maximum planar subgraph : exact algorithms and general limits of approximation algorithms
Exact algorithms for network design problems using graph orientations
Exact exponential algorithms
Exact algorithms for constraint satisfaction problems
Adaptive analysis of on-line algorithms
Packing grid figures : exact algorithms and heuristics
A Survey on Exact Algorithms of SAT
Exact algorithms for NP hard problems on networks : design, analysis and implementation
Exact algorithms for NP hard problems on networks : design, analysis, and implementation
Distributional analysis of entities
NP-hard networking problems : exact and approximate algorithms
Algorithms and statistical methods for exact motif discovery
Minimum genus and maximum planar subgraph : exact genus and maximum planar subgraph : exact algorithms and general limits of approximation algorithms