Performance bounds for the k-batch greedy strategy in optimization problems with curvature

The k-batch greedy strategy is an approximate algorithm to solve optimization problems where the optimal solution is hard to obtain. Starting with the empty set, the k-batch greedy strategy adds a batch of k elements to the current solution set with the largest gain in the objective function while satisfying the constraints. In this paper, we bound the performance of the k-batch greedy strategy with respect to the optimal strategy by defining the total curvature αk. We show that when the objective function is nondecreasing and submodular, the k-batch greedy strategy satisfies a harmonic bound 1/(1 + αk) for a general matroid constraint and an exponential bound (1 − (1 − αk/t)t/αk for a uniform matroid constraint, where k divides the cardinality of the maximal set in the general matroid, t = K/k is an integer, and K is the rank of the uniform matroid. We also compare the performance of the k-batch greedy strategy with that of the k1-batch greedy strategy when k1 divides k. Specifically, we prove that when the objective function is nondecreasing and submodular, the k-batch greedy strategy has better harmonic and exponential bounds in terms of the total curvature. Finally, we illustrate our results by considering a task-assignment problem.