Abstract
The reliable fraction of information is an attractive score for quantifying (functional) dependencies in high-dimensional data. In this paper, we
systematically explore the algorithmic implications
of using this measure for optimization. We show
that the problem is NP-hard, justifying worst-case
exponential-time as well as heuristic search methods. We then substantially improve the practical
performance for both optimization styles by deriving a novel admissible bounding function that has an
unbounded potential for additional pruning over the
previously proposed one. Finally, we empirically
investigate the approximation ratio of the greedy
algorithm and show that it produces highly competitive results in a fraction of time needed for complete
branch-and-bound style search