2021/11/14 by Sharat Ibrahimpur, Ibrahimpur, Sharat, Chaitanya Swamy +1 · 2 citations
Engineering · Computer Science · #Scheduling and Optimization Algorithms #Optimization and Search Problems #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2111.07244
We consider the Vector Scheduling problem on identical machines: we have m\nmachines, and a set J of n jobs, where each job j has a processing-time vector\npj\∈ \ℝd\≥ 0. The goal is to find an assignment \σ:J\→\n[m] of jobs to machines so as to minimize the makespan \maxi\∈\n[m]\maxr\∈ [d]( \∑j:\σ(j)=ipj,r). A natural lower bound on\nthe optimal makespan is lb :=\max \maxj\∈ J,r\∈ [d]pj,r,\maxr\∈\n[d](\∑j\∈ Jpj,r/m) . Our main result is a very simple O(log\nd)-approximation algorithm for vector scheduling with respect to the lower\nbound lb: we devise an algorithm that returns an assignment whose makespan is\nat most O(log d)*lb.\n As an application, we show that the above guarantee leads to an O(log log\nm)-approximation for Stochastic Minimum-Norm Load Balancing (StochNormLB). In\nStochNormLB, we have m identical machines, a set J of n independent stochastic\njobs whose processing times are nonnegative random variables, and a monotone,\nsymmetric norm f:\ℝm \→ \ℝ\≥ 0. The goal is to find an\nassignment \σ:J\→ [m] that minimizes the expected f-norm of the\ninduced machine-load vector, where the load on machine i is the (random) total\nprocessing time assigned to it. Our O(log log m)-approximation guarantee is in\nfact much stronger: we obtain an assignment that is simultaneously an O(log log\nm)-approximation for StochNormLB with all monotone, symmetric norms. Next, this\napproximation factor significantly improves upon the O(log m/log log\nm)-approximation in (Ibrahimpur and Swamy, FOCS 2020) for StochNormLB, and is a\nconsequence of a more-general black-box reduction that we present, showing that\na \γ(d)-approximation for d-dimensional vector scheduling with respect to\nthe lower bound lb yields a simultaneous \γ(\log m)-approximation for\nStochNormLB with all monotone, symmetric norms.\n