A 2-Dimensional Binary Search for Integer Pareto Frontiers

11/11/2021

∙

by   Yotam gafni, et al.

∙

0

∙

share

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.