Using a Generalized Statistically Optimal Method of Solution for Minimum Weighted Cover Task

Dmitriy Lapshin; Marina Lapshina; Nadezhda Yudina

doi:doi:10.12737/article_59c21391604168.79848908

UDC 63

Using a Generalized Statistically Optimal Method of Solution for Minimum Weighted Cover Task

Published в Forestry Engineering Journal · Volume 7, Issue 3, 2017 · Pages 290–299 · Rubrics: Business Administration. Model engineering. Information science

DOI 10.12737/article_59c21391604168.79848908

Received: 20.09.2017 Accepted: 01.11.2017 Published: 01.11.2017 Language of publication: RUS

Authors

Dmitriy Lapshin ¹ · Marina Lapshina ² · Nadezhda Yudina ³

1 Voronezh State Technical University (Institute of International Education and Cooperation, Deputy Director)
Voronezh, Voronezh, Russian Federation

2 Voronezh State University of Forestry and Technologies named after G.F. Morozov (Department of Computer Science and Information Systems, Professor)
Voronezh, Voronezh, Russian Federation

3 Voronezh State University of Forestry and Technologies named after G.F. Morozov (Departtment of Computer Science and Information Systems, assistant professor)
Voronezh, Voronezh, Russian Federation

ABSTRACT

Statistically optimal algorithm for finding minimal cover of 0.1-matrices for the unweighted matrix has been proposed in the works of O. V. German. The algorithm is based on iterative addition of new columns (columns-resolvent)to the matrix, which are built according to the authors' formulated the principle of group resolution (PGR). They have the following property. Under the assumption that optimal cover has not been obtained yet, each such cover contains at least one row from among those that cover the column - resolvent. After adding each new column, considered as a random 0.1-vector, analytical evaluation of mathematical expectation of the number of minimal covers with a given number of rows is made. The evaluation concludes the need to continue the iterations or termination of the algorithm. After evaluation it can be concluded about the necessity to continue the iterations or termination of the algorithm.The algorithm is tested for 600 randomly generated problems with a subsequent comparison with the exact solution. It can be concluded that analytical estimates for mathematical expectation of the number of covers with specified size are stable for matrices of large dimension. On the contrary, with a decrease in the number of columns these estimates become less stable. Doubtless, in our opinion, advantage of this method is its high speed. Thus, in the vast majority of cases, the algorithm concludes by finding the exact solution, which makes to consider it statistically optimal one. The advantage of this method is its speed, but it is empirically proven that increase in the dimension of the problem leads to unpredictable failures.

KEYWORDS

matrix algorithm rows columns weight.

Information Text References

Authors:

1. Voronezh State Technical University (Institute of International Education and Cooperation, Deputy Director)

Voronezh, Voronezh, Russian Federation

2. Voronezh State University of Forestry and Technologies named after G.F. Morozov (Department of Computer Science and Information Systems, Professor)

Voronezh, Voronezh, Russian Federation

3. Voronezh State University of Forestry and Technologies named after G.F. Morozov (Departtment of Computer Science and Information Systems, assistant professor)

Voronezh, Voronezh, Russian Federation

Type:

Article

Pages:

from 290 to 299

Status:

Published

Subject area:

UDC 63

Language:

Russian, English

Keywords:

matrix, algorithm, rows, columns, weight.

Text

Text (PDF): Read Download

Настоящая статья предлагает статистически оптимальный алгоритм распространить на более общий случай, в котором переменные входят в целевую функцию с произвольными неотрицательными коэффициентами, построенный алгоритм позволяет получить оптимальное решение в большинстве случаев, причем процент задач с точным решением увеличивается с увеличением числа итераций.

References

1. German O.V. Statisticheski optimal'nyy algoritm dlya zadachi o minimal'nom pokrytii [A statistically optimal algorithm for the minimal covering problem] // O.V. Herman, V.G. Naidenko /Economics and Math. Methods. - M .: Mir, 2013. T. 29. Issue. 4. pp. 42-48. (In Russian).

2. Papadimitriou X. Kombinatornaya optimizatsiya [Combinatorial optimization] / X. Papadimitriou, K. Staiglitz - Moscow: Nauka, 2007. - 217 p. (In Russian).

3. Kofman AA Metody i modeli issledovaniya operatsiy. Tselochislennoye programmirovaniye [Methods and models of operations research. Integer Programming] / A.A. Kofman, A. Henri-Laborder - M .: Mir, 2012. - 241 p. (In Russian).

4. Balashevich V A. Algoritmizatsiya matematicheskikh metodov planirovaniya [Algorithmization of mathematical methods of planning] / VA Balashevich-Minsk: Vysheish. Shk., 2008. -218 s. (In Russian).

5. Kovalev M.M. Diskretnaya optimizatsiya [Discrete optimization]. Kovalev. - Minsk: Belarusian Publishing House, University, 2007. - 167 p. (In Russian).

6. Lee D.T., Wu Y.F. Geometric complexity of some location problems, Algorithmica, 1 / D.T. Lee, Y.F. Wu. 1986. - p. 193-211.

7. McCreiqht E.M., van Wyk C.J. An O(n loglog n)-time algorithm for triangulating a simple polygon / E.M. McCreiqht, C.J. van Wyk // SIAM J. Comput., 17 - 1988. - p. 143-178.

8. Chazelle B.M., Edelsbrunner H. An optimal algorithm for intersecting line segments, manuscript / B.M. Chazelle, H. Edelsbrunner. - 2008. - 83 p.

9. Samuelson P.A. Abstract of a theorem concerning substituatability in open Leontief models / P.A. Samuelson. - I.: Collected Scientific papers, MIT Press, 2016. - pp. 36-44.

10. Zadeh L.A. Linear system Theory / L.A. Zadeh, C.A. Desoer // The State Space Approach, McGraw-Hill, N.Y., 1983. - p.p. 84-92.

This work is licensed under Creative Commons Attribution 4.0 International

Using a Generalized Statistically Optimal Method of Solution for Minimum Weighted Cover Task

Confirmation

Регистрация