Tight Running Times for Minimum ℓ_q-Norm Load Balancing: Beyond Exponential Dependencies on 1/ϵ

References

• [1] Alon N, Azar Y, Woeginger G, Yadid T (1997) Approximation schemes for scheduling. Saks ME, ed. Proc. 8th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 493–500.Google Scholar
• [2] Alon N, Azar Y, Woeginger G, Yadid T (1998) Approximation schemes for scheduling on parallel machines. J. Scheduling 1(1):55–66.Crossref, Google Scholar
• [3] Behrend F (1946) On sets of integers which contain no three terms in arithmetical progression. Proc. Natl. Acad. Sci. USA 32(12):331.Crossref, Google Scholar
• [4] Berman P, Karpinski M, Scott AD (2003) Approximation hardness and satisfiability of bounded occurrence instances of SAT. Electronic Colloquium Comput. Complex. TR03-022.Google Scholar
• [5] Bonnet E, Escoffier B, Kim E, Paschos V (2015) On subexponential and FPT-time inapproximability. Algorithmica 71(3):541–565.Crossref, Google Scholar
• [6] Chen L, Jansen K, Zhang G (2014) On the optimality of approximation schemes for the classical scheduling problem. Chekuri C, ed. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 657–668.Google Scholar
• [7] Chen J, Huang X, Kanj I, Xia G (2004) Linear FPT-reductions and computational lower bounds. Babai L, ed. Proc. 36th Annual ACM Sympos. Theory Comput. (ACM, New York), 212–221.Google Scholar
• [8] Chen L, Marx D, Ye D, Zhang G (2017) Parameterized and approximation results for scheduling with a low rank processing time matrix. Vollmer H, Vallée B, eds. Proc. 34th Sympos. Theoret. Aspects Comput. Sci., vol. 22 (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 1–14.Google Scholar
• [9] Demaine E, Fomin F, Hajiaghayi M, Thilikos D (2005) Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM 52(6):866–893.Crossref, Google Scholar
• [10] Erdös P, Turán P (1941) On a problem of Sidon in additive number theory, and on some related problems. J. London Math. Soc. 1(4):212–215.Crossref, Google Scholar
• [11] Garey M, Johnson D (2002) Computers and Intractability, vol. 29 (W. H. Freeman, New York).Google Scholar
• [12] Gasarch W, Glenn J, Kruskal C (2008) Finding large 3-free sets I: The small n case. J. Comput. System Sci. 74(4):628–655.Crossref, Google Scholar
• [13] Graham R, Lawler E, Lenstra J, Rinnooy Kan A (1979) Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. 5:287–326. Crossref, Google Scholar
• [14] Harary F, Hayes JP, Wu HJ (1988) A survey of the theory of hypercube graphs. Comput. Math. Appl. 15(4):277–289.Crossref, Google Scholar
• [15] Hochbaum D (1997) Chapter 9: Various notions of approximations: Good, better, best, and more. Approximation Algorithms for NP-Hard Problems (PWS Publishing Company).Google Scholar
• [16] Hochbaum D, Shmoys D (1987) Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM 34(1):144–162.Crossref, Google Scholar
• [17] Horowitz E, Sahni S (1976) Exact and approximate algorithms for scheduling nonidentical processors. J. ACM 23(2):317–327.Crossref, Google Scholar
• [18] Ibrahimpur S, Swamy C (2021) Minimum-norm load balancing is (almost) as easy as minimizing makespan. Bansal N, Merelli E, Worrell J, eds. Proc. 48th Internat. Colloquium Automata Languages Programming (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 81:1–81:20.Google Scholar
• [19] Impagliazzo R, Paturi R (2001) On the complexity of k-SAT. J. Comput. System Sci. 62(2):367–375.Crossref, Google Scholar
• [20] Impagliazzo R, Paturi R, Zane F (2001) Which problems have strongly exponential complexity? J. Comput. System Sci. 63:512–530.Crossref, Google Scholar
• [21] 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
• [22] Jansen K, Klein K, Verschae J (2020a) Closing the gap for makespan scheduling via sparsification techniques. Math. Oper. Res. 45(4):1371–1392.Link, Google Scholar
• [23] Jansen K, Land F, Land K (2016) Bounding the running time of algorithms for scheduling and packing problems. SIAM J. Discrete Math. 30(1):343–366.Crossref, Google Scholar
• [24] Jansen K, Maack M, Solis-Oba R (2020b) Structural parameters for scheduling with assignment restrictions. Theoret. Comput. Sci. 844:154–170.Crossref, Google Scholar
• [25] Karmarkar N, Karp R (1982) An efficient approximation scheme for the one-dimensional bin-packing problem. Proc. 23rd Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 312–320.Google Scholar
• [26] Klein P, Marx D (2012) Solving planar k-terminal cut in time. Czumaj A, Mehlhorn K, Pitts AM, Wattenhofer R, eds. Proc. 39th Internat. Colloquium Automata Languages Programming (Springer, Berlin, Heidelberg), 569–580.Google Scholar
• [27] Knop D, Kouteckỳ M (2018) Scheduling meets n-fold integer programming. J. Scheduling 21(5):493–503.Crossref, Google Scholar
• [28] König D (1916) Über graphen und ihre anwendung auf determinantentheorie und mengenlehre. Math. Ann. 77(4):453–465.Crossref, Google Scholar
• [29] Leung J (1989) Bin packing with restricted piece sizes. Inform. Processing Lett. 31(3):145–149.Crossref, Google Scholar
• [30] Lokshtanov D, Marx D, Saurabh S (2013) Lower bounds based on the exponential time hypothesis. Bull. EATCS 3(105):41–72.Google Scholar
• [31] Marx D (2007) On the optimality of planar and geometric approximation schemes. Proc. 48th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 338–348.Google Scholar
• [32] Marx D (2012) A tight lower bound for planar multiway cut with fixed number of terminals. Czumaj A, Mehlhorn K, Pitts AM, Wattenhofer R, eds. Proc. 39th Internat. Colloquium Automata Languages Programming (Springer, Berlin, Heidelberg), 677–688.Google Scholar
• [33] Mnich M, van Bevern R (2018) Parameterized complexity of machine scheduling: 15 open problems. Comput. Oper. Res. 100:254–261.Crossref, Google Scholar
• [34] Mnich M, Wiese A (2015) Scheduling and fixed-parameter tractability. Math. Programming 154(1):533–562.Crossref, Google Scholar
• [35] Moser L (1953) On non-averaging sets of integers. Canadian J. Math. 5:245–252.Crossref, Google Scholar
• [36] Moshkovitz D, Raz R (2010) Two-query PCP with subconstant error. J. ACM 57(5):29.Crossref, Google Scholar
• [37] O’Bryant K (2004) A complete annotated bibliography of work related to Sidon sequences. Electronic J. Combinatorics DS11:39, electronic only.Google Scholar
• [38] Pilipczuk M, Pilipczuk M, Sankowski, P, Leeuwen, Ev (2018) Network sparsification for Steiner problems on planar and bounded-genus graphs. ACM Trans. Algorithms 14(4):1–73.Crossref, Google Scholar
• [39] Schrijver A (1998) Theory of Linear and Integer Programming (John Wiley & Sons, Chichester, UK).Google Scholar
• [40] Skutella M, Woeginger G (1999) A PTAS for minimizing the weighted sum of job completion times on parallel machines. Vitter JS, Larmore LL, Leighton FT, eds. Proc. 31st Annual ACM Sympos. Theory Comput. (ACM, New York), 400–407.Google Scholar
• [41] Tovey C (1984) A simplified satisfiability problem. Discrete Appl. Math. 8:85–89.Crossref, Google Scholar
• [42] Trevisan L (2014) Inapproximability of combinatorial optimization problems. Paschos VT, ed. Paradigms of Combinatorial Optimization: Problems and New Approaches (Wiley-ISTE, Hoboken, NJ), 381–434.Crossref, Google Scholar
• [43] Williamson D, Shmoys D (2011) The Design of Approximation Algorithms (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar