License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2013.351
URN: urn:nbn:de:0030-drops-43856
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4385/
Li, Jian ;
Zhang, Zeyu
Ranking with Diverse Intents and Correlated Contents
Abstract
We consider the following document ranking problem: We have a collection of documents, each containing some topics (e.g. sports, politics, economics). We also have a set of users with diverse interests. Assume that user u is interested in a subset I_u of topics. Each user u is also associated with a positive integer K_u,
which indicates that u can be satisfied by any K_u topics in I_u. Each document s contains information for a subset C_s of topics. The objective is to pick one document at a time such that the average satisfying time is minimized, where a user's satisfying time is the first time that at least K_u topics in I_u are covered in the documents selected so far.
Our main result is an O(rho)-approximation algorithm for the problem, where rho is the algorithmic integrality gap of the linear programming relaxation of the set cover instance defined by the documents and topics. This result generalizes the constant approximations for generalized min-sum set cover and ranking with unrelated intents and the logarithmic approximation for the problem of ranking with submodular valuations (when the submodular function is the coverage function), and can be seen as an interpolation between these results. We further extend our model to the case when each user may be interested in more than one sets of topics and when the user's valuation function is XOS, and obtain similar results for these models.
BibTeX - Entry
@InProceedings{li_et_al:LIPIcs:2013:4385,
author = {Jian Li and Zeyu Zhang},
title = {{Ranking with Diverse Intents and Correlated Contents}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {351--362},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-64-4},
ISSN = {1868-8969},
year = {2013},
volume = {24},
editor = {Anil Seth and Nisheeth K. Vishnoi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/4385},
URN = {urn:nbn:de:0030-drops-43856},
doi = {10.4230/LIPIcs.FSTTCS.2013.351},
annote = {Keywords: Approximation Algorithm, Diversification, min-sum Set Cover}
}
|
Keywords: |
|
Approximation Algorithm, Diversification, min-sum Set Cover |
|
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) |
|
Issue Date: |
|
2013 |
|
Date of publication: |
|
10.12.2013 |
