On a general framework for network representability in discrete optimization [Extended Abstract]
On a general framework for network representability in discrete optimization [Extended Abstract]
复制标题
离散优化中网络可表示性的通用框架[扩展摘要]
DOI：
10.1007/978-3-319-45587-7_32
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Yuni Iwamasa
中科院分区：
文献类型：
--
作者：
Hirai Hiroshi;Iwamasa Yuni;Murota Kazuo;Zivny Stanislav;Yuni Iwamasa
In discrete optimization, representing an objective function as ans-tcut function of a network is a basic technique to design an efficient minimization algorithm. A network representable function can be minimized by computing a minimums-tcut of a directed network, which is an efficiently solvable problem. Hence it is natural to ask what functions are network representable. In the case of pseudo Boolean functions (functions on), it is known that any submodular function onis network representable. Živný–Cohen–Jeavons showed by using the theory of expressive power that a certain submodular function onis not network representable. In this paper, we introduce a general framework for the network representability of functions on, whereDis an arbitrary finite set. We completely characterize network representable functions onin 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 binaryk-submodular function are not network representable.
In discrete optimization, representing an objective function as ans-tcut function of a network is a basic technique to design an efficient minimization algorithm. A network representable function can be minimized by computing a minimums-tcut of a directed network, which is an efficiently solvable problem. Hence it is natural to ask what functions are network representable. In the case of pseudo Boolean functions (functions on), it is known that any submodular function onis network representable. Živný–Cohen–Jeavons showed by using the theory of expressive power that a certain submodular function onis not network representable. In this paper, we introduce a general framework for the network representability of functions on, whereDis an arbitrary finite set. We completely characterize network representable functions onin 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 binaryk-submodular function are not network representable.