Name
Abstract | ||
|---|---|---|
We consider the problem of recommending the best set of k items when there is an inherent ordering between items, expressed as a set of prerequisites (e.g., the movie 'Godfather I' is a prerequisite of 'Godfather II'). Since this general problem is computationally intractable, we develop 3 approximation algorithms to solve this problem for various prerequisite structures (e.g., chain graphs, AND graphs, AND-OR graphs). We derive worst-case bounds for these algorithms for these structures, and experimentally evaluate these algorithms on synthetic data. We also develop an algorithm to combine solutions in order to generate even better solutions, and compare the performance of this algorithm with the other three. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1871437.1871555 | CIKM |
Keywords | Field | DocType |
generalizing recommendation,general problem,best set,chain graph,k item,approximation algorithm,better solution,synthetic data,godfather ii,and-or graph,various prerequisite structure,graph theory | Graph theory,Data mining,Approximation algorithm,Graph,Computer science,Generalization,Theoretical computer science,Synthetic data | Conference |
Citations | PageRank | References |
16 | 0.74 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aditya Parameswaran | 1 | 1112 | 78.56 |
| Héctor García-Molina | 2 | 24359 | 5652.13 |
| Jeffrey D. Ullman | 3 | 13099 | 5226.28 |