A 2-Dimensional Binary Search for Integer Pareto Frontiers

Abstract

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 $\theta (n)$ worst-case run time.

arXiv commentFound that this is a restatement of a known algorithm called Saddleback search: https://link.springer.com/chapter/10.1007/11783596_8