约束条件下的买方对卖方推荐

对于每个卖方，冲突阈值t（参考第4节）设置为与卖方相关的冲突买方对总数的50%。183690 367380 551070 734760变量数（边）货币（*100万美元）0 200 400 600 8000 20 40 60 80 100时间（秒）货币时间图6：大规模数据集上的贪婪算法显示其可伸缩性。在图6中，运行时间几乎呈线性增加，当变量（边）的数量相当大时，只需要大约104秒就可以得到一个解，734760！5.2.2 CAC-RECILP配方的ILP配方使我们能够充分利用THLP解算器（Gurobi）来解决更大尺寸的CAC-REC问题。在本节中，我们进行了更大规模的实验，以比较不同方法的解决方案，即ILP、带舍入的LP和贪婪。我们使用第5.1节中描述的相同方法创建了一个0.16%密度的二分图。完整的图表包括18742名买家、1884名卖家和56520条边。我们还从完整的图中提取了三个不同大小的子集，即使用25%、50%和75%的边总数（买方和卖方节点的数量相应减少）。度约束比、约束对比分别为50%和10%。每个卖方的冲突阈值t（参考第4节）设置为与卖方相关的冲突买方对总数的50%。图7显示了不同数据集上不同方法的解决方案比较。图7显示了在货币权重和秩权重上使用舍入和贪婪算法的LP非常有希望的结果；它们只比ILP得到的最优整数解稍差。

与SDP实验相比，本实验还验证了在大数据集上使用舍入法的LP和GR-EEDY的效果，因为我们在本节中使用的图形被认为比SDP实验中使用的图形更大。密度（0.16%）也是真实世界图形（0.016%）的10倍。因此，我们的LP公式改善了解决大规模CAC-REC问题的可扩展性。在公元0年。25 0.5 0.75 1占所有EdgeMoney（*100万美元）的0 20 40 80 ILPLP。贪婪的金钱解决方案。25 0.5 0.75 1所有EdgeBank解决方案的百分比（*100万）0 50 100 150 200 250 ILPLP。roundingGREEDY（b）秩解图7:CAC RECon大规模数据集的线性规划实验。此外，虽然ILP是NP难的（运行时间可能很长），但我们可以使用更快的贪婪方法或带舍入的LP来提高效率。6.结论我们引入了一个新的推荐问题，即aimsat在容量和冲突约束下向卖家推荐买家（RBS）。我们提供了两种RBS的正式定义，即C-REC和CAC-REC，以解决不同的TRB场景。我们认为C-REC可以用线性规划有效地解决。然而，考虑到买家之间的冲突，苏格兰皇家银行的复杂性显著增加。我们证明了CAC-REC是NP难的。然后，我们提出了一种带roun-ding过程的SDP算法和一种贪婪算法来求解CAC-REC。我们使用真实数据集进行的大量实验结果表明，所提出的算法可以获得接近最优的解。最后，我们证明了贪婪算法是高度可扩展的。感谢Terapeak Inc.为本研究提供电子商务数据。在本节的实验中，ILP的最长运行时间约为10分钟。7.参考文献[1]O.Amini，D.Peleg，S.P\'erennes，I.Sau，andS。索拉布。

关于某种程度约束子图问题的可逼近性。离散应用数学，160（12）：1661-16792012。[2] A.Felfernig和R.D.Burke。基于约束的推荐系统：技术和研究问题。ICEC，2008年第3页。[3] M.卡里姆扎德甘和C.翟。限制多方面专业知识匹配，以供委员会审查分配。在CIKM中，第1697-1700页，2009年。[4] M.卡里姆扎德甘和C.翟。整数线性规划用于受约束的多方面CommitteerView分配。《信息处理与管理》，48（4）：725–740，2012年。[5] M.卡里姆扎德根、C.翟和G.贝尔福德。多方面的专业知识匹配用于评审分配。在CIKM中，第1113-1122页。ACM，2008年。[6] 科瓦拉先生和斯廷格尔先生。用迭代求解器改进的障碍法求解大规模sdp问题。数学程序109(2-3):413–444, 2007.[7] 梅斯特。贪婪的近似算法。InESA，第528-539页，2006年。[8] A.G.帕拉米斯瓦兰、P.维尼蒂斯和H。加西亚·莫利纳。具有复杂约束的推荐系统：课程推荐视角。ACM Trans。中导系统。，29(4):20, 2011.[9] W.H.出版社、S.A.特科尔斯基、W.T.维特林和B。P.弗兰纳里。C语言中的数字配方：科学计算的艺术（第二版）。剑桥大学出版社，1992年。[10] 雷布曼。总单模块性和运输问题：一个推广。线性代数及其应用，8（1）：11-241974。[11] A.施里弗。线性和整数编程理论。约翰·威利父子公司，美国纽约州纽约市，1986年。[12] C·J·泰勒。关于将会议论文最优分配给审稿人的问题。技术报告MS-CIS-08-3，宾夕法尼亚大学计算机和信息科学系，2008年。[13] K.C.Toh、M.Todd和R.H.T–ut–unc–u.Sd pt3–用于半精确编程的amatlab软件包。优化方法和软件，11:545–5811999。[14] R。

H·T¨ut¨unc¨u，K·C·Toh和M·J·托德。用sdpt 3求解半限定二次线性规划。数学程序95(2):189–217, 2003.[15] 谢先生、L.V.S.Lakshmanan和P.T.Wood。打破推荐框：从商品到包装。在RecSys，第151-158页，2010年。[16] M.Zanker和M.Jessenitschnig。在推荐系统中探索明确客户需求的案例研究。用户模型。用户适应。互动19(1-2):133–166, 2009.