Geodesic
On monomials in quadratic forms
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 3, pp. 65-70.

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

There are proved some restrictions on the zero-nonzero pattern of entries in a matrix of the real quadratic form which reaches its minimum value on a large set of vertices of the multidimensional cube centered at the origin whose edges are parallel to the coordinate axes. In particular, if the graph of the matrix contains an articulation point then the set of minima of the corresponding quadratic form is not maximal (with respect to set inclusion) among all such sets for various quadratic forms. Bibliogr. 21.
Keywords: combinatorial optimization, quadratic form, polytope, graph
Mots-clés : facet, matrix. 
@article{DA_2013_20_3_a3,
     author = {A. V. Seliverstov},
     title = {On monomials in quadratic forms},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {65--70},
     publisher = {mathdoc},
     volume = {20},
     number = {3},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2013_20_3_a3/}
}
TY  - JOUR
AU  - A. V. Seliverstov
TI  - On monomials in quadratic forms
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2013
SP  - 65
EP  - 70
VL  - 20
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2013_20_3_a3/
LA  - ru
ID  - DA_2013_20_3_a3
ER  - 
%0 Journal Article
%A A. V. Seliverstov
%T On monomials in quadratic forms
%J Diskretnyj analiz i issledovanie operacij
%D 2013
%P 65-70
%V 20
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2013_20_3_a3/
%G ru
%F DA_2013_20_3_a3
A. V. Seliverstov. On monomials in quadratic forms. Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 3, pp. 65-70. http://geodesic.mathdoc.fr/item/DA_2013_20_3_a3/

[1] Beresnev V. L., Diskretnye zadachi razmescheniya i polinomy ot bulevykh peremennykh, Izd-vo in-ta matematiki, Novosibirsk, 2005, 408 pp.

[2] Beresnev V. L., “Algoritmy lokalnogo poiska dlya zadachi konkurentnogo razmescheniya predpriyatii”, Avtomatika i telemekhanika, 2012, no. 3, 12–27

[3] Beresnev V. L., Goncharov E. N., Melnikov A. A., “Lokalnyi poisk po obobschënnoi okrestnosti dlya zadachi optimizatsii psevdobulevykh funktsii”, Diskret. analiz i issled. operatsii, 18:4 (2011), 3–16 | MR | Zbl

[4] Gorbunov K. Yu., Seliverstov A. V., Lyubetskii V. A., “Vzaimnoe raspolozhenie parallelnykh giperploskostei, kvadrik i vershin mnogomernogo kuba”, Probl. peredachi inform., 48:2 (2012), 113–120

[5] Kolokolov A. A., Orlovskaya T. G., Rybalka M. F., “Analiz algoritmov tselochislennogo programmirovaniya s ispolzovaniem $L$-razbieniya i unimodulyarnykh preobrazovanii”, Avtomatika i telemekhanika, 2012, no. 2, 178–190

[6] Maksimenko A. N., “Mnogogranniki zadachi o vypolnimosti yavlyayutsya granyami mnogogrannika zadachi kommivoyazhëra”, Diskret. analiz i issled. operatsii, 18:3 (2011), 76–83 | MR | Zbl

[7] Maksimenko A. N., “Analog teoremy Kuka dlya mnogogrannikov”, Izv. vuzov. Matematika, 2012, no. 8, 34–42 | Zbl

[8] Seliverstov A. V., “Zamechaniya o raspolozheniyakh tochek na kvadrikakh”, Modelirovanie i analiz inform. sistem, 19:4 (2012), 72–77

[9] Seliverstov A. V., Lyubetskii V. A., “O simmetrichnykh matritsakh s neopredelennoi glavnoi diagonalyu”, Probl. peredachi inform., 45:3 (2009), 73–78 | MR | Zbl

[10] Seliverstov A. V., Lyubetskii V. A., “O formakh, ravnykh nulyu v kazhdoi vershine kuba”, Informatsionnye protsessy, 11:3 (2011), 330–335

[11] Skhreiver A., Teoriya lineinogo i tselochislennogo programmirovaniya, v. 1, Mir, M., 1991, 360 pp. | MR

[12] Ahlatçioğlu A., Bussieck M., Esen M., Guignard M., Jagla J.-H., Meeraus A., “Combining QCR and CHR for convex quadratic pure 0–1 programming problems with linear constraints”, Ann. Oper. Res., 199:1 (2012), 33–49 | DOI | MR | Zbl

[13] Avis D., “Computational experience with the reverse search vertex enumeration algorithm”, Optim. Methods Softw., 10:2 (1998), 107–124 | DOI | MR | Zbl

[14] Avis D., Fukuda K., “A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra”, Discrete Comput. Geom., 8:1 (1992), 295–313 | DOI | MR | Zbl

[15] Billera L. J., Sarangarajan A., “All 0-1 polytopes are traveling salesman polytopes”, Combinatorica, 16:2 (1996), 175–188 | DOI | MR | Zbl

[16] Billionnet A., Elloumi S., “Using a mixed integer quadratic programming solver for the unconstrained quadratic 0–1 problem”, Math. Program., 109:1 (2007), 55–68 | DOI | MR | Zbl

[17] Fukasawa R., Goycoolea M., “On the exact separation of mixed integer knapsack cuts”, Math. Program., 128:1–2 (2011), 19–41 | DOI | MR | Zbl

[18] Galli L., Kaparis K., Letchford A. N., “Gap inequalities for non-convex mixed-integer quadratic programs”, Oper. Res. Lett., 39:5 (2011), 297–300 | MR | Zbl

[19] Padberg M., “The boolean quadric polytope: some characteristics, facets, and relatives”, Math. Program., 45:1–3 (1989), 139–172 | DOI | MR | Zbl

[20] Tamir A., “New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems”, Oper. Res. Lett., 37:5 (2009), 303–306 | DOI | MR | Zbl

[21] Wang Y., Lü Z., Glover F., Hao J.-K., “Path relinking for unconstrained binary quadratic programming”, Eur. J. Oper. Res., 223:3 (2012), 595–604 | DOI | MR