Geodesic
Probabilistic models for the analysis of inverse extremal problems in combinatorics
Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences, Tome 26 (2022) no. 3, pp. 573-591

Voir la notice de l'article provenant de la source Math-Net.Ru

In an inverse extremal problem for a combinatorial scheme with a given value of the objective function of the form of a certain extreme value of its characteristic, a probabilistic model is developed that ensures that this value is obtained in its outcomes. Two types of such characteristics are considered, relating to each of the schemes or to a set of outcomes. The pre-asymptotic analysis of such a model is carried out by the author's enumerative method. It is based on the construction of an iterative random process with iterations of successive stages of a numbered non-repetitive enumeration and the formation of outcomes of the scheme. The iterative development of the process is represented by a probabilistic graph. The study of the outcomes of the scheme according to the model in the enumerative method is carried out in the following areas: visual numbering of the outcomes of the scheme, finding their number, establishing a one-to-one correspondence between the types and numbers of outcomes of the scheme, obtaining their probabilistic distribution (controlled by a random process of listing the outcomes of the scheme), and modeling them with this distribution. Along with the direct study of circuits in these areas, algorithms are proposed to obtain results for them by partially recalculating them from the results of a similar analysis of more general, previously studied circuits without restrictions or with less restrictions on the values of the characteristics under consideration.
Keywords: inverse extremal problem, extremal value of a characteristic, pre-asymptotic analysis of a circuit. 
N. Yu. Enatskaya. Probabilistic models for the analysis of inverse extremal problems in combinatorics. Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences, Tome 26 (2022) no. 3, pp. 573-591. http://geodesic.mathdoc.fr/item/VSGTU_2022_26_3_a8/
@article{VSGTU_2022_26_3_a8,
     author = {N. Yu. Enatskaya},
     title = {Probabilistic models for the analysis of inverse extremal problems in combinatorics},
     journal = {Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences},
     pages = {573--591},
     year = {2022},
     volume = {26},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSGTU_2022_26_3_a8/}
}
TY  - JOUR
AU  - N. Yu. Enatskaya
TI  - Probabilistic models for the analysis of inverse extremal problems in combinatorics
JO  - Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences
PY  - 2022
SP  - 573
EP  - 591
VL  - 26
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VSGTU_2022_26_3_a8/
LA  - ru
ID  - VSGTU_2022_26_3_a8
ER  - 
%0 Journal Article
%A N. Yu. Enatskaya
%T Probabilistic models for the analysis of inverse extremal problems in combinatorics
%J Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences
%D 2022
%P 573-591
%V 26
%N 3
%U http://geodesic.mathdoc.fr/item/VSGTU_2022_26_3_a8/
%G ru
%F VSGTU_2022_26_3_a8

[1] Afanas'ev M. Yu., Suvorov B. P., Issledovanie operatsii v ekonomike. Modeli, zadachi, resheniia [Operations Research in Economics. Models, Tasks, Solutions], INFRA-M, Moscow, 2003, 202 pp. (In Russian)

[2] Baranov V. I., Stechkin B. S., Ekstremal'nye kombinatornye zadachi i ikh prilozheniia [Extremal Combinatorial Problems and Their Applications], Fizmatlit, Moscow, 2004, 240 pp. (In Russian)

[3] Kolchin V. F., “On the limiting behavior of extreme order statistics in a polynomial scheme”, Theory Probab. Appl., 14:3 (1969), 458–469 | DOI | MR | Zbl

[4] Khakimullin E.R., “Asymptotic behavior of the maximum occupancy in an equiprobable scheme of allocation of particles by complexes”, Math. Notes, 30:2 (1981), 626–633 | DOI | MR | Zbl

[5] Viktorova I. I., “Asymptotic behavior of maximum of an equiprobable polynomial scheme”, Math. Notes, 5:3 (1969), 184–191 | DOI | MR | Zbl

[6] Enatskaya N. Yu., “Probabilistic models of combinatorial schemes”, Bulletin of the South Ural State University, Ser. Mathematical Modelling, Programming and Computer Software, 13:3 (2020), 103–111 (In Russian) | DOI

[7] Enatskaya N. Yu., “Analysis of combinatorial schemes in the pre-asymptotic region of parameter change”, Proceedings of the Karelian Research Centre of the Russian Academy of Sciences, 2018, no. 7, 117–133 (In Russian) | DOI