3
$\begingroup$

It is known that it is NP-hard to distinguish whether a set system has discrepancy $0$ or $O(\sqrt{n})$, given that the set system has $n$ elements and $m=O(n)$ sets.

In general if it is so hopeless to estimate or upper-bound discrepancy , then why do we care about algorithms that give colorings of $O(\mathrm{herdisc}(C)(\log m\log n)^{1/2})$ discrepancy ? I am interested in applications of discrepancy in approximation algorithms.

$\endgroup$
7
$\begingroup$

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

  1. for all $i,j$, $\|u_i\|^2 \leq t$ and $\|v_j\|^2 \leq t$;
  2. 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.

$\endgroup$
7
  • $\begingroup$ Thanks a lot for the answer. I happened to read an excellent survey article by Nikhil Bansal which cleared a lot of these doubts. So, is it correct that $herdisc$ is approximable to $\log^{3/2} m$, in the regime where $m = O(n)$ ?. I understand the algorithmic perspective that I can round to intergral solutions such that $||Ax - Ay|| _{\infty} \leq herdisc(A)$. I want to upper-bound $herdisc$ efficiently, so that I can provide error bounds in terms of $m,n$. $\endgroup$
    – rajatsen91
    Apr 7 '15 at 19:07
  • $\begingroup$ Yes, Nikhil's survey is highly recommended. You can approximate $\mathrm{herdisc}(A)$ up to $\log^{3/2} m$ no matter what $m$ and $n$ are: see the edit to my answer. $\endgroup$ Apr 7 '15 at 19:33
  • $\begingroup$ Thanks a lot. I think I have a fair idea of what is doable. I will go through the papers you recommended. $\endgroup$
    – rajatsen91
    Apr 7 '15 at 19:36
  • $\begingroup$ Is this the review by Nikhil that is being referred to, win.tue.nl/~nikhil/pubs/disc-ismp%20-final.pdf ? $\endgroup$
    – Anirbit
    Apr 8 '15 at 19:09
  • 1
    $\begingroup$ @Anirbit The article I was referring to is this one : link.springer.com/chapter/10.1007/978-3-319-04696-9_6 $\endgroup$
    – rajatsen91
    Apr 8 '15 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.