Finite bag menus and original-order witness reconstruction
DefinitionStableMSR_Recovery_Supplement_BagMenuEncodingalgorithmsclustering
Enumerate restrictions on at most t+1 distinct variables. Connect bag states that agree on overlaps. Give each factor occurrence to the first bag covering its scope, and read the global value of each variable from the first bag containing it.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_FiniteMenuTrees
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional.MenuTree
abbrev Data := Block × List Value × FactorLayout
def nodes (L : FactorLayout) := List.range L.length
def bag (L : FactorLayout) (i : ℕ) : Block := (L[i]?.getD ([],[])).1
def owner (L : FactorLayout) (S : Block) : ℕ :=
((nodes L).filter (fun i => S.all (fun v => (bag L i).contains v))).headD 0
def words {β : Type} (letters : List β) : ℕ → List (List β)
| 0 => [[]]
| k+1 => [] :: letters.flatMap (fun a => (words letters k).map (a::·))
def alphabet (z : Data) := z.1.flatMap (fun v => z.2.1.map (v,·))
def readWord (r : List (ℕ × Value)) (v : ℕ) : Value :=
((r.filter (fun p => p.1 == v)).headD (0,[])).2
def bagPlans (t : ℕ) (z : Data) (i : ℕ) : List Plan :=
(((words (alphabet z) (t+1)).map (fun r => z.1.map (readWord r))).filter
(fun s => z.1.all (fun v => !(bag z.2.2 i).contains v || z.2.1.contains (pickValue z.1 s v))))
def entry (t : ℕ) (z : Data) (i k : ℕ) : Plan := (bagPlans t z i)[k]?.getD []
def keys (t : ℕ) (z : Data) : List Key :=
(nodes z.2.2).flatMap (fun i => (List.range (bagPlans t z i).length).map (i,·))
def matchB (t : ℕ) (z : Data) (a b : Key) : Bool :=
z.1.all (fun v => !(bag z.2.2 a.1).contains v || !(bag z.2.2 b.1).contains v ||
pickValue z.1 (entry t z a.1 a.2) v == pickValue z.1 (entry t z b.1 b.2) v)
def links (t : ℕ) (z : Data) : List (Key × Key) :=
(keys t z).flatMap (fun a => ((keys t z).filter (matchB t z a)).map (a,·))
def portion (L : FactorLayout) (ids : Block) (scope : ℕ→Block) (emit : ℕ→Plan→Pack) (i : ℕ) (s : Plan) :=
renderFactors (ids.filter (fun j => owner L (scope j) == i)) emit s
def encodeMenus (t : ℕ) (z : Data) (ids : Block) (scope : ℕ→Block) (emit : ℕ→Plan→Pack)
(cost : Block→ℚ) : Instance :=
(z.2.2,(nodes z.2.2).map (fun i => (bagPlans t z i).map (fun s =>
let p := portion z.2.2 ids scope emit i s
(p,packCost cost p))),links t z)
def unpack (t : ℕ) (z : Data) (x : Block) : Plan :=
z.1.map (fun v => let i := owner z.2.2 [v]
pickValue z.1 (entry t z i (num x i)) v)
def RepresentsPlan (t : ℕ) (z : Data) (x : Block) (s : Plan) : Prop :=
∀ (i : Fin z.2.2.length) v, v∈z.1 → v∈bag z.2.2 i.val →
pickValue z.1 (entry t z i.val (num x i.val)) v=pickValue z.1 s v
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.