停止依赖无选择,不要重复移动:商品组合优化的最优、高效和实用算法
我们考虑了一种混合物优化问题,针对在线随机匹配的情况,我们提出了一种多项式时间近似算法,其近似比为至少 1-ln (2-1 /e) 或 0.51,并基于线性规划松弛进一步改进了以前的随机舍入方案。在一般的混合物问题中,我们建立了第一个常数因子近似比为 0.09 的情况,这种情况下不同类型的客户赋予不同价值,并建立了近似比为 0.15 的情况,即不同客户赋予每个项目相同的价值。
Aug, 2019
现实世界中的产品组合选择是物理零售商面临的一项关键挑战,通过有效地与购物者的喜好相匹配,可以增加销售并减少缺货。为解决这些挑战,我们引入了一个实时推荐系统,利用 3D 计算机视觉和感知技术,以及借助贝叶斯奖励模型、空间聚类和基于图的候选生成算法,以适应异质的消费者喜好和解决组合搜索问题。通过在真实店铺进行多次测试和观察研究,我们展示了销售量分别提高了 35% 和 27%。
Jun, 2024
本文提出一种针对多个资源分配问题的算法体系,将在线请求建模为每次从未知的概率分布中独立抽取,给出了一个在任意接受数据的情况下获得一定比例最优解的单一算法,并且探究了如何在任意情况下应对敌对分布。同时,文中提出了解决大型 LPs 混合装填覆盖问题的快速算法,并分析了该算法在在线拍卖、网络路由和广告策略方案等特殊情况下的应用。
Mar, 2019
优化用户排序列表的算法将用户偏好和物品位置的变化考虑在内,通过上界调整预测的用户满意度分数,并选择最大化这些调整分数的排序操作,以在异质用户中个性化用户体验。该算法在实验中表现优于基线模型。
Jun, 2024
本研究旨在通过自适应挑选子集并收集偏好反馈,在 Plackett-Luce 模型下解决 PAC 排名问题,提出了新的 pivot trick 技巧,从而实现了在一定概率下识别 n 个项目的 ε- 最优排名,(m-1)/m 降低的样本复杂度和对称排名算法的阶无法提高的。
Oct, 2018
本文提出了一种名为 PL-Rank 的新算法,用于估计 PL 排名模型关于相关性和公平度量的梯度,相比现有的策略梯度方法,PL-Rank 的采样效率更高且计算成本更低,可以用于更真实、更公平的实际排名系统。
May, 2021
该研究提出一种利用机器学习建议进行在线资源分配决策的框架,算法类似于一种 Pareto 最优算法,它能够在机器学习建议存在不准确性的情况下,在保证一定的性能准则的前提下尽量提高稳健比率,最终证明与基准算法相比,该算法能够在最坏和平均情况之间实现平衡,并且获得更好的性能。
Jun, 2023
通过在线广告分配,我们从理论和实践角度研究在线随机装箱线性规划。我们首先展示了一种近似最优的在线算法,证明了基于训练的简单原始对偶算法在随机顺序随机模型下实现(1 - o (1)) 逼近担保,这是对同一问题敌对变量的对数或常数逼近的显著改进;然后,我们侧重于在线显示广告分配问题,研究了各种基于训练和在线分配算法在实际数据集上的效率和公平性。我们的实验评估确认了基于训练的原始对偶算法在真实数据集上的有效性,并指出公平性和效率之间的内在权衡。
Jan, 2010