作者：王瑾超; 杨滨源; 周春花; 母桑妮双边匹配在线算法对偶规划平衡函数竞争比
摘要：如何分配关键词给广告厂商以使得搜索引擎公司收入最大实际上是一个在线双边匹配问题。贪婪算法只考虑到厂商出价,竞争比只有1/2。本文分配方案不仅考虑到每个厂商的出价,而是通过引入平衡函数综合考虑厂商出价和未使用的预算,然后将关键词分配给能够使得出价和平衡函数乘积最大的厂商。最后将问题转化为一个线性规划族,通过求解其对偶规划族算出平衡函数的具体形式,并得出本文的分配方案能使得竞争比达到1-1/e,优于其他任意随机算法的竞争比。
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
