# Metadata

- Title: Towards Minimizing k-Submodular Functions
- Authors: Anna Huber, Vladimir Kolmogorov
- Year: 2013
- Venue: arXiv preprint; short version in ISCO 2012
- Primary group: k-submodular
- Secondary tags: minimization, polyhedron, min-max-theorem, multimatroid, tree-submodularity
- Problem: structural theory for minimizing k-submodular functions in the oracle model, generalizing the submodular and bisubmodular Min-Max viewpoint
- Main guarantee: proves an exact Min-Max theorem `min_T f(T) = max_{x in U(f)} -||x||_1` for normalized k-submodular functions, gives an integer version, defines the k-submodular polyhedron, and shows rank functions of k-matroids are k-submodular
- Key techniques: reduction to submodular slices `2^K`, tight-set analysis, partial reduction to the bisubmodular case via unique negative leaves, unified vectors, polyhedral embedding
- Status: processed-deep, foundational-original
- Tags: #k-submodular #minimization #polyhedron #min-max #multimatroid #foundations
- Inbox source: inbox/1309.5469v1.pdf