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

Billionnet, A.; Minoux, M.

Discrete Appl. Math. 12, 1-11 (1985).

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.

MSC:

90C09	Boolean programming
90C10	Integer programming
90B10	Deterministic network models in operations research

Keywords:

maximizing a pseudoboolean function; supermodular; maximum flow; negative-positive functions; conflict graph

References:

[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