Simpler and Better Algorithms for MinimumNorm Load Balancing Recently, Chakrabarty and Swamy (STOC 2019) introduced the em minimumnorm loadbalancing problem on unrelated machines, wherein we are given a set J of jobs that need to be scheduled on a set of m unrelated machines, and a monotone, symmetric norm; We seek an assignment sg:Jmapstom that minimizes the norm of the resulting load vector lvec_sginR_m, where lvec_sg(i) is the load on machine i under the assignment sg. Besides capturing all ell_p norms, symmetric norms also capture other norms of interest including topell norms, and ordered norms. Chakrabarty and Swamy (STOC 2019) give a (38ve)approximation algorithm for this problem via a general framework they develop for minimumnorm optimization that proceeds by first carefully reducing this problem (in a series of steps) to a problem called minmax ordered load balancing, and then devising a socalled deterministic oblivious LProunding algorithm for ordered load balancing.  give a :142,direct, and simple 4approximation algorithm for the minimumnorm load balancing based on rounding a (nearoptimal) solution to a novel convexprogramming relaxation for the problem. Whereas the natural convex program encoding minimumnorm load balancing problem has a large nonconstant integrality gap, we show that this issue can be remedied by including a key constraint that bounds the norm of the jobcost vector. Our techniques also yield a (essentially) 4approximation for: (a) em multinorm load balancing, wherein we are given multiple monotone symmetric norms, and we seek an assignment respecting a given budget for each norm; (b) the best em simultaneous approximation factor achievable for all symmetric norms for a given instance.

FixedOrder Scheduling on Parallel Machines We consider the following natural scheduling problem: Given a sequence of jobs with weights and processing times, one needs to assign each job to one of m identical machines in order to minimize the sum of weighted completion times. The twist is that for machine the jobs assigned to it must obey the order of the input sequence, as is the case in multiserver queuing systems. We establish a constant factor approximation algorithm for this (strongly NPhard) problem. Our approach is necessarily very different from what has been used for similar scheduling problems without the fixedorder assumption. We also give a QPTAS for the special case of unit processing times.