Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions. (English) Zbl 0583.90067

The problem of maximizing a pseudoboolean function (or equivalently a set function) which is supermodular, has many interesting applications e.g. in combinatorial optimization, operations research etc. Up to now, a number of special cases of pseudoboolean functions have been known, the maximization of which can be converted into the search for a maximum flow in an associated network. These were essentially the so-called negative- positive pseudoboolean functions (which, as will be noted here, turn out to be supermodular). First it is shown here how these results on negative-positive functions can be more easily derived by using the concept of conflict graph. The conflict graph approach is then generalized to extend the class of problems amenable to maximum network flow problems to the whole set of cubic supermodular pseudoboolean functions.


90C09 Boolean programming
90C10 Integer programming
90B10 Deterministic network models in operations research
Full Text: DOI


[1] Aoshima, K.; Iri, M., Comments of F. Hadlock’s paper: finding a maximum cut of a planar graph in polynomial time, SIAM J. comput., 6, 1, 86-87, (1977) · Zbl 0348.05003
[2] Berge, C., Graphes et hypergraphes, (1970), Dunod Paris · Zbl 0213.25702
[3] Biesel-Guitonneau, S., Algorithmes gluotons et fonctions surmodulaires: théorie et application à un problème de sécurité dans LES réseaux de Télécommunications, Ann. Télécommunications, 35, 7-8, 266-271, (1980) · Zbl 0465.94051
[4] Billionnet, A.; Caradot, I., Comparaison expérimentale d’algorithmes pour LES problèmes de recouvrement et de maximisation d’une fonction pseudo-booléene, RAIRO (série verte), 17, 1, 15-20, (1983) · Zbl 0525.90070
[5] Dantzig, G.B., Linear programming and extensions, (1963), Princeton Univ. Press Princeton · Zbl 0108.33103
[6] Edmonds, J., Paths trees and flowers, Canad. J. math., 17, 449-467, (1965) · Zbl 0132.20903
[7] Even, S., The maximal flow algorithm of dinic and karzanov: an exposition, Mit, lcs, tm, 80, (1976)
[8] Fisher, M.L.; Nemhauser, G.L.; Wolsey, L.A., An analysis of approximation for maximizing submodular set functions I, Math. programming, 14, 265-294, (1978) · Zbl 0374.90045
[9] Ford, L.R.; Fulkerson, D.R., Flows in networks, (1962), Princeton Univ. Press Princeton · Zbl 0139.13701
[10] Garey, M.R.; Johnson, D.S., Computers and intractability: an introduction to the theory of NP-completeness, (1979), W.H. Freeman San Francisco · Zbl 0411.68039
[11] Gondran, M.; Minoux, M., Graphes et algorithmes, () · Zbl 0497.05023
[12] Grötschel; Lovasz, L.; Schrijver, A., The ellipsoïd method and its consequences in combinatorial optimization, Combinatorica, I, 2, 169-197, (1981) · Zbl 0492.90056
[13] Hadlock, F., Finding a maximum cut of a planar graph in polynomial time, SIAM J. comput., 4, 3, 221-225, (1975) · Zbl 0321.05120
[14] Hammer, P.L., The conflict graph of a Pseudoboolean function, (1978), W. Long Branch New Jersey, Bell Labs. Operations Research Center
[15] Hammer, P.; Hansen, P.; Simeone, B., Roof duality, complementation and persistency in quadratic 0-1 optimization, Math. programming, 28, 121-155, (1984) · Zbl 0574.90066
[16] P. Hansen, Quelques approches de la programmation non linéaire en variables 0-1. · Zbl 0298.90048
[17] Minoux, M., Accelerated greedy algorithms for maximizing submodular set functions, (), 234-243
[18] Rhys, J.M.W., A selection problem of shared fixed costs and network flows, Management sci., 17, 3, 200-207, (1970) · Zbl 0203.52505
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.