Perturbation algorithm for a minimax regret minimum spanning tree problem
Journal Title: Operations Research and Decisions - Year 2014, Vol 24, Issue 1
Abstract
The problem of finding a robust spanning tree has been analysed. The problem consists of determining a minimum spanning tree of a graph with uncertain edge costs. We should determine a spanning tree that minimizes the difference in costs between the tree selected and the optimal tree. While doing this, all possible realizations of the edge costs should be taken into account. This issue belongs to the class of NP-hard problems. In this paper, an algorithm based on the cost perturbation method and adapted to the analysed problem has been proposed. The paper also contains the results of numerical experiments testing the effectiveness of the proposed algorithm and compares it with algorithms known in the literature. The research is based on a large number of various test examples taken from the literature.
Authors and Affiliations
Mariusz Makuchowski
Keywords
Related Articles
- EP ID EP168410
- DOI -
- Views 29
- Downloads 0
Using a multicriteria interactive approach in scheduling non-critical activities
A typical project consists of many activities. Logical dependencies cause some of them to be critical and some non-critical. While critical activities have a strict start time, in some projects the problem of selecting t...
Decisions involving databases, fuzzy databases and codatabases
The authors consider the following three ways of decision making: (i) decisions involving databases by means of standard tools of sequential logic and universal algebra; (ii) deci sions involvingfuzzy databases by means...
The present value of a portfolio of assets with present values determined by trapezoidal ordered fuzzy numbers
We consider the obvious thesis that the present value of a portfolio is equal to the sum of the present values of its components. The main goal of this paper is the implementation of this thesis in the case when present...
The number of stable matchings in models of the Gale-Shapley type with preferences given by partial orders
From the famous Gale–Shapley theorem we know that each classical marriage problem admits at least one stable matching. This fact has inspired researchers to search for the maximum number of possible stable matchings, whi...
Hybrid correlated data in risk assessment
A method for evaluating the risks in a situation has been presented where parameters in the calculation are expressed in the form of dependent fuzzy numbers and probability distributions. The procedure of risk estimation...