Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
The 11/6 supremum of the Wang-Sitters rounding scheme for graph balancing
Adam Y. Shavit
Wang and Sitters' 11/6-approximation for graph balancing (each job allowed on at most two machines) is not one algorithm but a set of permitted executions. Step 1 may return any fe…
cs.DS2026
A minimum witness for the 3/2 configuration-linear-program gap in two-weight graph balancing, unique at its size
Adam Y. Shavit
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…
cs.DS2026
Minimum-makespan completion and vertex selection leave the Wang-Sitters constant at 11/6
Adam Y. Shavit
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 c…