Hartke's integrality gap conjecture for trees with at most 12 vertices
Hartke's integrality gap conjecture for trees with at most 12 vertices
Let be a tree, and consider the linear program obtained from the MacGillivray–Wang integer program for virus spread by relaxing to a linear constraint and adding constraint (6):
for each vertex and . Hartke's integrality gap conjecture. The tree in Figure~ is the smallest tree such that the LP optimum under constraint (6) differs from the integer-program optimum. Equivalently, the strengthened linear program realizes the integer-program optimum for every tree with at most 12 vertices. The conjecture concerns the occurrence of integrality gaps: the displayed 13-vertex tree has LP optimum and integer-program optimum , while the claim asserts that no smaller tree has such a gap.
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
Andrea Barnett, Robert Bond, Anthony Macias, Thomas W. Mattman, Bill Parnell and Ely Schoenfield, “COVID on trees and infinite grids”, arXiv:2409.14303 (2024).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.