{"id":"arxiv/2608.13318","url":"https://arxiv.org/abs/2608.13318","tags":["cs.DS","math.OC"],"score":0,"title":"A minimum witness for the 3/2 configuration-linear-program gap in two-weight graph balancing, unique at its size","domain":"cs.DS","source":"arxiv","authors":["Adam Y. Shavit"],"reviews":0,"subject":"cs.DS","summary":"Restricted assignment minimizes makespan, the busiest machine's load, when each job has one size and a set of allowed machines. Its tightest studied relaxation is the configuration linear program, which fractionally gives each machine whole job sets that fit. Its integrality gap, the worst-case ratio of integral optimum to relaxation value, is open in general. On two-weight graph balancing (sizes 1 and 2, each job allowed on at most two machines) the gap is known: Jansen, Land, and Maack (2016) give both bounds. Their Table 1 instance attains 3/2, and their Corollary 11 bound of 2-s/b for…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-13","reactions":{}}