A generalization of the notion of the rank function of a matroid (Q2713933)

The author introduces two functions which generalize the notions of the rank function for independence systems and, in particular, of the rank function of a matroid. In terms of those functions, the author describes accuracy of an approximate solution obtained by a greedy algorithm to a maximum problem of integer programming with a linear objective function. Some interrelations are found between optimality of the greedy algorithm and submodularity of rank functions. As a corollary, it is shown that the greedy algorithm ``go to the farthest unpassed town'' solves the travelling salesman maximum problem on an unordered graph with relative accuracy 1/2.