  Many problems in computer science and applied mathematics require rounding a
vector $\mathbf{w}$ of fractional values lying in the interval $[0,1]$ to a
binary vector $\mathbf{x}$ so that, for a given matrix $\mathbf{A}$,
$\mathbf{A}\mathbf{x}$ is as close to $\mathbf{A}\mathbf{w}$ as possible. For
example, this problem arises in LP rounding algorithms used to approximate
$\mathsf{NP}$-hard optimization problems and in the design of uniformly
distributed point sets for numerical integration. For a given matrix
$\mathbf{A}$, the worst-case error over all choices of $\mathbf{w}$ incurred by
the best possible rounding is measured by the linear discrepancy of
$\mathbf{A}$, a quantity studied in discrepancy theory, and introduced by
Lovasz, Spencer, and Vesztergombi (EJC, 1986).
  We initiate the study of the computational complexity of linear discrepancy.
Our investigation proceeds in two directions: (1) proving hardness results and
(2) finding both exact and approximate algorithms to evaluate the linear
discrepancy of certain matrices. For (1), we show that linear discrepancy is
$\mathsf{NP}$-hard. Thus we do not expect to find an efficient exact algorithm
for the general case. Restricting our attention to matrices with a constant
number of rows, we present a poly-time exact algorithm for matrices consisting
of a single row and matrices with a constant number of rows and entries of
bounded magnitude. We also present an exponential-time approximation algorithm
for general matrices, and an algorithm that approximates linear discrepancy to
within an exponential factor.
