Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization

ABSTRACT

Bisubmodular functions are a natural "directed", or "signed", extension of submodular functions with several applications. Recently Fujishige and Iwata showed how to extend the Iwata, Fleischer, and Fujishige (IFF) algorithm for submodular function minimization (SFM) to bisubmodular function minimization (BSFM). However, they were able to extend only the weakly polynomial version of IFF to BSFM. Here we investigate the difficulty that prevented them from also extending the strongly polynomial version of IFF to BSFM, and we show a way around the difficulty. This new method gives the first combinatorial strongly polynomial algorithm for BSFM. This further leads to extending Iwata's fully combinatorial version of IFF to BSFM.

REFERENCES

• 1: K. Ando and S. Fujishige (1994). ⊔, ⊓-Closed Families and Signed Posets. Report no. 93813, Forschungsinstitut für Diskrete Mathematik, Universität Bonn.
• 2: Kazutoshi Ando , Satoru Fujishige, On structures of bisubmodular polyhedra, Mathematical Programming: Series A and B, v.74 n.3, p.293-317, Sept. 30, 1996 [doi>10.1007/BF02592201]
• 3: J. M. Bilbao Arrese, J. R. Fernández García, M. Jiménez Jiménez, J. J. López Vázquez (2005). A Survey of Bicooperative Games. Proceedings of the 4th Twente Workshop on Cooperative Game Theory, Enschede, the Netherlands, 5--15.
• 4: R. E. Bixby, W. H. Cunningham, and D. M. Topkis (1985). The Partial Order of a Polymatroid Extreme Point. Math. of OR, 10, 367--378.
• 5: A. Bouchet (1989). Matchings and Δ-Matroids. Discrete Mathematics, 24, 55--62.
• 6: Andre Bouchet , William H. Cunningham, Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra, SIAM Journal on Discrete Mathematics, v.8 n.1, p.17-32, Feb. 1995 [doi>10.1137/S0895480191222926]
• 7: R. Chandrasekaran , Santosh N. Kabadi, Pseudomatroids, Discrete Mathematics, v.71 n.3, p.205-217, Nov. 1988 [doi>10.1016/0012-365X(88)90101-X]
• 8: W. H. Cunningham (1984). Testing Membership in Matroid Polyhedra. JCT Series B, 36, 161--188.
• 9: W. H. Cunningham and J. Green-Krótki (1991). b-Matching Degree Sequence Polyhedra. Combinatorica, 11, 219--230.
• 10: William H. Cunningham , Jan Green-Krótki, A separation algorithm for the matchable set polytope, Mathematical Programming: Series A and B, v.65 n.2, p.139-150, June 28, 1994 [doi>10.1007/BF01581694]
• 11: A. Dress and T. F. Havel (1986). Some Combinatorial Properties of Discriminants in Metric Vector Spaces. Adv. Math., 62, 285--312.
• 12: Satoru Fujishige, A Min--Max Theorem for Bisubmodular Polyhedra, SIAM Journal on Discrete Mathematics, v.10 n.2, p.294-308, May 1997 [doi>10.1137/S0895480194264344]
• 13: S. Fujishige (2005). Submodular Functions and Optimization. Second Edition. North-Holland.
• 14: Satoru Fujishige , Satoru Iwata, Bisubmodular Function Minimization, SIAM Journal on Discrete Mathematics, v.19 n.4, p.1065-1073, 2005 [doi>10.1137/S0895480103426339]
• 15: M. Grötschel, L. Lovász, and A. Schrijver (1988). Geometric Algorithms and Combinatorial Optimization. Springer-Verlag.
• 16: Satoru Iwata, A fully combinatorial algorithm for submodular function minimization, Journal of Combinatorial Theory Series B, v.84 n.2, p.203-212, March 2002 [doi>10.1006/jctb.2001.2072]
• 17: S. Iwata (2003). A Faster Scaling Algorithm for Minimizing Submodular Functions. SIAM J. on Computing, 32, 833--840.
• 18: Satoru Iwata , Lisa Fleischer , Satoru Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of the ACM (JACM), v.48 n.4, p.761-777, July 2001 [doi>10.1145/502090.502096]
• 19: S. N. Kabadi , R. Chandrasekaran, On totally dual integral systems, Discrete Applied Mathematics, v.26 n.1, p.87-104, Jan. 1990 [doi>10.1016/0166-218X(90)90023-6]
• 20: S. T. McCormick (2006). Submodular Function Minimization. Chapter 7 in the Handbook on Discrete Optimization, Elsevier, K. Aardal, G. Nemhauser, and R. Weismantel, eds, 321--391.
• 21: Megiddo, N. (1979). Combinatorial Optimization With Rational Objective Functions. Math. Oper. Res. 4; 414--424.
• 22: Kazuo Murota, Discrete convex analysis, Mathematical Programming: Series A and B, v.83 n.3, p.313-371, Nov. 1, 1998 [doi>10.1007/BF02680565]
• 23: K. Nagano (2004). A Strongly Polynomial Algorithm for Line Search in Submodular Polyhedra. Technical Report METR 2004-33, Department of Mathematical Informatics, University of Tokyo, Tokyo, Japan.
• 24: L. Qi, Directed submodularity, ditroids and directed submodular flows, Mathematical Programming: Series A and B, v.42 n.3, p.579-599, Dec. 1988 [doi>10.1007/BF01589420]
• 25: Victor Reiner, Signed posets, Journal of Combinatorial Theory Series A, v.62 n.2, p.324-360, March 1993 [doi>10.1016/0097-3165(93)90052-A]
• 26: Alexander Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory Series B, v.80 n.2, p.346-355, Nov. 2000 [doi>10.1006/jctb.2000.1989]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Algorithms, Design, Theory