Exact-count pruning preserves a least rational-cost witness
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree.exact_count_message_compressionalgorithmsclusteringdynamic-programming
One entry per unary count suffices. Every retained word is an eligible input witness. For each eligible witness within the budget a retained word attains the same count with no greater rational cost.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_TreeMenuMessages open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree.exact_count_message_compression (I : Instance) (ps : List Word) :
(∀ w∈compress I ps, w∈ps ∧ fitsB I w=true) ∧
(compress I ps).length≤(bins I).length ∧
∀ w∈ps, fitsB I w=true → load I w≤(resources I).length →
∃v∈compress I ps,load I v=load I w ∧ price I v≤price I w := by
sorry
Source
Leaf elimination implementation for the bounded-treewidth dynamic program of Ravichandran and Reyzin, arXiv:2611.03547, Appendix A.6.