Generalized skew bisubmodularity: A characterization and a min–max theorem

• Fujishige, Satoru

• Tanigawa, Shin-ichi

• Yoshida, Yuichi

Abstract

Huber, Krokhin, and Powell (2013) introduced a concept of skew bisubmodularity, as a generalization of bisubmodularity, in their complexity dichotomy theorem for valued constraint satisfaction problems over the three-value domain. In this paper we consider a natural generalization of the concept of skew bisubmodularity and show a connection between the generalized skew bisubmodularity and a convex extension over rectangles. We also analyze the dual polyhedra, called skew bisubmodular polyhedra, associated with generalized skew bisubmodular functions and derive a min–max theorem that characterizes the minimum value of a generalized skew bisubmodular function in terms of a minimum-norm point in the associated skew bisubmodular polyhedron.

Journal

• Discrete Optimization

  Discrete Optimization 12 1-9, 2014-05

  Elsevier B.V.

Keywords

• Skew bisubmodularity
• Submodularity
• Convex extensions

Details

• CRID: 1050001335788820736
• NII Article ID: 120005411432
• NII Book ID: AA12016193
• ISSN: 15725286
• DOI: 10.1016/j.disopt.2013.12.001
• HANDLE: 2433/185325
• Web Site: https://api.elsevier.com/content/article/PII:S1572528613000601?httpAccept=text/xml
• Web Site: https://api.elsevier.com/content/article/PII:S1572528613000601?httpAccept=text/plain
• Text Lang: en
• Article Type: journal article
• Data Source:
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN