EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
2376. Parallel computation of the Pareto frontier for the bi-objective minimum spanning tree problem
Invited abstract in session WA-37: Multiobjective Combinatorial Optimization, stream Multiobjective Optimization.
Wednesday, 8:30-10:00Room: 33 (building: 306)
Authors (first author is the speaker)
| 1. | Mariagrazia Cairo
|
| Statistical Sciences, Sapienza University of Rome | |
| 2. | Lavinia Amorosi
|
| Statistical Sciences, Sapienza | |
| 3. | Dell'Olmo Paolo
|
| Dipartimento di Statistica, Probabilità, Statistiche applicate, University of Rome La Sapienza |
Abstract
This talk presents a parallel algorithm for the bi-objective minimum spanning tree (BMST) problem which takes advantage of a two-phase procedure for the generation of a complete set of efficient solutions.
The first phase involves computing the extreme supported efficient solutions by resorting to an algorithmic approach (Prim embedded in a dichotomic search), while the second phase focuses on determining the non-extreme supported and non-supported efficient solutions.
In this latter phase, all spanning trees of a connected graph are generated through edge interchanges based on increasing evaluation of reduced costs of associated weighted linear programs.
The results of preliminary computational experiments will be discussed.
Keywords
- Programming, Multi-Objective
- Combinatorial Optimization
- Parallel Algorithms and Implementation
Status: accepted
Back to the list of papers