A 2-Dimensional Binary Search for Integer Pareto Frontiers

2021/11/11 by Yotam Gafni, Gafni, Yotam
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Algorithms and Data Compression #Machine Learning and Algorithms #cs.DS

paper · pdf · doi:10.48550/arxiv.2111.06101

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

arxiv created 2022/01/23 · arxiv updated 2022/01/25

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

Related

• Stochastic convergence of random search to fixed size Pareto set approximations
• A General Large Neighborhood Search Framework for Solving Integer Linear Programs
• Learning Large Neighborhood Search Policy for Integer Programming
• On deterministic, constant memory triangular searches on the integer lattice
• Exploiting variable associations to configure efficient local search algorithms in large-scale binary integer programs