Hereditary Discrepancy
Actually for applications to approximation algorithms, hereditary discrepancy is often the right quantity. The central result here is due to Lovasz, Spencer and Vesztergombi:


  LSV Thm. For any $m\times n$ matrix $A$ and any vector $x \in [0,1]^n$, there exists a vector $y \in \{0,1\}^n$ such that $\|Ax - Ay\|_\infty \leq \mathrm{herdisc}(A)$.


(If you don't have access to the paper, you can check Lemma 1.14 in Chazelle's book for a proof.)
This theorem can then be used to round a solution to a linear programming relaxation of a combinatorial problem. A very nice example is the recent work on the bin packing problem: for the basic idea check the paper by Eisenbrand, Palvoelgyi, and Rothvoss, and for the best result to date, check this recent arxiv paper by Hoberg and Rothvoss.

The exact guarantee you mention -- efficiently finding a coloring with discrepancy bounded by the hereditary discrepancy -- fits very nicely into this, because it's exactly the guarantee to make the LSV theorem constructive. I.e. if you have an algorithm that for any matrix $A$ finds in polynomial time a coloring $x \in \{-1, 1\}^n$ such that $\|Ax\|_\infty \leq \alpha \cdot \mathrm{herdisc}(A)$, then we have an efficient LSV theorem in which for any $A$ and $x$ there exists a polynomial time computable $y$ such that $\|Ax - Ay\|_\infty \leq \alpha \cdot \mathrm{herdisc}(A)$.

By the way, hereditary discrepancy turns out to be the right quantity in other applications too: constructing $\epsilon$-samples and differential privacy, for example. Also it can be efficiently approximated up to a factor of $\log^{3/2}m$. The largest hardness of approximation known for hereditary discrepancy is factor 2, so hereditary discrepancy may even be approximable within a fixed constant (although I'd be surprised). 

EDIT: Let me say a few more words about the approximation, since you say you want to find upper bounds on $\mathrm{herdisc}$. Although my paper with Kunal is not written this way, what we show in fact is that 
$$
\gamma_2(A)/O(\log \min(m,n)) \leq \mathrm{herdisc}(A) \leq O(\sqrt{\log m})\gamma_2(A),
$$
where $\gamma_2(A)$ is a classical factorization norm, equal to the smallest number $t$ such that there exist vectors $u_1, \ldots, u_m$, $v_1, \ldots, v_n$ satisfying


for all $i,j$, $\|u_i\|^2 \leq t$ and $\|v_j\|^2 \leq t$;
for all $i, j$, $a_{i,j} = u_i^T v_j$.


It's not hard to turn this definition into a semidefinite program that computes $\gamma_2(A)$. Besides the approximation, this is very useful because $\gamma_2$ has many nice properties which make it easy to give upper and lower bounds which then translate into upper and lower bounds for hereditary discrepancy. My paper with Matousek has some applications.