Оценки числа вершин целых полиэдров

S. I. Veselov ; A. Yu. Chirkov

Diskretnyj analiz i issledovanie operacij, Tome 14 (2007) no. 2, pp. 14-31.

Bibliographie

[1] Brensted A., Vvedenie v teoriyu vypuklykh mnogogrannikov, Mir, M., 1988 | MR

[2] Veselov S. I., Nizhnyaya otsenka srednego chisla neprivodimykh i krainikh tochek v dvukh zadachakh diskretnogo programmirovaniya, deponirovano v VINITI, No 619–V84, Gorkovskii gos. un-t, M., 1984, 8 pp.

[3] Veselov S. I., Nakhozhdenie vypukloi obolochki tselykh tochek poliedra na ploskosti, deponirovano v VINITI, No 8624–V88, Gorkovskii gos. un-t, M., 1988, 12 pp.

[4] Veselov S. I., Shevchenko V. N., O chisle ekstremalnykh tochek kvadratnoi sistemy lineinykh neravenstv, deponirovano v VINITI, No 450–79, Gorkovskii gos. un-t, M., 1979, 10 pp.

[5] Veselov S. I., Shevchenko V. N., “Otsenki minimalnogo rasstoyaniya mezhdu tochkami nekotorykh tselochislennykh reshetok”, Kombinatorno-algebraicheskie metody v prikladnoi matematike, Gorkovskii gos. un-t, Gorkii, 1980, 26–33 | MR | Zbl

[6] Vinogradov I. M., Osnovy teorii chisel, Nauka, M., 1972 | MR

[7] Emelichev V. A., Kovalev M. M., Kravtsov M. K., Mnogogranniki, grafy, optimizatsiya, Nauka, M., 1981 | MR

[8] Klein F., Elementarnaya matematika s tochki zreniya vysshei. V 2-kh tomakh. T. 1. Arifmetika. Algebra. Analiz, Nauka, M., 1987 | MR

[9] Preparata F., Sheimos M., Vychislitelnaya geometriya. Vvedenie, Mir, M., 1989 | MR | Zbl

[10] Skhreiver A., Teoriya lineinogo i tselochislennogo programmirovaniya, T. 2, Mir, M., 1991

[11] Khu T., Tselochislennoe programmirovanie i potoki v setyakh, Mir, M., 1974 | MR

[12] Chirkov A. Yu., “O chisle krainikh tochek v zadache tselochislennogo lineinogo programmirovaniya”, Kombinatorno-algebraicheskie metody v diskretnoi optimizatsii, Nizhegorodskii gos. universitet, Nizhnii Novgorod, 1991, 157–159

[13] Chirkov A. Yu., Teorema Karateodori i pokrytie mnogogrannika simpleksami, deponirovano v VINITI, No 668–V93, Nizhegorodskii gos. un-t, M., 1993, 12 pp.

[14] Chirkov A. Yu., “O nizhnei otsenke chisla vershin vypukloi obolochki tselochislennykh i chastichno tselochislennykh tochek poliedra”, Diskret. analiz i issled. operatsii, 3:2 (1996), 80–89 | MR | Zbl

[15] Chirkov A. Yu., “O svyazi chisla vershin vypukloi obolochki tselochislennykh tochek poliedra s ego metricheskimi kharakteristikami”, Trudy 2-i mezhdunarodnoi konferentsii “Matematicheskie algoritmy”, Nizhnii Novgorod, 1997, 169–174

[16] Chirkov A. Yu., Shevchenko V. N., deponirovano v VINITI, No 2165–V93, Nizhegorodskii gos. un-t, M., 1993, 12 pp.

[17] Shevchenko V. N., “O chisle krainikh tochek v tselochislennom programmirovanii”, Kibernetika, 1981, no. 2, 133–134 | Zbl

[18] Shevchenko V. N., “Algebraicheskii podkhod v tselochislennom programmirovanii”, Kibernetika, 1984, no. 4, 36–41 | MR | Zbl

[19] Shevchenko V. N., “Verkhnie otsenki chisla krainikh tochek v tselochislennom programmirovanii”, Matematicheskie voprosy kibernetiki, Vyp. 4, Nauka, M., 1992, 65–72 | MR

[20] Shevchenko V. N., Kachestvennye voprosy tselochislennogo programmirovaniya, Fizmatlit, M., 1995 | MR | Zbl

[21] Barany I.,Howe R., Lovasz L., “On integer points in polyhedra: a lower bound”, Combinatorica, 12:2 (1992), 135–142 | DOI | MR | Zbl

[22] Cook W., Gerards A. M. H., Schrijver A., Tardos E., “Sensitivity theorems in integer linear programming”, Mathematical Programming, 34:3 (1986), 251–264 | DOI | MR | Zbl

[23] Cook W., Hartmann M., Kannan R., McDiarmid C., “On integer points in polyhedra”, Combinatorica, 12:1 (1992), 27–37 | DOI | MR | Zbl

[24] Hayes A. C., Larman D. G., “The vertices of the knapsack polytope”, Discrete Applied Math., 6:2 (1983), 135–138 | DOI | MR | Zbl

[25] Morgan D. A., “Upper and lower bound results on the convex hull of integer points in polyhedra”, Mathematika, 38:2 (1991), 321–328 | MR | Zbl

[26] Rubin D. S., “On the unlimited number of faces in integer hulls of linear programs with a single constraint”, Operations Research, 18:5 (1970), 940–945 | DOI | MR