Better Multiple Intents Re-ranking

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.

Speaker Details

Nikhil Bansal is at the IBM T.J. Watson Research Center, where he currently manages the Algorithms group. His research interests are broadly in the area of design and analysis of algorithms, with particular focus on approximation and online algorithms. He obtained his PhD in 2003 from Carnegie Mellon University, and his Bachelor’s degree in 1999 from Indian Institute of Technology, Mumbai.

Date:
Speakers:
Nikhil Bansal
Affiliation:
IBM T.J. Watson Research