ArXiv.org · 2003 · 17 citations · 8 references
ComputingComputer ScienceAlgorithmsOptimizationStatistical ComputingApproximation AlgorithmsBoolean OperationsCombinatorial OptimizationBoolean Function DecompositionBoolean Function MinimizationBoolean Function RepresentationEfficient EstimationMinimization Of Boolean FunctionsSubmodular MaximizationSubmodular Optimization
Combinatorial algorithms for minimization of functions of many variables, which take their values in finite totally ordered sets, are developed. For that the decomposition of the functions by Boolean polynomials is used. The modified SFM algorithm for minimization of submodular Boolean polynomials is described. The representation of some subclass of submodular Boolean polynomials by graphs is derived in order to make possible use of the graph cut technique.
8