我们先将问题进行简化来探寻更好的算法，这些简化包括：
- 每条查询只显示一个广告
- 所有广告商的预算都相等
- 所有广告的点击率都相等
- 所有的出价不是0就是1
有一种Balance算法对贪心算法做了简单改进，它在仅有两个广告商的情况下竞争率为3/4，随着广告商数目的不断增长，竞争率会下降到1-1/e（约为0.63），但不会更低。
在前面的简化条件下，Balance算法将查询分配给出价最高且剩余预算最多的广告商，考虑到出价不是0就是1，所以在算法运行过程中通常是根据剩余预算做决策，如果剩余预算相同，则可以随机选择。
当于所有广告商出价并不是非0即1这中更一般性的情况时，我们需要对Balance算法进行改进，以保证其竞争率仍然为1-1/e（约为0.63）。
我们这样做，当某个查询q到来，广告商Ai对q的出价是xi，另外假定Ai预算中的结余比例为fi，令Ψi=xi(1-e^-fi)，将q分配给具有最大Ψ值的广告商。
对于adwords问题，不存在竞争率超过1-1/e的在线算法。
前面讲的adwords问题是查询词与对查询词出价的广告商之间的匹配问题，接下来我们要处理的是文档和投标之间的匹配算法，区别在于，广告商仍然是对词出价，但我们考虑匹配的不再是查询词，而是文档，文档是一个更大的词语集合。
这种文档和词的匹配问题与搜索引擎所解决的问题看起来十分类似，但实际上，搜索引擎是以词查相关文档，但是这里是为文档找到有投标的相关词。
而且需要注意的是，投标也是一个词集，虽然比较小，并不是单个词。
对于投标，我们将投标表示成某种排序下的词语表，并为词语表添加一个状态信息，用于记录列表中从头开始已经和当前文档匹配上的词语数目。如果一个投标词语表中的所有词语都出现在文档中，不管这些词语是否和投标中同序，不管他们是否相邻，都认为投标和文档匹配。
对于投标和文档（该段中统称为文档），在匹配时，为了减少工作量，我们以低频优先的方式对词语排序。由于出现在所有文档中的不同词数目本质上是无限的，所以我们选择一种折中的方法，我们找到所有文档中最常见的n个词，比如10万或者100万，这n个词会按照频率排序，并占据每篇文档的尾部，剩下的低频词，我们假定他们频率都一样并按照词典序排在列表的前面。我们以上述的方式来表示每一篇文档，文档会按照这种低频优先的方式存储在哈希表中，其中第一个词作为哈希键。
大规模投标和文档的管理过程如下图所示：
图中存在两张哈希表（投标的哈希表索引和部分匹配的投标）和一张匹配投标表，第一张哈希表以之前讲过的顺序记录了所有投标，第二张哈希表是为了保存那些已经部分匹配的投标的副本。表之间的切换以及第二个表的循环下面会讲。
在这个过程的开始，我们将文档中的词按照同样的顺序进行排列，并去掉重复词。
对于文档的排序列表中的每个词w，进行如下操作：
- 在部分匹配哈希表中使用w作为哈希键，找到那些以w为键的投标（图中的a）
- 对这样的每个投标b，如果w是b词集中的最后一个词，将b移到已匹配投标表中（图中的b）
- 如果w不是b中的最后那个词，则对b的状态值加1，并利用比新状态值大1的位置上对应的词作为哈希键重新对b进行哈希处理（图中的c）
- 以w为哈希键检查第一个哈希表（图中的d）
- 如果该投标b词集中只有一个词，那么将它复制到已匹配投标中去（图中的e）
- 如果b中不止一个词，那么将它以状态1放到第二张部分匹配投标表中，并使用b中的第二个词作为哈希键。
然后最后输出已匹配投标表。
这样某个投标只有在其最低频词出现在文档时才会复制到第二个哈希表中。
