Optimization over the polyhedron determined by a submodular function on a co-intersecting family (Q1116890)

A greedy algorithm solves the problem of maximizing a linear objective function over the polyhedron (called the submodular polyhedron) determined by a submodular function on a distributive lattice or a ring family. We generalize the problem by considering a submodular function on a co-intersecting family and give an algorithm for solving it. Here, simple-minded greedy augmentations do not work any more and some complicated augmentations with multiple exchanges are required. We can find an optimal solution by at most \(1/2\;n(n-1)\) augmentations, where n is the number of the variables and we assume a certain oracle for computing multiple exchange capacities.