  We study the generalized load-balancing (GLB) problem, where we are given $n$
jobs, each of which needs to be assigned to one of $m$ unrelated machines with
processing times $\{p_{ij}\}$. Under a job assignment $\sigma$, the load of
each machine $i$ is $\psi_i(\mathbf{p}_{i}[\sigma])$ where
$\psi_i:\mathbb{R}^n\rightarrow\mathbb{R}_{\geq0}$ is a symmetric monotone norm
and $\mathbf{p}_{i}[\sigma]$ is the $n$-dimensional vector $\{p_{ij}\cdot
\mathbf{1}[\sigma(j)=i]\}_{j\in [n]}$. Our goal is to minimize the generalized
makespan $\phi(\mathsf{load}(\sigma))$, where
$\phi:\mathbb{R}^m\rightarrow\mathbb{R}_{\geq0}$ is another symmetric monotone
norm and $\mathsf{load}(\sigma)$ is the $m$-dimensional machine load vector.
This problem significantly generalizes many classic optimization problems,
e.g., makespan minimization, set cover, minimum-norm load-balancing, etc.
  We obtain a polynomial time randomized algorithm that achieves an
approximation factor of $O(\log n)$, matching the lower bound of set cover up
to constant factor. We achieve this by rounding a novel configuration LP
relaxation with exponential number of variables. To approximately solve the
configuration LP, we design an approximate separation oracle for its dual
program. In particular, the separation oracle can be reduced to the norm
minimization with a linear constraint (NormLin) problem and we devise a
polynomial time approximation scheme (PTAS) for it, which may be of independent
interest.
