The central result is a trade-off, not a single winning algorithm. A preprint studies how to merge consecutive probabilities into contiguous segments while keeping the entropy of the resulting distribution q at or below a chosen limit R, then maximize the entropy that remains. Only neighboring probabilities may be combined.
The paper's motivation is practical in principle: grouping can reduce the number of symbols in a source or reduce its entropy while preserving statistical information. It points to alphabetic coding, scalar quantization and histogram segmentation as examples of where the problem could arise.
This is a methods paper built around abstract probability distributions in the probability simplex, not an empirical study using human, animal or biological data. Its findings are mathematical statements about algorithms under the stated model.
The exact answer comes at a heavy cost
The exact route uses dynamic programming. For every prefix of the input distribution and every possible number of segments, it records the entropy states that remain feasible. It then chooses the largest final state, producing the best feasible entropy for the constrained problem.
That exactness is costly. The paper reports exponential worst-case time and space for the dynamic program. The supplied text extraction flattens a superscript in the displayed Theta bound, so the precise typeset exponent should be checked against the original source.
Two shortcuts make different bets
Algorithm 1, called AvoidMaxAggregation, takes a different route. When R is below log2 n, it constructs aggregations whose entropies decrease as the procedure proceeds, avoids merging designated largest input probabilities with one another, and returns the first aggregation that meets the limit. When R is at least log2 n, the original distribution p is itself optimal.
The authors give AvoidMaxAggregation two guarantees. In additive terms, the gap between the optimum and the algorithm's output is bounded by a binary-entropy term tied to a threshold-dependent order statistic, meaning a ranked input probability selected by the entropy limit. In multiplicative terms, the output is greater than the optimum multiplied by a factor formed from one minus that same term divided by R.
AvoidMaxAggregation is stated to have O(n) time complexity. That is an analytical runtime claim, not a measured speed result.
Algorithm 2, Min-Min, follows a more local rule: at each step it merges the adjacent pair with the smallest sum. The procedure has O(n log n) time complexity.
Min-Min also comes with theorem-based guarantees. The paper states a strict reciprocal bound on its additive loss and a threshold-dependent factor for its multiplicative performance. The extracted fraction layouts are ambiguous, so those guarantees are best reported in words unless checked against the typeset source.
The worked examples do not produce a universal winner. One favors AvoidMaxAggregation, while another favors Min-Min, leaving the two greedy methods not directly comparable on the supplied evidence.
A practical verdict is still out
The inputs are abstract distributions, and the supplied analysis reports no empirical runtime comparison, average-case quality study or application-specific dataset. The formal guarantees therefore do not show how either greedy procedure would behave on a particular real-world workload.
The paper also stops short of settling the problem's computational status. The authors conjecture that the optimization problem is NP-hard, but that conjecture is not proved here. They propose rounding the input probabilities inside the dynamic program as a possible path to a polynomial-time approximation scheme, leaving that scheme as an open direction rather than a reported result.
The document is a preprint identified in its front matter as arXiv version 1, dated 26 Aug 2026.
Paper data and sources
Original title: Constrained Maximum Entropy Contiguous Aggregations
Authors: Roberto Bruno, Ugo Vaccaro
Journal/Repository: 2026 IEEE International Symposium on Information Theory (ISIT), Guangzhou, China, 2026, pp. 1-6
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: 10.1109/isit62367.2026.11654039
Original paper · Full text