A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract)

DOI10.1007/978-3-319-45587-7_33MaRDI QIDQ2835693zbMATH OpenOpenAlexFDO

Authors Hiroshi Hirai, Taihei Oki

Publication date 30 November 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-45587-7_33

zbMATH Keywords

\(k\)-submodular functionBirkhoff representation theoremPotts energy functionposet with inconsistent pairs

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Proceedings, conferences, collections, etc. pertaining to operations research and mathematical programming (90-06) Semilattices (06A12) Algebraic aspects of posets (06A11) Computational methods for problems pertaining to ordered structures (06-08)

Recommendations

• A compact representation for minimizers of \(k\)-submodular functions
• Towards minimizing \(k\)-submodular functions
• Maximizing \(k\)-submodular functions and beyond
• A note on minimizing submodular functions
• Submodular function minimization and related topics
• Submodular function minimization and maximization in discrete convex analysis
• On submodular function minimization
• scientific article; zbMATH DE number 7051294
• K-submodular functions and convexity of their Lovász extension
• scientific article; zbMATH DE number 2119755

Cites work

• Generating all maximal models of a Boolean expression
• Geodesics in CAT(0) cubical complexes
• Half-integrality, LP-branching, and FPT algorithms
• Matrices and matroids for systems analysis
• Max flows in \(O(nm)\) time, or better
• Median graphs, parallelism and posets
• Medians and Betweenness
• Network flow and 2-satisfiability
• On \(k\)-submodular relaxation
• On the structure of all minimum cuts in a network and applications
• Petri nets, event structures and domains. I
• The Complexity of Multiterminal Cuts
• The power of linear programming for general-valued CSPs
• Towards minimizing \(k\)-submodular functions

Cited in

(6)

• On a general framework for network representability in discrete optimization (extended abstract)
• A compact representation for minimizers of \(k\)-submodular functions
• On a general framework for network representability in discrete optimization
• A min-max theorem for transversal submodular functions and its implications
• Efficient minimization of higher order submodular functions using monotonic Boolean functions
• Towards minimizing \(k\)-submodular functions

This page was built for publication: A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835693)