A minimum witness for the 3/2 configuration-linear-program gap in two-weight graph balancing, unique at its size
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.13318
curl -X POST /api/v1/records/arxiv/2608.13318/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.13318/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'