Geodesic
On the faces of the graph approximation problem polytope
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 2, pp. 86-101.

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

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, matroid, geometric configuration.
Mots-clés : Boolean polynomial 
@article{DA_2015_22_2_a6,
     author = {R. Yu. Simanchev and I. V. Urazova},
     title = {On the faces of the graph approximation problem polytope},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {86--101},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_2_a6/}
}
TY  - JOUR
AU  - R. Yu. Simanchev
AU  - I. V. Urazova
TI  - On the faces of the graph approximation problem polytope
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 86
EP  - 101
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_2_a6/
LA  - ru
ID  - DA_2015_22_2_a6
ER  - 
%0 Journal Article
%A R. Yu. Simanchev
%A I. V. Urazova
%T On the faces of the graph approximation problem polytope
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 86-101
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_2_a6/
%G ru
%F DA_2015_22_2_a6
R. Yu. Simanchev; I. V. Urazova. On the faces of the graph approximation problem polytope. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 2, pp. 86-101. http://geodesic.mathdoc.fr/item/DA_2015_22_2_a6/

[1] V. A. Emelichev, M. M. Kovalev, M. K. Kravtsov, Polyhedra. Graphs. Optimization, Nauka, Moscow, 1981, 344 pp. | MR

[2] Il'ev V. P., Il'eva S. D., Navrotskaya A. A., “Approximation algorithms for graph approximation problems”, J. Appl. Ind. Math., 5:4 (2011), 569–581 | DOI | MR | Zbl

[3] Il'ev V. P., Fridman G. Sh., “On the problem of approximation by graphs with a fixed number of components”, Sov. Math., Dokl., 25 (1982), 666–670 | MR | Zbl

[4] A. V. Seliverstov, “Polytopes and connected subgraphs”, Diskretn. Anal. Issled. Oper., 21:3 (2014), 82–86 | MR

[5] R. Yu. Simanchev, N. Yu. Shereshik, “Integer models for the interrupt-oriented services of jobs by single machine”, Diskretn. Anal. Issled. Oper., 21:4 (2014), 89–101 | MR

[6] Schrijver A., Theory of Linear and Integer Programming, v. 2, John Wiley Sons, New York, 1986 | MR | Zbl

[7] G. Sh. Fridman, “A problem of graph approximation”, Upr. Sist., 8, 1971, 73–75

[8] Grotschel M., Holland O., “Solution of large-scale symmetric travelling salesman problems”, Math. Programming, 51:2 (1991), 141–202 | DOI | MR | Zbl

[9] Shamir R., Sharan R., Tsur D., “Cluster graph modification problems”, Discrete Appl. Math., 144:1–2 (2004), 173–182 | DOI | MR | Zbl