Facet-defining conjecture for clique inequalities in the two-level graph partitioning polytope
Facet-defining conjecture for clique inequalities in the two-level graph partitioning polytope
Let be the graph and let be the partition parameters, with , , and as defined for the corresponding clique inequalities. For a clique , write and for the associated clique expressions. Facet-defining conjecture. The following results hold for the convex hull of 2L-PP solutions: the -clique inequalities define facets if and only if ; the -clique inequalities define facets if and only if ; and the -clique inequalities define facets if and only if . This conjecture would characterize exactly when the three newly studied families of clique inequalities are facet-defining, strengthening the preceding necessary conditions for non-domination; the source reports only computational evidence from PORTA, so the general assertions remain open.
Sources & referencesView supporting material
Primary source
Jamie Fairbrother, Adam Letchford and Keith Briggs, “A Two-Level Graph Partitioning Problem Arising in Mobile Wireless Communications”, arXiv:1705.08773 (2017).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.