On a general framework for network representability in discrete optimization

DOI10.1007/S10878-017-0136-YMaRDI QIDQ1631628zbMATH OpenOpenAlexFDO

Authors Yuni Iwamasa

Publication date 6 December 2018

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.03137

zbMATH Keywords

\(k\)-submodular functionexpressive powernetwork representabilityvalued constraint satisfaction problem

Mathematics Subject Classification ID

Integer programming (90C10) Programming involving graphs or networks (90C35)

Abstract: In discrete optimization, representing an objective function as an $s$-$t$ cut function of a network is a basic technique to design an efficient minimization algorithm. A network representable function can be minimized by computing a minimum $s$-$t$ cut of a directed network, which is a very easy and fastly solved problem. Hence it is natural to ask what functions are network representable. In the case of pseudo Boolean functions (functions on ${0,1}^n$), it is known that any submodular function on ${0,1}^3$ is network representable. v{Z}ivn'y--Cohen--Jeavons showed by using the theory of expressive power that a certain submodular function on ${0,1}^4$ is not network representable. In this paper, we introduce a general framework for the network representability of functions on $D^n$, where $D$ is an arbitrary finite set. We completely characterize network representable functions on ${0,1}^n$ in our new definition. We can apply the expressive power theory to the network representability in the proposed definition. We prove that some ternary bisubmodular function and some binary $k$-submodular function are not network representable.

Recommendations

• On a general framework for network representability in discrete optimization (extended abstract)
• Submodular functions in problems of synthesis of networks
• A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract)
• The Expressive Power of Binary Submodular Functions
• The expressive power of binary submodular functions

Cites work

• A combinatorial algorithm for the minimum \((2,r)\)-metric problem and some generalizations
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Algebraic properties of valued constraint satisfaction problem
• An algebraic theory of complexity for discrete optimization.
• Discrete convexity and polynomial solvability in minimum 0-extension problems
• Efficient minimization of higher order submodular functions using monotonic Boolean functions
• Geometric algorithms and combinatorial optimization
• Half-integrality, LP-branching, and FPT algorithms
• scientific article; zbMATH DE number 2062604 (Why is no real title available?)
• L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
• Learning with submodular functions: a convex optimization perspective
• Max flows in O(nm) time, or better
• Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
• Minimum cost multiflows in undirected networks
• On the complexity of submodular function minimisation on diamonds
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• Submodular functions and optimization.
• The complexity of valued constraint satisfaction problems
• The expressive power of binary submodular functions
• The power of linear programming for general-valued CSPs
• The power of Sherali-Adams relaxations for general-valued CSPs
• Towards minimizing k-submodular functions

Cited in

(2)

• On a general framework for network representability in discrete optimization (extended abstract)
• A characterization of network representable polymatroids

This page was built for publication: On a general framework for network representability in discrete optimization

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