Recognition of a class of unimodular functions
1990
Abstract For some pseudo-Boolean functions, the problem of maximization reduces to a linear programming problem with a totally unimodular matrix. Among those, we consider the subclass of functions which can be transformed into functions whose nonlinear terms have nonnegative coefficients. A polynomial-time recognition algorithm for such functions is described. The notion of extended graph of a function is introduced; we show that it is bipartite if the linear programming formulation of the optimization problem has a totally unimodular constraint matrix.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
7
References
5
Citations
NaN
KQI