Some Notes about Arrangements of Points on Quadrics
https://doi.org/10.18255/1818-1015-2012-4-72-77
Abstract
It is considered the minimization of a quadratic polynomial on the set of all points of a multidimensional space, coordinates of which are either zero or one. Some restrictions are imposed on the arrangement of the minimum points when there are many such points.
combinatorial optimization, quadratic programming, empty quadric, polytope, facet
About the Author
A. V. Seliverstov
Институт проблем передачи информации им. А. А. Харкевича РАН
Russian Federation
старший научный сотрудник, кандидат физико-математических наук
Russian Federation
старший научный сотрудник, кандидат физико-математических наук
References
1. Береснев В. Л. Дискретные задачи размещения и полиномы от булевых переменных. Новосибирск: Издательство Института математики, 2005. 408 с.
2. Billionnet A., Elloumi S. Using a mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem // Mathematical programming. Ser. A. 2007. V. 109. №1. P. 55–68.
3. Ahlat¸cio˘glu 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 // Annals of operations research. 2012. V. 199. №1. P. 33–49.
4. Емеличев В. А., Коротков В. В. Об устойчивости лексикографического решения векторной минимаксной квадратичной булевой задачи // Тр. Института матем. НАН Беларуси. 2011. Т. 19. №2. С. 26–36.
5. Емеличев В. А., Ковалев М. М., Кравцов М. К. Многогранники, графы, оптимизация. М.: Наука, 1981. 344 с.
6. Padberg M. The boolean quadric polytope: some characteristics, facets and relatives // Mathematical programming. 1989. V. 45. №1–3. P. 139–172.
7. Максименко А. Н. О числе фасет 2-смежностного многогранника // Модел. и анализ информ. систем. 2010. Т. 17. №1. С. 76–82.
8. Деза М., Лоран М. Геометрия разрезов и метрик. М.: МЦНМО, 2001. 736 с.
9. Zhao W., Posner M. E. A large class of facets for the K-median polytope // Mathematical programming. Ser. A. 2011. V. 128. №1–2. P. 171–203.
10. Galli L., Kaparis K., Letchford A. N. Gap inequalities for non-convex mixed-integer quadratic programs // Operations research letters. 2011. V. 39. №5. P. 297–300.
11. Николаев А. В. Гиперграфы специального вида и анализ свойств релаксаций разрезного многогранника // Модел. и анализ информ. систем. 2011. Т. 18. №3. С. 82–100.
12. Делоне Б. Н. Геометрия положительных квадратичных форм // УМН. 1937. №3. С. 16–62.
13. Селиверстов А. В., Любецкий В. А. О симметричных матрицах с неопределенной главной диагональю // Пробл. передачи информ. 2009. Т. 45. №3. C. 73–78.
14. Селиверстов А. В., Любецкий В. А. О формах, равных нулю в каждой вершине куба // Информационные процессы. 2011. Т. 11. №3. С. 330–335. Электронный научный журнал http://www.jip.ru
15. Costello K. P., Vu V. H. The rank of random graphs // Random structures and algorithms. 2008. V. 33. №3. P. 269–285.
Review
For citations:
Seliverstov A.V. Some Notes about Arrangements of Points on Quadrics. Modeling and Analysis of Information Systems. 2012;19(4):72-77. (In Russ.) https://doi.org/10.18255/1818-1015-2012-4-72-77
Views:
804
Email this article 