paper

Classification via Two-Way Comparisons

arXiv:2302.09692 · doi:10.1145/3709361

Abstract

Given a weighted, ordered query set and a partition of into classes, we study the problem of computing a minimum-cost decision tree that, given any query in , uses equality tests and less-than comparisons to determine the class to which belongs. Such a tree can be much smaller than a lookup table, and much faster and smaller than a conventional search tree. We give the first polynomial-time algorithm for the problem. The algorithm extends naturally to the setting where each query has multiple allowed classes.

Appears in WADS 2023 and TALG 2024

Classification via Two-Way Comparisons · wovepaper