A Lowest Level Rule Push-Relabel Algorithm for Submodular Flows and Matroid Optimization

摘要

We present a new strategy for combinatorial push-relabel algorithm used in sub modular flows and matroid optimization. In the case of matroid optimization, in contrast with other known algorithms, our strategy needs no lexicographic order of the elements. Combined with a reduction of the number of active basis the resulting procedure gives a time complexity of O(n). Moreover our rule offers more interesting properties of the treated elements and suggests the adaptation of this rule to the sub modular flow algorithm. The above strategy applied for sub modular flows gives an O(n) time complexity procedure, which is the same with the known best complexity given by a procedure based on highest level rule. This method starts a way for a simpler algorithm for finding a feasible sub modular flow which is described in the second part of the paper. Our method for sub modular flow is based on a lowest level rule combined with a bfs-like traversal. The lowest level rule does not work alone because new (ψ- or g-) larger nodes on lower levels can appear during treatment of the current node. Therefore, it is reinforced with a bfs traversal: the new larger nodes are added to a queue - restarted with a lowest level, larger node, whenever it becomes empty. The O(n) time complexity is the same as the best known. Our strategy brings a forest structure of the treated nodes, where the basic operations (pushes and liftings) can be easily numbered and for this reason has a better potential for future improvements.