Explicitly listed weighted labelings of finite trees
DefinitionStableMSR_Recovery_Supplement_FiniteMenuTreesalgorithmsclustering
Each node has a list of states with an explicit pack and rational weight. An explicit pair list specifies compatibility on tree edges. A witness gives a state index at every node. For each attainable total pack length retain a legal witness of least total rational weight.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_FactorLayouts
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree
open StableMSR.Recovery.Supplement.BinaryRecovery.Regional
abbrev Key := ℕ × ℕ
abbrev Cell := Pack × ℚ
abbrev Instance := FactorLayout × List (List Cell) × List (Key × Key)
def num (x : Block) (i : ℕ) := x[i]?.getD 0
def menu (I : Instance) (i : ℕ) := I.2.1[i]?.getD []
def cell (I : Instance) (x : Block) (i : ℕ) := (menu I i)[num x i]?.getD ([],0)
def Legal (I : Instance) (x : Block) : Prop :=
x.length=I.1.length ∧ (∀ i : Fin I.1.length, num x i.val < (menu I i.val).length) ∧
∀ i j : Fin I.1.length, (layoutTree I.1).Adj i j →
((i.val,num x i.val),(j.val,num x j.val))∈I.2.2
def total (I : Instance) (x : Block) : ℕ × ℚ :=
∑ i : Fin I.1.length, ((cell I x i.val).1.length,(cell I x i.val).2)
def Optima (I : Instance) (xs : List Block) : Prop :=
(∀x∈xs, Legal I x) ∧ ∀y, Legal I y →
∃x∈xs, (total I x).1=(total I y).1 ∧ (total I x).2≤(total I y).2
end StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree
Source
Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Appendix A.6. Explicit finite-menu formulation of the bag dynamic program.