# Metadata

- Title: Potts model, parametric maxflow and k-submodular functions
- Authors: Igor Gridchyn, Vladimir Kolmogorov
- Year: 2013
- Venue: computer vision paper / arXiv preprint (`arXiv:1310.1771v1`, October 7, 2013)
- Primary group: k-submodular
- Secondary tags: Potts, parametric-maxflow, relaxation, persistency, minimization, computer-vision
- Problem: partial optimality for Potts-energy minimization, plus the relation between Potts relaxations, tree-metric maxflow formulations, and k-submodular relaxations
- Main guarantee: reduces Kovtun-style preprocessing from `k` maxflow computations to `ceil(1 + log_2 k)` maxflows or one parametric maxflow, proves the resulting tree-metric minimizer is partially optimal, and formalizes k-submodular relaxations with persistency for multilabel energies
- Key techniques: T-convex unary terms on a star/tree metric, divide-and-conquer over binary edge subproblems, coarea formula, parametric maxflow nesting, and persistency arguments for k-submodular relaxations
- Status: processed-deep, venue-year-to-verify
- Tags: #k-submodular #Potts #parametric-maxflow #relaxation #persistency #minimization #computer-vision #arXiv
- Inbox source: inbox/1310.1771v1.pdf