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

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...

Download PDF file
  • EP ID EP168410
  • DOI -
  • Views 42
  • Downloads 0

How To Cite

Mariusz Makuchowski (2014). Perturbation algorithm for a minimax regret minimum spanning tree problem. Operations Research and Decisions, 24(1), -. https://europub.co.uk/articles/-A-168410