[{"related_material":{"record":[{"relation":"earlier_version","id":"2934","status":"public"}]},"issue":"4-5","volume":160,"publication_status":"published","language":[{}],"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1005.2305"}],"scopus_import":1,"intvolume":" 160","month":"03","abstract":[{"lang":"eng"}],"oa_version":"Preprint","department":[{"tree":[{"_id":"ResearchGroups"},{"_id":"IST"}],"_id":"VlKo"}],"date_updated":"2023-02-23T11:04:49Z","creator":{"login":"kschuh","id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87"},"type":"journal_article","status":"public","_id":"3257","page":"416 - 426","uri_base":"https://research-explorer.ista.ac.at","date_created":"2018-12-11T12:02:18Z","date_published":"2012-03-01T00:00:00Z","dc":{"creator":["Kolmogorov, Vladimir"],"rights":["info:eu-repo/semantics/openAccess"],"language":["eng"],"title":["Generalized roof duality and bisubmodular functions"],"relation":["info:eu-repo/semantics/altIdentifier/doi/10.1016/j.dam.2011.10.026","info:eu-repo/semantics/altIdentifier/arxiv/1005.2305"],"source":["Kolmogorov V. Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. 2012;160(4-5):416-426. doi:10.1016/j.dam.2011.10.026"],"identifier":["https://research-explorer.ista.ac.at/record/3257"],"description":["Consider a convex relaxation f̂ of a pseudo-Boolean function f. We say that the relaxation is totally half-integral if f̂(x) is a polyhedral function with half-integral extreme points x, and this property is preserved after adding an arbitrary combination of constraints of the form x i=x j, x i=1-x j, and x i=γ where γ∈{0,1,1/2} is a constant. A well-known example is the roof duality relaxation for quadratic pseudo-Boolean functions f. We argue that total half-integrality is a natural requirement for generalizations of roof duality to arbitrary pseudo-Boolean functions. Our contributions are as follows. First, we provide a complete characterization of totally half-integral relaxations f̂ by establishing a one-to-one correspondence with bisubmodular functions. Second, we give a new characterization of bisubmodular functions. Finally, we show some relationships between general totally half-integral relaxations and relaxations based on the roof duality. On the conceptual level, our results show that bisubmodular functions provide a natural generalization of the roof duality approach to higher-order terms. This can be viewed as a non-submodular analogue of the fact that submodular functions generalize the s-t minimum cut problem with non-negative weights to higher-order terms."],"date":["2012"],"type":["info:eu-repo/semantics/article","doc-type:article","text","http://purl.org/coar/resource_type/c_6501"],"publisher":["Elsevier"]},"publication":"Discrete Applied Mathematics","day":"01","oa":1,"quality_controlled":"1","external_id":{"arxiv":[]},"author":[{"last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"}],"publist_id":"3397","dini_type":"doc-type:article","citation":{"chicago":"Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.” Discrete Applied Mathematics. Elsevier, 2012. https://doi.org/10.1016/j.dam.2011.10.026.","ista":"Kolmogorov V. 2012. Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. 160(4–5), 416–426.","mla":"Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.” Discrete Applied Mathematics, vol. 160, no. 4–5, Elsevier, 2012, pp. 416–26, doi:10.1016/j.dam.2011.10.026.","apa":"Kolmogorov, V. (2012). Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2011.10.026","ieee":"V. Kolmogorov, “Generalized roof duality and bisubmodular functions,” Discrete Applied Mathematics, vol. 160, no. 4–5. Elsevier, pp. 416–426, 2012.","short":"V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 416–426."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"}]