I want to compute exactly the hereditary discrepancy of a small (on up to 20 points) set system - is there an efficient way to do it? Brute force search over the discrepancies of all subsystems seems impossible in this case...
1 Answer
$\begingroup$
$\endgroup$
In general, there is (probably) no efficient way to compute even the discrepancy. To see it is NP-hard, notice that a NAE-3SAT formula can give a set system that has discrepancy<3 if and only if the formula is satisfiable. Moreover, every set can be made to have exactly 3 points, so the hereditary discrepancy would be the same. Of course if you have only 20 points, then there can be some ways to calculate it in a reasonable time, unfortunately I don't know anything about these.