Heuristics for Minimum Spanning K-tree Problem

Shangin R.; P. M. Pardalos

?

Heuristics for Minimum Spanning K-tree Problem

P. 1074–1083.

In this paper we consider the problem of finding a spanning k-tree of minimum weight in a complete weighted graph which has a number of applications in designing reliable telecommunication networks. This problem is known to be NP-hard. We propose four effective heuristics: the first heuristic is based on the idea of a well-known Prim's algorithm, the second one is based on a dynamic programming approach, and the other two use the idea of iterative improvement from a starting solution. Preliminary numerical experiment was performed to compare the effectiveness of the proposed algorithms with known heuristics and exact algorithms.

Language: English

Text on another site

Keywords: NP-hardness heuristics invulnerable networks spanning k-tree

In book

Procedia Computer Science. 2nd International Conference on Information Technology and Quantitative Management, ITQM 2014. National Research University Higher School of Economics (HSE) in Moscow (Russia) on June 3-5, 2014

Vol. 31. , Amsterdam: Elsevier, 2014.

Decision making under uncertainty: a heuristics overview and the analytic network process

Милкова М. А., Andreichikova O. N., Andreichikov A. V., Psychology. Journal of the Higher School of Economics 2019 No. 4 P. 730–751

The paper provides an overview of known heuristic techniques and different views on decision-making based on heuristics. We discuss heuristics of the “heuristics and biases” program introduced by Daniel Kahneman and Amos Tversky, and heuristics of the “fast and frugal heuristics” program developed by Gerd Gigerenzer and colleagues. We propose the idea that heuristics, being ...

Added: June 29, 2023

NP-hardness of the problem of optimal box positioning

Galatenko A. V., Nersisyan S., Zhuk D., Mathematics 2019 Vol. 7 No. 8 P. 711

We consider the problem of finding a position of a d-dimensional box with given edge lengths that maximizes the number of enclosed points of the given finite set P⊂Rd , i.e., the problem of optimal box positioning. We prove that while this problem is polynomial for fixed values of d, it is NP-hard in the ...

Added: April 28, 2020

Independent domination versus weighted independent domination

Lozin V. V., Malyshev D., Mosca R. et al., Information Processing Letters 2020 Vol. 156 P. 105914

Independent domination is one of the rare problems for which the complexity of weighted and unweighted versions is known to be different in some classes of graphs. Trying to better understand the gap between the two versions of the problem, in the present paper we prove two complexity results. First, we extend NP-hardness of the weighted ...

Added: January 16, 2020

Политическая наука и укрощение контингентности

Lokshin I., Политическая экспертиза: ПОЛИТЭКС 2019 Т. 15 № 1 С. 45–58

The paper makes an attempt at inserting (positivistic) political science in a broader epistemological context than it is usually conceived. The implied context is that of the contingency of the human world which was pointed out by Aristotle in “Nicomachean Ethics” when he stated that politics deals more with particulars than with general principles, and more with changeable ...

Added: October 29, 2019

A tolerance-based heuristic approach for the weighted independent set problem

Goldengorin B. I., Malyshev D., Pardalos P. M. et al., Journal of Combinatorial Optimization 2015 Vol. 29 No. 2 P. 433–450

The notion of a tolerance is a helpful tool for designing approximation and exact algorithms for solving combinatorial optimization problems. In this paper we suggest a tolerance-based polynomial heuristic algorithm for the weighted independent set problem. Several computational experiments show that our heuristics works very well on graphs of a small density ...

Added: October 3, 2013

Ипотечные заемщики: повседневные практики восходящей мобильности

Klimov I., Социологический журнал 2009 № 4 С. 104–136

The article has been examining the ways of transformation of mortgage borrowers' everyday life as well as peculiarities of decision making under uncertainty and high risks closely related to house building and purchase dwelling. Our research is carrying out in Irkutsk since 2007. It shows that mortgage is not only "a school of financial competence". ...

Added: April 7, 2013

Algorithms for Special Cases of the Single Machine Total Tardiness Problem and an Application to the Even-Odd Partition Problem

Lazarev A. A., Werner F., Mathematical and Computer Modelling 2009 Vol. 49 No. 9-10 P. 2061–2072

The scheduling problem of minimizing total tardiness on a single machine is known to be NP-hard in the ordinary sense. In this paper, we consider the special case of the problem when the processing times p_j and the due dates d_j of the jobs are oppositely ordered: p_1 >= p_2>=...>=p_n and d_1. ...

Added: November 24, 2012