We study the problem of ranking with submodular valuations. An instance of this problem consists of a ground set @math , and a collection of @math monotone submodular set functions @math , where each @math . An additional ingredient of the input is a weight vector @math . The objective is to find a linear ordering of the ground set elements that minimizes the weighted cover time of the functions. The cover time of a function is the minimal number of elements in the prefix of the linear ordering that form a set whose corresponding function value is greater than a unit threshold value. Our main contribution is an @math -approximation algorithm for the problem, where @math is the smallest non-zero marginal value that any function may gain from some element. Our algorithm orders the elements using an adaptive residual updates scheme, which may be of independent interest. We also prove that the problem is @math -hard to approximate, unless P = NP. This implies that the outcome of our algorithm is optimal up to constant factors.
We give a strongly polynomial-time algorithm minimizing a submodular function f given by a value-giving oracle. The algorithm does not use the ellipsoid method or any other linear programming method. No bound on the complexity of the values of f is needed to be known a priori. The number of oracle calls is bounded by a polynomial in the size of the underlying set. We introduce several generalizations of classical computer science problems obtained by replacing simpler objective functions with general submodular functions.The new problems include submodular load balancing, which generalizes load balancing or minimum-makespan scheduling, submodular sparsest cut and submodular balanced cut, which generalize their respective graph cut problems, as well as submodular function minimization with a cardinality lower bound. We establish upper and lower bounds for the approximability of these problems with a polynomial number of queries to a function-value oracle.The approximation guarantees for most of our algorithms are of the order of radic(n ln n). We show that this is the inherent difficulty of the problems by proving matching lower bounds.We also give an improved lower bound for the problem of approximately learning a monotone submodular function. In addition, we present an algorithm for approximately learning submodular functions with special structure, whose guarantee is close to the lower bound. Although quite restrictive, the class of functions with this structure includes the ones that are used for lower bounds both by us and in previous work. This demonstrates that if there are significantly stronger lower bounds for this problem, they rely on more general submodular functions. This paper addresses the problems of minimizing nonnegative submodular functions under covering constraints, which generalize the vertex cover, edge cover, and set cover problems. We give approximation algorithms for these problems exploiting the discrete convexity of submodular functions. We first present a rounding 2-approximation algorithm for the submodular vertex cover problem based on the half-integrality of the continuous relaxation problem, and show that the rounding algorithm can be performed by one application of submodular function minimization on a ring family. We also show that a rounding algorithm and a primal-dual algorithm for the submodular cost set cover problem are both constant factor approximation algorithms if the maximum frequency is fixed. In addition, we give an essentially tight lower bound on the approximability of the submodular edge cover problem.  This paper presents a strongly polynomial algorithm for submodular function minimization using only additions, subtractions, comparisons, and oracle calls for function values.  This paper shows how to compute O(√log n)-approximations to the S PAR S EST CUT and BALANCED SEPARATOR problems in O(n 2 ) time, thus improving upon the recent algorithm of Arora, Rao, and Vazirani [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231]. Their algorithm uses semidefinite programming and requires O(n 9.5 ) time. Our algorithm relies on efficiently finding expander flows in the graph and does not solve semidefinite programs. The existence of expander flows was also established by Arora, Rao, and Vazirani [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231]. We consider the problem of minimizing a submodular function f defined on a set V with n elements. We give a combinatorial algorithm that runs in O(n 5EO + n 6) time, where EO is the time to evaluate f(S) for some @math . This improves the previous best strongly polynomial running time by more than a factor of n. We also extend our result to ring families.  L. G. Khachiyan recently published a polynomial algorithm to check feasibility of a system of linear inequalities. The method is an adaptation of an algorithm proposed by Shor for non-linear optimization problems. In this paper we show that the method also yields interesting results in combinatorial optimization. Thus it yields polynomial algorithms for vertex packing in perfect graphs; for the matching and matroid intersection problems; for optimum covering of directed cuts of a digraph; for the minimum value of a submodular set function; and for other important combinatorial problems. On the negative side, it yields a proof that weighted fractional chromatic number is NP-hard.  Applications in complex systems such as the Internet have spawned a recent interest in studying situations involving multiple agents with their individual cost or utility functions. In this paper, we introduce an algorithmic framework for studying combinatorial optimization problems in the presence of multiple agents with submodular cost functions. We study several fundamental covering problems in this framework and establish upper and lower bounds on their approximability. Combinatorial strongly polynomial algorithms for minimizing submodular functions have been developed by Iwata, Fleischer, and Fujishige (IFF) and by Schrijver. The IFF algorithm employs a scaling scheme for submodular functions, whereas Schrijver's algorithm achieves strongly polynomial bound with the aid of distance labeling. Subsequently, Fleischer and Iwata have described a push relabel version of Schrijver's algorithm to improve its time complexity. This paper combines the scaling scheme with the push relabel framework to yield a faster combinatorial algorithm for submodular function minimization. The resulting algorithm improves over the previously best known bound by essentially a linear factor in the size of the underlying ground set.