Motivated by recent developments in designing algorithms based on individual item scores for solving utility maximization problems, we study the framework of using test scores, defined as a statistic of observed individual item performance data, for solving the budgeted stochastic utility maximization problem. We extend an existing scoring mechanism, namely the replication test scores, to incorporate heterogeneous item costs as well as item values. We show that a natural greedy algorithm that selects items solely based on their replication test scores outputs solutions within a constant factor of the optimum for a broad class of utility functions. Our algorithms and approximation guarantees assume that test scores are noisy estimates of certain expected values with respect to marginal distributions of individual item values, thus making our algorithms practical and extending previous work that assumes noiseless estimates. Moreover, we show how our algorithm can be adapted to the setting where items arrive in a streaming fashion while maintaining the same approximation guarantee. We present numerical results, using synthetic data and data sets from the Academia.StackExchange Q&A forum, which show that our test score algorithm can achieve competitiveness, and in some cases better performance than a benchmark algorithm that requires access to a value oracle to evaluate function values.
翻译:基于个别项目分数设计算法以解决公用事业最大化问题方面的最新动态,我们研究了使用测试分数的框架,测试分数的定义是观察到的个别项目性能数据统计,以解决编入预算的随机性能效用最大化问题。我们扩展了现有的评分机制,即复制测试分数,将不同项目成本和项目价值纳入其中。我们展示了一种天然贪婪算法,这种算法仅根据复制项目测试分数的计算法来选择项目,这种算法是用于最有利于广泛类别的公用事业功能的经常系数。我们的算法和近似保证假定,测试分数是对个别项目价值边际分布的某些预期值的杂音估计,从而使我们的算法具有实用性,并扩展了假定无噪音估计的先前工作。此外,我们展示了我们的算法如何适应项目以流态到达的环境,同时保持同样的近似保证。我们用合成数据和Academial的数据集来提供数字结果,表明我们的测试分数算法可以取得竞争力,在某些情况下比基准算法更好的业绩,需要获得价值或骨质来评估价值。