Full-text resources of CEJSH and other databases are now available in the new Library of Science.
Visit https://bibliotekanauki.pl

Refine search results

Journals help

  1. 1 Operations Research and Decisions

Authors help

  1. 1 MAKUCHOWSKI M.

Years help

  1. 1 2014

Results found: 1

first rewind previous Page / 1 next fast forward last

Search results

Search:
in the keywords:  minimax regret
help Sort By:

help Limit search:
first rewind previous Page / 1 next fast forward last
1
Content available remote

Perturbation algorithm for a minimax regret minimum spanning tree problem

100%
MAKUCHOWSKI M.
Operations Research and Decisions
|
2014
|
vol. 24
|
issue 1
37-49
EN
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.
first rewind previous Page / 1 next fast forward last
JavaScript is turned off in your web browser. Turn it on to take full advantage of this site, then refresh the page.