Minimum-makespan completion and vertex selection leave the Wang-Sitters constant at 11/6
Wang and Sitters' rounding scheme for graph balancing (each job allowed on at most two machines) keeps the makespan, the busiest machine's load, within 11/6 of the optimum, and a companion note shows that no smaller constant holds. One suspected cause is Step 3's freedom to match leftover jobs to slots in any valid way. We show that removing that freedom does not improve the constant. An idealized oracle that always picks the valid matching with the smallest makespan still has worst-case constant exactly 11/6 against the optimum. Both natural 7/4 bounds for it, against the relaxation's…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.10004
curl -X POST /api/v1/records/arxiv/2609.10004/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.10004/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'