A network flow solution to some nonlinear 0‐1 programming problems, with applications to graph theory

Publisher Website
Google Scholar
Abstract
A network flow technique is used to solve the unconstrained nonlinear 0‐1 programming problem, which is maximizing the ratio of two polynomials, assuming that all the nonlinear coefficients in the numerator are non‐negative and all the nonlinear coefficients in the denominator are nonpositive. Two examples are an investment selection problem to maximize the rate of return, and a decomposition approach to a scheduling problem studied by Sidney and Lawler. The proposed algorithm requires the solution of a sequence of minimum‐cut problems in a related network, and can be extended to some more general problems of the same type. This approach is also applied to find the density of a graph (the maximum ratio, among its subgraphs, of the number of edges to the number of nodes) and its arboricity, for which polynomial algorithms are described. It is also useful in providing a bounding scheme for the maximum‐clique and vertex packing problems.

This publication has 13 references indexed in Scilit: