Volume 22, No 2, 2015, P. 86–101
UDC 519.1
R. Yu. Simanchev, I. V. Urazova
On the faces of the graph approximation problem polytope
Abstract:
We study the polytope of the graph approximation problem. The polyhedral relaxation of this polytope is built. We describe the class of valid inequalities for this polytope among which the inequalities that generate facets are allocated.
Ill. 1, bibliogr. 9.
Keywords: stability of the solution, stability radius, Boolean polynomial, matroid, geometric configuration.
DOI: 10.17377/daio.2015.22.469
Ruslan Yu. Simanchev 1,2
Inna V. Urazova 1
1. Omsk State University,
55–a Mira Ave., 644077 Omsk, Russia
2.
Omsk Scientific Center, SB RAS,
15/1 K. Marx Ave., 644024 Omsk, Russia
å-mail: osiman@rambler.ru , urazovainn@mail.ru
Received 11 December 2014
Revised 31 January 2015
References
[1] V. A. Emelichev, M. M. Kovalev, andM. K. Kravtsov, Mnogogranniki. Grafy. Optimizatsiya (Polyhedra. Graphs. Optimization), Nauka, Moscow, 1981.[2] V. P. Il’ev, S. D. Il’eva, and A. A. Navrotskaya, Approximation algorithms for graph approximation problems, Diskretn. Anal. Issled. Oper., 18, No. 1, 41–60, 2011. Translated in J. Appl. Ind. Math., 5, No. 4, 569–581, 2011.
[3] V. P. Il’ev and G. Sh. Fridman, On the problem of approximation by graphs with a fixed number of components, Dokl. Akad. Nauk SSSR, 264, No. 3, 533–538, 1982. Translated in Sov. Math., Dokl., 25, 666–670, 1982.
[4] A. V. Seliverstov, Polytopes and connected subgraphs, Diskretn. Anal. Issled. Oper., 21, No. 3, 82–86, 2014.
[5] R. Yu. Simanchev and N. Yu. Shereshik, Integer models for the interrupt-oriented services of jobs by single machine, Diskretn. Anal. Issled. Oper., 21, No. 4, 89–101, 2014.
[6] A. Schrijver, Theory of Linear and Integer Programming, Vol. 2, John Wiley & Sons, New York, 1986. Translated under the title Teoriya lineinogo i tselochislennogo programmirovaniya, Vol. 2, Mir, Moscow, 1991.
[7] G. Sh. Fridman, A problem of graph approximation, Upr. Sist., 8, 73–75, 1971.
[8] M. Grötschel, O. Holland, Solution of large-scale symmetric travelling salesman problems, Math. Program., Ser. A, 51, No. 1–3, 141–202, 1991.
[9] R. Shamir, R. Sharan, and D. Tsur, Cluster graph modification problems, Discrete Appl. Math., 144, No. 1–2, 173–182, 2004.
