标题： 高效且实用的用于内容流广告的近似算法 显示英文标题

标题： Efficient and Practical Approximation Algorithms for Advertising in Content Feeds

摘要： 平台如X（前身为Twitter）和TikTok提供的内容流被用户每天消费。 在本文中，我们重新审视了内容流中的原生广告问题，该问题由Ieong等人提出。 给定一系列与用户兴趣或信息搜索相关的有机项目（例如视频或帖子），目标是在有机内容中插入广告，以最大化奖励函数（例如点击次数），同时考虑两个因素：（1）广告只能在相关的内容项之后插入；（2）用户在消费内容或广告后注意力会下降。 这些考虑提供了一个自然的模型，用于捕捉广告效果和用户体验。 在本文中，我们设计了快速且实用的2-近似贪心算法，解决了相关优化问题，优于目前最佳的实用算法，该算法仅能达到约4的近似因子。 我们的算法利用了一个反直觉的观察，即虽然顶部项目似乎由于用户注意力的下降而更重要，但妥善处理底部项目是获得改进的近似保证的关键。 然后，我们对该问题进行了首次全面的实证评估，展示了我们方法的强大实证性能。 显示英文摘要

摘要： Content feeds provided by platforms such as X (formerly Twitter) and TikTok are consumed by users on a daily basis. In this paper, we revisit the native advertising problem in content feeds, initiated by Ieong et al. Given a sequence of organic items (e.g., videos or posts) relevant to a user's interests or to an information search, the goal is to place ads within the organic content so as to maximize a reward function (e.g., number of clicks), while accounting for two considerations: (1) an ad can only be inserted after a relevant content item; (2) the users' attention decays after consuming content or ads. These considerations provide a natural model for capturing both the advertisement effectiveness and the user experience. In this paper, we design fast and practical 2-approximation greedy algorithms for the associated optimization problem, improving over the best-known practical algorithm that only achieves an approximation factor of~4. Our algorithms exploit a counter-intuitive observation, namely, while top items are seemingly more important due to the decaying attention of the user, taking good care of the bottom items is key for obtaining improved approximation guarantees. We then provide the first comprehensive empirical evaluation on the problem, showing the strong empirical performance of our~methods.