Maximizing submodular functions have been studied extensively for a wide range of subset-selection problems. However, much less attention has been given to the role of submodularity in sequence-selection and ranking problems. A recently-introduced framework, named \emph{maximum submodular ranking} (MSR), tackles a family of ranking problems that arise naturally when resources are shared among multiple demands with different budgets. For example, the MSR framework can be used to rank web pages for multiple user intents. In this paper, we extend the MSR framework in the streaming setting. In particular, we consider two different streaming models and we propose practical approximation algorithms. In the first streaming model, called \emph{function arriving}, we assume that submodular functions (demands) arrive continuously in a stream, while in the second model, called \emph{item arriving}, we assume that items (resources) arrive continuously. Furthermore, we study the MSR problem with additional constraints on the output sequence, such as a matroid constraint that can ensure fair exposure among items from different groups. These extensions significantly broaden the range of problems that can be captured by the MSR framework. On the practical side, we develop several novel applications based on the MSR formulation, and empirically evaluate the performance of the proposed~methods.
翻译:对一系列子模块问题进行了广泛的研究,对子模块功能最大化进行了广泛的研究,但对于子模块选择和排序问题,对子模块的作用给予的关注要少得多。最近推出的一个名为 emph{ 最大子模块排名} (MSR)的框架解决了一系列在资源在不同预算的多种需求之间共享时自然产生的排序问题。例如,MSR框架可用于对多个用户意图的网页进行排序。在本文中,我们扩展了流动环境中的MSR框架。特别是,我们考虑两种不同的流模式,并提出实用近似算法。在第一个流模式中,称为 emph{ 功能到达} (MSR),我们假设子模块的功能(需求)会持续进入一个流流中,而在第二个模型中,称为\emph{ 项到达},我们假设项目(资源)会持续到达。此外,我们研究MSR问题与产出序列的额外制约有关,例如可以确保不同群体项目之间公平接触的基质制约。在第一个流模式中,我们假设子(mSR) 的扩展会大大扩展了我们提出的MSR应用范围。