Geodesic
Discrete optimization problems with interval parameters
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 5, pp. 836-847 
V. A. Perepelitsa; F. B. Tebueva. Discrete optimization problems with interval parameters. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 5, pp. 836-847. http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_5_a4/
@article{ZVMMF_2010_50_5_a4,
     author = {V. A. Perepelitsa and F. B. Tebueva},
     title = {Discrete optimization problems with interval parameters},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {836--847},
     year = {2010},
     volume = {50},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_5_a4/}
}
TY  - JOUR
AU  - V. A. Perepelitsa
AU  - F. B. Tebueva
TI  - Discrete optimization problems with interval parameters
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2010
SP  - 836
EP  - 847
VL  - 50
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_5_a4/
LA  - ru
ID  - ZVMMF_2010_50_5_a4
ER  - 
%0 Journal Article
%A V. A. Perepelitsa
%A F. B. Tebueva
%T Discrete optimization problems with interval parameters
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2010
%P 836-847
%V 50
%N 5
%U http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_5_a4/
%G ru
%F ZVMMF_2010_50_5_a4

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

Optimization problems on graphs with interval parameters are considered, and exponential and polynomial bounds for their computational complexity are obtained. For a certain subclass of polynomially solvable problems, two algorithms are proposed—one of them for finding an optimal solution and the other one for finding a suboptimal solution. Sufficient conditions for the statistical efficiency of the algorithm for finding a suboptimal solution are obtained.

[1] Alefeld G., Khertsberger Yu., Vvedenie v intervalnye vychisleniya, Mir, M., 1987 | MR

[2] Shokin Yu. I., Intervalnyi analiz, SO Nauka, Novosibirsk, 1981 | Zbl

[3] Hammer R., Hocks M., Kulisch U., Ratz D., Numerical toolbox for verified computing, v. I, Basic numerical problems, Springer, Berlin etc., 1993 | MR

[4] Neumaier A., Introduction to numerical analysis, Cambridge Univ. Press, Cambridge, 2001 | MR | Zbl

[5] Moore R. E., Kearfott R. B., Cloud M. J., Introduction to interval analysis, SIAM, Philadelphia, 2009 | MR | Zbl

[6] Kuznetsov V. P., Intervalnye statisticheskie modeli, Radio i svyaz, M., 1991 | MR

[7] Perepelitsa V. A., Kozina G. L., “Interval discrete models and multiodjectivity”, Interval Comput., 1993, no. 1 | MR | Zbl

[8] Voschinin A. P., Sotirov G. R., Optimizatsiya v usloviyakh neopredelennosti, Nauka, M., 1989

[9] Aschepkov L. T., Davydov D. V., “Pokazatel intervalnogo neravenstva: svoistva i primenenie”, Vychisl. tekhnologii, 11:4 (2006), 13–22 | Zbl

[10] Levin V. I., “Sravnenie intervalnykh velichin i optimizatsiya neopredelennykh sistem”, Informatsionnye tekhnologii, 1998, no. 7, 22–32

[11] Berzh K., Teoriya grafov i ee primeneniya, Izd-vo inostr. lit., M., 1962

[12] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lektsii po teorii grafov, Nauka, M., 1990 | MR | Zbl

[13] Claudio D. M., Escadro M. H., Franciosi B. T., “An order-theoretic approach to interval analysis”, Interval Comput., 1992, no. 3 | MR

[14] Kim Gyu Pkhir, “Optimalnoe raspredelenie resursa v usloviyakh intervalnoi neopredelennosti”, Sb. trudov, Mezhdunar. konf. po intervalnym i stokhastich. metodam v nauke i tekhn. (INTERVAL-92), v. 1, M., 1992

[15] Perepelitsa V. A., Tolok V. A., “Application of vector optimization methods for analysis of interval methods”, Internat. Kolloquium über Anvendungen der Informatik und der Mathematik in Architektur und Bauwesen (Weimar, 1994), Hochschule für Architektur und Bauwesen Weimar Universitat, 1994

[16] Podinovskii V. V., Nogin V. D., Pareto-optimalnye resheniya mnogokriterialnykh zadach, Nauka, M., 1982 | MR

[17] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR

[18] Perepelitsa V. A., Mamedov A. Z., Issledovanie slozhnosti i razreshimosti vektornykh zadach na grafakh, Uch. posobie, RIO KChTI, Cherkessk, 1995

[19] Emelichev V. A., Perepelitsa V. A., “Slozhnost diskretnykh mnogokriterialnykh zadach”, Diskretnaya matem., 6:1 (1994)

[20] Akho A., Khopkroft Dzh., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979 | MR

[21] Beresnev V. A., Gimadi E. Kh., Dementev V. T., Ekstremalnye zadachi standartizatsii, Nauka, SO, Novosibirsk, 1978 | MR

[22] Girlikh E., Kovalev M. M., Kravtsov M. K., Yanushkevich O. A., “Usloviya razreshimosti vektornykh zadach s pomoschyu lineinoi svertki kriteriev”, Kibernetika i sistemnyi analiz, M., 1999 | Zbl

[23] Korshunov A. D., “Osnovnye svoistva sluchainykh grafov s bolshim chislom vershin i reber”, Uspekhi matem. nauk, 40:1(241) (1985) | MR