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 43
- 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...
Credit risk mangement in finance - a review of various approaches
Classification of customers of banks and financial institutions is an important task in today’s business world. Reducing the number of loans granted to companies of questionable credibility can positively influence banks...
The coexistence of controlling and other management methods
The effects of the coexistence of Controlling and other management methods (benchmarking, BPM, BPR, BSC, Competency-based Management, CRM, ERP, KM, LM, Outsourcing, Six Sigma, TQM) have been analysed. The complexity and...
Data Envelopment Analysis as an instrument for measuring the efficiency of courts
The paper addresses the problem of measuring the efficiency of civil jurisdiction courts. Non-parametric data envelopment analysis (DEA) has been proposed as a measurement instrument. Hearing (settling) a case within a r...
Indirect control and power
To determine who has the power within a stock corporate company can be a quite complex prob-lem, especially when control is achieved through alliances between shareholders. This problem arises especially in cases of indi...