Combinatorial Structure of the Deterministic Seriation Method with Multiple Subset Solutions
This work addresses the combinatorial complexity in deterministic frequency seriation, which is incremental and relevant for researchers in data ordering and clustering domains.
The paper reviews the combinatorial structure of the classical seriation problem and extends it to an iterative frequency seriation method that finds optimal subsets satisfying a unimodality criterion, noting that the number of possible solutions exceeds n! and highlighting the need for new algorithms and heuristics.
Seriation methods order a set of descriptions given some criterion (e.g., unimodality or minimum distance between similarity scores). Seriation is thus inherently a problem of finding the optimal solution among a set of permutations of objects. In this short technical note, we review the combinatorial structure of the classical seriation problem, which seeks a single solution out of a set of objects. We then extend those results to the iterative frequency seriation approach introduced by Lipo (1997), which finds optimal subsets of objects which each satisfy the unimodality criterion within each subset. The number of possible solutions across multiple solution subsets is larger than $n!$, which underscores the need to find new algorithms and heuristics to assist in the deterministic frequency seriation problem.