On calculation of the stability radius for a minimum spanning tree
Abstract
We consider a minimum spanning tree problem in the situation where weights of edges are exposed to independent perturbations. We study a quantitative characteristic of stability for a given optimal solutions of the problem. The characteristic is called the stability radius and defined as the limit level of edges weights perturbations which preserve optimality of a particular solution. We present an exact formula for the stability radius that allows calculating the radius in time which is extremely close to linear with respect to number of graph edges. This improves upon a well-known formula of an optimal solution for a linear combinatorial problem which requires complete enumeration of feasible solutions set whose cardinality may grow exponentially.
References
- Gordeev Je. N. Issledovanie ustojchivosti zadachi o kratchajshem ostovnom dereve v metrike l1 [Stability analysis of the minimum spanning tree problem]. Zh. vychislitel. mat. mat. fiz. 1999. Vol. 39, No. 5. P. 770 –778 (in Russ.).
- Sergienko I. V., Shilo V. P. Zadachi diskretnoj optimizacii. Problemy, metody reshenija, issledovanija [Discrete Optimization Problems. Challenges, Solution Techniques, and Analysis]. Kiev, 2003 (in Russ.).
- Emelichev V., Podkopaev D. Quantitative stability analysis for vector problems of 0 –1 programming. Discret. Optim. 2010. Vol. 7, No. 1/2. P. 48 – 63.
- Roland J., Smet Y. De, Figueira J. R. On the calculation of stability radius for multi-objective combinatorial optimization problems by inverse optimization. 4OR. 2012. Vol. 10, No. 4. P. 379 –389.
- Kuzʼmin K. G. Edinyj podhod k nahozhdeniju radiusov ustojchivosti v mnogokriterialʼnoj zadache o maksimalʼnom razreze grafa [A general approach to the calculation of stability radii for the max-cut problem with multiple criteria]. Diskretn. anal. issled. oper. 2015. Vol. 22, No. 5. P. 30 –51 (in Russ.).
- Eppstein D. Finding the k smallest spanning trees. BIT Numer. Math. 1992. Vol. 32, No. 2. P. 237–248.
- Frederickson G. N. Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and Smallest Spanning Trees Time. SIAM J. Comput. 1997. Vol. 26, No. 2. P. 484 –538.
- Pettie S. Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time. J. Graph Algorithms Appl. 2015. Vol. 19, No. 1. P. 375–391.
The authors who are published in this journal agree to the following:
- The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
- The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
- The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)
