Ranking has abundant applications in information retrieval (IR), data mining, and natural language processing. In many real scenarios, the ranking problem is defined as follows. Given a group of data objects, a ranking model (function) sorts the objects in the group according to their degrees of relevance, importance, or preferences. For example, in IR, the “group” corresponds to a query, and “objects” correspond to documents associated with the query. A mass of relevant objects may contain highly redundant, even duplicated information, which is undesirable for users. Furthermore, the user’s needs might be multi-faceted or ambiguous. The redundance in top ranked results will reduce the chance to satisfy different users. For example, given a query “zeppelin”, if the top ranked search results were all similar articles about the “Zeppelin iPod speaker”, it would be a waste of the output space and largely degrade users’ search experience even though the results are all highly relevant to the query. Obviously, such top ranked results would not satisfy the users who want to know about the rigid airship “Zeppelin” or the rock band “Zeppelin”. Thus, it is important to reduce redundancy in these top search results. Therefore, beyond relevance and importance, diver- sity has also been recognized as a crucial criterion in ranking. Top ranked results are expected to convey as little redundant information as possible, and cover as many aspects as possible. In this way, we are able to minimize the risk that the information need of the user will not be satisfied. Many real application tasks demand diversity in ranking. For example, in query recommendation, the recommended queries should capture different query intents of different users. In text summarization, candidate sentences of a summary are expected to be less redundant and cover different aspects of information delivered by the document. In e-commerce, a list of relevant but distinctive products is useful for users to browse and make a purchase.