Better Multiple Intents Re-ranking

Опубликовано 7 сентября 2016, 17:27

The multiple intents re-ranking problem was introduced recently by Azar, Gamzu and Xin (STOC 2009) in the context of ordering results of a web search query. In this problem, we are given a universe of elements U and a collection of subsets S1,S2,..,Sm. Additionally, each set S has a covering requirement of K(S). The goal is to order the elements in U to minimize average covering time of a set, where set S is said to be covered at time t, if t is the earliest time at which K(S) elements from S appear in the ordering. This problem generalizes various problems: (i) If K(S) = 1 for all sets, we get the min-sum set cover problem, and (ii) If K(S) = |S| for all sets, we get the minimum-latency set cover problem. Recently, Azar et al. gave an elegant logarithmic approximation algorithm for this problem. They also gave O(1) approximations for some special cases. In this talk, I will describe an O(1) approximation for the general problem. Our result is based on formulating and rounding a strengthened LP relaxation of the problem based on the so-called Knapsack Cover Inequalities. This is joint work with Ravishankar Krishnaswamy and Anupam Gupta.