Data-correcting algorithm for the maximization of submodular functions: a multilevel search in the hasse diagram

Abstract

The Data Correcting Algorithm (DCA) is a recursive branch and bound type algorithm, in which the data of a given instance is heuristically corrected at each branching in such a way that the new instance will be as close as possible to polynomially solvable and the optimal solution to the corrected instance satisfies a prescribed accuracy condition