On a general framework for network representability in discrete optimization

Yuni Iwamasa ()
Additional contact information
Yuni Iwamasa: University of Tokyo

Journal of Combinatorial Optimization, 2018, vol. 36, issue 3, No 2, 678-708

Abstract: 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 an efficiently solvable problem. Hence it is natural to ask what functions are network representable. In the case of pseudo Boolean functions (functions on $$\{0,1\}^n$$ { 0 , 1 } n ), it is known that any submodular function on $$\{0,1\}^3$$ { 0 , 1 } 3 is network representable. Živný–Cohen–Jeavons showed by using the theory of expressive power that a certain submodular function on $$\{0,1\}^4$$ { 0 , 1 } 4 is not network representable. In this paper, we introduce a general framework for the network representability of functions on $$D^n$$ D n , where D is an arbitrary finite set. We completely characterize network representable functions on $$\{0,1\}^n$$ { 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.

Keywords: Network representability; Valued constraint satisfaction problem; Expressive power; k-Submodular function (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0136-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:36:y:2018:i:3:d:10.1007_s10878-017-0136-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0136-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().