Bounded bag menus enumerate every allowed restriction
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree.bag_state_coveragealgorithmsclusteringdynamic-programming
Assignments on one bag are enumerated by words of at most t+1 variable/value pairs. Every menu option is allowed on that bag and every allowed global assignment has a matching option, including empty bags and domains.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_BagMenuEncoding open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree.bag_state_coverage (t : ℕ) (z : Data) (i : Fin z.2.2.length)
(hw : (layoutBag z.1 z.2.2 i).card≤t+1) :
(∀ s∈bagPlans t z i.val, ∀ v∈z.1, v∈bag z.2.2 i.val → pickValue z.1 s v∈z.2.1) ∧
∀ s, AllowedPlan z.1 z.2.1 s → ∃ u∈bagPlans t z i.val,
∀ v∈z.1, v∈bag z.2.2 i.val → pickValue z.1 u v=pickValue z.1 s v := by
sorry
Source
Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Appendix A.6, tree-decomposition dynamic program. Explicit binary witness formulation.