A 2-Dimensional Binary Search for Integer Pareto Frontiers
Yotam Gafni · arXiv (Cornell University) · 2021
For finite integer squares, we consider the problem of learning a classification $I$ that respects Pareto domination. The setup is natural in dynamic programming settings. We show that a generalization of the binary search algorithm achieves an optimal $θ(n)$ worst-case run time.