Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope
RAIRO - Operations Research - Recherche Opérationnelle, Volume 50 (2016) no. 3, pp. 627-644.

In a previous work we presented six facet-inducing families of valid inequalities for the polytope associated to an integer programming formulation of the acyclic coloring problem. In this work we study their disjunctive rank, as defined by [E. Balas, S. Ceria and G. Cornuéjols, Math. Program. 58 (1993) 295–324]. We also propose to study a dual concept, which we call the disjunctive anti-rank of a valid inequality.

Received:
Accepted:
DOI: 10.1051/ro/2015053
Classification: 90C10, 05C15
Keywords: Acyclic coloring, disjunctive rank
Braga, Mónica 1; Marenco, Javier 1

1 Sciences Institute, National University of General Sarmiento J.M. Gutierrez 1150, (B1613 GSX) Los Polvorines, Argentina.
@article{RO_2016__50_3_627_0,
     author = {Braga, M\'onica and Marenco, Javier},
     title = {Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {627--644},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {3},
     year = {2016},
     doi = {10.1051/ro/2015053},
     zbl = {1378.90058},
     mrnumber = {3538844},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2015053/}
}
TY  - JOUR
AU  - Braga, Mónica
AU  - Marenco, Javier
TI  - Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 627
EP  - 644
VL  - 50
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2015053/
DO  - 10.1051/ro/2015053
LA  - en
ID  - RO_2016__50_3_627_0
ER  - 
%0 Journal Article
%A Braga, Mónica
%A Marenco, Javier
%T Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 627-644
%V 50
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2015053/
%R 10.1051/ro/2015053
%G en
%F RO_2016__50_3_627_0
Braga, Mónica; Marenco, Javier. Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope. RAIRO - Operations Research - Recherche Opérationnelle, Volume 50 (2016) no. 3, pp. 627-644. doi : 10.1051/ro/2015053. http://archive.numdam.org/articles/10.1051/ro/2015053/

N. Aguilera, S. Bianchi and G. Nasini, Relaciones entre los rangos de las facetas de problemas asociados a matching. Proc. of the XVIII JAIIO (1999) 10–21.

N. Alon, C. Mcdiarmid and B. Reed, Acyclic colouring of graphs. Random Struct. and Algorithms 2 (1991) 277–288. | DOI | MR | Zbl

Y. Au and L. Tunçel, On the polyhedral lift-and-project methods and the fractional stable set polytope. Discrete Optim. 6 (2009) 206–213. | DOI | MR | Zbl

Y. Au and L. Tunçel, A comprehensive analysis of polyhedral lift-and-project methods. Manuscript (2013).

E. Balas, S. Ceria and G. Cornuéjols, Lift-and-Project Cutting Plane Algorithm for Mixed 0 - 1 Programs. Math. Program. 58 (1993) 295–324. | DOI | MR | Zbl

O.V. Borodin, On acyclic colorings of planar graphs. Discrete Math. 25 (1979) 211–236. | DOI | MR | Zbl

O.V. Borodin, A.V. Kostochka and D.R. Woodall, Acyclic colourings of planar graphs with large girth. J. London Math. Soc. 2 (1999) 344-352. | DOI | MR | Zbl

O.V. Borodin, A.V. Kostochka, A. Raspaud and E. Sopena, Acyclic colouring of 1-planar graphs. Discrete Appl. Math. 114 (2001) 29–41. | DOI | MR | Zbl

M. Braga and J. Marenco, Disjunctive ranks and anti-ranks of some facet-inducing inequalities of the acyclic coloring polytope. Electron. Notes Discrete Math. 37 (2011) 213–218. | DOI | MR | Zbl

M. Braga, D. Delle Donne and J. Marenco, A polyhedral study of the acyclic coloring problem. Discrete Appl. Math. 160 (2012) 2606–2617. | DOI | MR | Zbl

M.I. Burnstein, Every 4-valent graph has an acyclic 5-coloring. Soobsc Akad. Nauk Gruzin SSR 93 (1979) 21–24. | MR | Zbl

T.F. Coleman and J. Cai, The cyclic coloring problem and estimation of sparse Hessian matrices. SIAM J. Alg. Disc. Meth. 7 (1986) 221–235. | DOI | MR | Zbl

T.F. Coleman and J.J. More, Estimation of sparse Jacobian matrices and graph coloring problems. SIAM J. Numer. Anal. 20 (1983) 187–209. | DOI | MR | Zbl

G. Fertin and A. Raspaud, Acyclic Coloring of Graphs of Maximum Degree Five: Nine Colors are Enough. Inf. Process. Lett. 105 (2008) 65–72. | DOI | MR | Zbl

A.H. Gebremedhin, F. Manne and A. Pothen. What color is your Jacobian? Graph coloring for computing derivatives. SIAM Rev. 47 (2005) 629–705. | DOI | MR | Zbl

A.H. Gebremedhin, A. Tarafdar, F. Manne and A. Pothen, New Acyclic and Star Coloring Algorithms with Application to Computing Hessians. SIAM J. Sci. Comput. 29 (2007) 1042–1072. | DOI | MR | Zbl

A.H. Gebremedhin, A. Tarafdar, A. Pothen and A. Walther, Efficient Computation of Sparse Hessians Using Coloring and Automatic Differentiation. INFORMS J. Comput. 21 (2009) 209–223. | DOI | MR | Zbl

B. Grünbaum, Acylic colorings of planar graphs. Israel J. Math. 14 (1973) 390-408. | DOI | MR | Zbl

J. Lasserre, An explicit exact SDP relaxation for nonlinear 0-1 programs. Vol. 2081 of Lect. Notes Comput. Sci. (2001) 293–303. | MR | Zbl

M. Laurent, A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming. Math. Oper. Res. 28 (2003) 470–496. | DOI | MR | Zbl

V. Leoni and G. Nasini, On the relationship between disjunctive relaxations and minors in packing and covering problems. Revista de la Unión Matemática Argentina 46 (2005) 11–22. | MR | Zbl

I. Loiseau, I. Méndez Díaz and G. Nasini, Determinación del rango disyuntivo de facetas del problema de ordenación lineal. Proc. of the XXII JAIIO (1993) 124–130.

L. Lovász and A. Schrijver, Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1 (1991) 166–190. | DOI | MR | Zbl

C. Mathieu and A. Sinclair, Sherali-Adams relaxations of the matching polytope. Proc. of STOC’09 (2009) 293–302. | MR | Zbl

I. Méndez Díaz and G. Nasini, El problema del ordenamiento lineal y el operador BCC. Proc. of the XVIII JAIIO (1999) 22–32.

T. Rothvoß, The Lasserre hierarchy in approximation algorithms. MAPSP 2013 tutorial (2013).

H. Sherali and W. Adams, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3 (1990) 411–430. | DOI | MR | Zbl

Cited by Sources: