An algebraic framework for multi-objective and robust variants of path problems
It is well known that various types of path problems in graphs can be treated together within a common algebraic framework. Thereby each type is characterized by a different ``path algebra", i.e., a different instance of the same abstract algebraic structure. This paper demonstrates that the co...
| Permalink: | http://skupnikatalog.nsk.hr/Record/nsk.NSK01001098339/Details |
|---|---|
| Matična publikacija: |
Glasnik matematički (Online) 55 (2020), 1 ; str. 143-176 |
| Glavni autor: | Manger, Robert (Author) |
| Vrsta građe: | e-članak |
| Jezik: | eng |
| Predmet: | |
| Online pristup: |
https://doi.org/10.3336/gm.55.1.12 Hrčak |
| LEADER | 02387naa a22003374i 4500 | ||
|---|---|---|---|
| 001 | NSK01001098339 | ||
| 003 | HR-ZaNSK | ||
| 005 | 20210609124502.0 | ||
| 006 | m d | ||
| 007 | cr|||||||||||| | ||
| 008 | 210420s2020 ci a |o |0|| ||eng | ||
| 024 | 7 | |2 doi |a 10.3336/gm.55.1.12 | |
| 035 | |a (HR-ZaNSK)001098339 | ||
| 040 | |a HR-ZaNSK |b hrv |c HR-ZaNSK |e ppiak | ||
| 041 | 0 | |a eng |b eng | |
| 042 | |a croatica | ||
| 044 | |a ci |c hr | ||
| 080 | 1 | |a 51 |2 2011 | |
| 100 | 1 | |a Manger, Robert |4 aut | |
| 245 | 1 | 3 | |a An algebraic framework for multi-objective and robust variants of path problems |h [Elektronička građa] / |c Robert Manger. |
| 300 | |b Ilustr. | ||
| 504 | |a Bibliografske bilješke na kraju teksta. | ||
| 504 | |a Abstract. | ||
| 520 | |a It is well known that various types of path problems in graphs can be treated together within a common algebraic framework. Thereby each type is characterized by a different ``path algebra", i.e., a different instance of the same abstract algebraic structure. This paper demonstrates that the common algebraic framework, although originally intended for conventional problem variants, can be extended to cover multi-objective and robust variants. Thus the paper is mainly concerned with constructing and justifying new path algebras that correspond to such more complex problem varieties. A consequence of the obtained algebraic formulation is that multi-objective or robust problem instances can be solved by well-known general algorithms designed to work over an arbitrary path algebra. The solutions obtained in this way comprise all paths that are efficient in the Pareto sense. The efficient paths are by default described only implicitly, as vectors of objective-function values. Still, it is shown in the paper that, with slightly extended versions of the involved algebras, the same paths can also be identified explicitly. Also, for robust problem instances it is possible to select only one ``robustly optimal" path according to a generalized min-max or min-max regret criterion. | ||
| 653 | 0 | |a Algebra putova |a Usmjereni graf |a Robusna optimizacija | |
| 773 | 0 | |t Glasnik matematički (Online) |x 1846-7989 |g 55 (2020), 1 ; str. 143-176 |w nsk.(HR-ZaNSK)000659858 | |
| 981 | |b Be2020 |b B03/20 | ||
| 998 | |b tino2106 | ||
| 856 | 4 | 0 | |u https://doi.org/10.3336/gm.55.1.12 |
| 856 | 4 | 0 | |u https://hrcak.srce.hr/239054 |y Hrčak |
| 856 | 4 | 1 | |y Digitalna.nsk.hr |