The minor inequality facet conjecture for circulant set covering polyhedra

From papers

Let CnkC_n^k be a circulant matrix, let WZnW\subset\mathbb Z_n define a relevant circulant minor isomorphic to CnkC_{n'}^{k'}, and let Q(Cnk)Q(C_n^k) denote the associated set covering polyhedron. The corresponding minor inequality is

iW2xi+iWxink.\sum_{i\in W}2x_i+\sum_{i\notin W}x_i\geq\left\lceil\frac{n'}{k'}\right\rceil.

Here, WW is relevant when n0(modk)n'\neq0\pmod {k'} and n/k>n/k\left\lceil n'/k'\right\rceil>\left\lceil n/k\right\rceil. The minor inequality facet conjecture. A relevant minor inequality corresponding to a minor of CnkC_n^k isomorphic to CnkC_{n'}^{k'} defines a facet of Q(Cnk)Q(C_n^k) if and only if n=1(modk)n'=1\pmod {k'}. The conjecture seeks a complete characterization of when these non-boolean, non-rank inequalities are facet defining; the supplied source gives no evidence of resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Silvia M. Bianchi, Graciela L. Nasini and Paola B. Tolomei, “The Minor inequalities in the description of the Set Covering Polyhedron of Circulant Matrices”, arXiv:1206.1300 (2012).

Solutions 0

No solutions have been posted yet.