Integrating Pareto Optimization into Dynamic Programming

Gatter T, Giegerich R, Saule C (2016)
ALGORITHMS 9(1): 12.

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Zeitschriftenaufsatz | Veröffentlicht | Englisch
Abstract / Bemerkung
Pareto optimization combines independent objectives by computing the Pareto front of the search space, yielding a set of optima where none scores better on all objectives than any other. Recently, it was shown that Pareto optimization seamlessly integrates with algebraic dynamic programming: when scoring schemes A and B can correctly evaluate the search space via dynamic programming, then so can Pareto optimization with respect to A and B. However, the integration of Pareto optimization into dynamic programming opens a wide range of algorithmic alternatives, which we study in substantial detail in this article, using real-world applications in biosequence analysis, a field where dynamic programming is ubiquitous. Our results are two-fold: (1) We introduce the operation of a Pareto algebra product in the dynamic programming framework of Bellman's GAP. Users of this framework can now ask for Pareto optimization with a single keystroke. Careful evaluation of the implementation alternatives by means of an extended Bellman's GAP compiler demonstrates the dependence of the best implementation choice on the application at hand. (2) We extract from our experiments several pieces of advice to programmers who do not use a system such as Bellman's GAP, but who choose to hand-craft their dynamic programming recurrences, incorporating Pareto optimization from scratch.
Erscheinungsjahr
Zeitschriftentitel
ALGORITHMS
Band
9
Zeitschriftennummer
1
Artikelnummer
12
ISSN
PUB-ID

Zitieren

Gatter T, Giegerich R, Saule C. Integrating Pareto Optimization into Dynamic Programming. ALGORITHMS. 2016;9(1): 12.
Gatter, T., Giegerich, R., & Saule, C. (2016). Integrating Pareto Optimization into Dynamic Programming. ALGORITHMS, 9(1), 12. doi:10.3390/a9010012
Gatter, T., Giegerich, R., and Saule, C. (2016). Integrating Pareto Optimization into Dynamic Programming. ALGORITHMS 9:12.
Gatter, T., Giegerich, R., & Saule, C., 2016. Integrating Pareto Optimization into Dynamic Programming. ALGORITHMS, 9(1): 12.
T. Gatter, R. Giegerich, and C. Saule, “Integrating Pareto Optimization into Dynamic Programming”, ALGORITHMS, vol. 9, 2016, : 12.
Gatter, T., Giegerich, R., Saule, C.: Integrating Pareto Optimization into Dynamic Programming. ALGORITHMS. 9, : 12 (2016).
Gatter, Thomas, Giegerich, Robert, and Saule, Cedric. “Integrating Pareto Optimization into Dynamic Programming”. ALGORITHMS 9.1 (2016): 12.