# Metadata

- Title: On k-Submodular Relaxation
- Authors: Hiroshi Hirai, Yuni Iwamasa
- Year: 2016
- Venue: arXiv preprint (`arXiv:1504.07830v3`, September 9, 2016); preliminary version in HJSDM workshop
- Primary group: k-submodular
- Secondary tags: relaxation, VCSP, persistency, half-integrality, Fourier-Motzkin, domain-characterization
- Problem: given a function `f : [k]^n -> R union {+infty}`, decide whether it admits a k-submodular relaxation on `[0, k]^n`, and construct one when it exists
- Main guarantee: characterizes relaxability by closure of `dom f` under the ternary operation `theta`, and gives an `O((kn)^2)` combinatorial algorithm that either constructs a k-submodular relaxation or certifies impossibility; integer inputs yield half-integral relaxations and binary instances get the unique maximal relaxation
- Key techniques: dual-discriminator polymorphism `theta`, closure operators, greedy Fourier-Motzkin elimination over k-submodular inequalities, persistency, and VCSP/FPT reductions
- Status: processed-deep, venue-year-to-verify
- Tags: #k-submodular #relaxation #VCSP #persistency #half-integrality #Fourier-Motzkin #arXiv
- Inbox source: inbox/1504.07830v3.pdf