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).
- Language
-
Englisch
- Bibliographic citation
-
Journal: 4OR ; ISSN: 1614-2411 ; Volume: 19 ; Year: 2020 ; Issue: 2 ; Pages: 199-233 ; Berlin, Heidelberg: Springer
- Classification
-
Management
- Subject
-
Online optimization
Lookahead
Distributional analysis
Algorithm analysis
- Event
-
Geistige Schöpfung
- (who)
-
Dunke, Fabian
Nickel, Stefan
- Event
-
Veröffentlichung
- (who)
-
Springer
- (where)
-
Berlin, Heidelberg
- (when)
-
2020
- DOI
-
doi:10.1007/s10288-020-00442-1
- Last update
-
10.03.2025, 11:42 AM CET
Data provider
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. If you have any questions about the object, please contact the data provider.
Object type
- Artikel
Associated
- Dunke, Fabian
- Nickel, Stefan
- Springer
Time of origin
- 2020
Other Objects (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