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 42
- Downloads 0
Spectral analysis of business cycles in Poland and its major trading partners
The properties of business cycles in Poland and its major trading partners have been examined. The business cycle synchronization (BCS) between Poland and other countries was studied in order to assess the impact of inte...
Analysis of complex decision problems based on cumulative prospect theory
Complex risky decision problems involve sequences of decisions and random events. The choice at a given stage depends on the decisions taken in the previous stages, as well as on the realizations of the random events tha...
Measurement of stock market liquidity supported by an algorithm inferring the initiator of a trade
The aim of this study is to assess and analyse selected liquidity/illiquidity measures derived from high-frequency intraday data from the Warsaw Stock Exchange (WSE). As the side initiating a trade cannot be directly ide...
Branch and bound algorithm for discrete multi- level linear fractional programming problem
An algorithm is proposed to find an integer solution for bilevel linear fractional programming problem with discrete variables. The method develops a cut that removes the integer solutions which are not bilevel feasible....
Choquet integral calculus on a continuous support and its applications
The results of the calculation of the Choquet integral of a monotone function on the nonnegative real line have been described. Next, the authors prepresented Choquet integral of nonmonotone functions, by constructing mo...