Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4959501 | European Journal of Operational Research | 2017 | 41 Pages |
Abstract
To explain this performance, we analyze the theoretical tightness of this formulation. We show that if the number of jobs in each family is bounded then the gap between a heuristic rounding and the lower bound produced by the linear programing increases at most sub-linearly with the number of jobs. The optimality gaps of prior approximation algorithms grow linearly with the number of jobs. Our work improves on these prior results.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Oliver Hinder, Andrew J. Mason,