Closing the Gap for Makespan Scheduling via Sparsification Techniques

References

• [1] Alon N, Azar Y, Woeginger GJ, Yadid T (1997) Approximation schemes for scheduling. Proc. 8th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 493–500.Google Scholar
• [2] Alon N, Azar Y, Woeginger GJ, Yadid T (1998) Approximation schemes for scheduling on parallel machines. J. Scheduling 1(1):55–66.Crossref, Google Scholar
• [3] Chen L, Jansen K, Zhang G (2014) On the optimality of approximation schemes for the classical scheduling problem. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 657–668.Google Scholar
• [4] Eisenbrand F, Shmonin G (2006) Carathéodory bounds for integer cones. Oper. Res. Lett. 34(5):564–568.Crossref, Google Scholar
• [5] Goemans MX, Rothvoß T (2014) Polynomiality for bin packing with a constant number of item types. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 830–839.Google Scholar
• [6] Gonzalez TF, Ibarra OH, Sahni S (1977) Bounds for LPT schedules on uniform processors. SIAM J. Comput. 6(1):155–166.Crossref, Google Scholar
• [7] Graham RL (1966) Bounds for certain multiprocessing anomalies. Bell System Tech. J. 45(9):1563–1581.Crossref, Google Scholar
• [8] Graham RL (1969) Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2):416–429.Crossref, Google Scholar
• [9] Hochbaum D (1997) Various notions of approximations: Good, better, best, and more. Hochbaum D, ed. Approximation Algorithms for NP-Hard Problems (PWS Publishing Company, Boston), 346–398.Google Scholar
• [10] Hochbaum DS, Shmoys DB (1987) Using dual approximation algorithms for scheduling problems: Theoretical and practical results. J. ACM 34(1):144–162.Crossref, Google Scholar
• [11] Jansen K (2010) An EPTAS for scheduling jobs on uniform processors: Using an MILP relaxation with a constant number of integral variables. SIAM J. Discrete Math. 24(2):457–485.Crossref, Google Scholar
• [12] Jansen K, Mastrolilli M (2010) Scheduling unrelated parallel machines: Linear programming strikes back. Technical Report 1004, University of Kiel, Kiel, Germany.Google Scholar
• [13] Jansen K, Robenek C (2011) Scheduling jobs on identical and uniform processors revisited. Solis-Oba R, Persiano G, eds. Approximation and Online Algorithms (WAOA 2011), Lecture Notes in Computer Science 7164 (Springer, Berlin, Heidelberg), 109–122.Crossref, Google Scholar
• [14] Kannan R (1987) Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3):415–440.Link, Google Scholar
• [15] Lenstra HW (1983) Integer programming with a fixed number of variables. Math. Oper. Res. 8(4):538–548.Link, Google Scholar
• [16] Leung JYT (1989) Bin packing with restricted piece sizes. Inform. Process. Lett. 31(3):145–149.Crossref, Google Scholar
• [17] Schrijver A (1986) Theory of Linear and Integer Programming (John Wiley & Sons, New York).Google Scholar