DIMACS Research Experience for Undergraduates

Name: Ben Sowell
Email: sowellb at carleton dot edu
Home Institution: Carleton College
Advisor: S. Muthu Muthukrishnan
Co-Advisors: Graham Cormode, Christian Sohler

About Me

I am a computer science major at Carleton College in Northfield, MN, where I will be a senior in the fall.

Project Description

As search engines such as Yahoo and Google continue to grow, they have developed increasingly sophisticated advertising models. In many cases, advertisers specify a maximum daily budget and a set of keywords that they wish to bid on, and then an automated auction is performed to determine which ads should be displayed for a given user query. The problem we are interested in (sometimes called the "AdWords problem") is to maximize the revenue while respecting the daily budget of each advertiser.

This problem can be modelled as an on-line bipartite graph matching problem. Given a set of keywords searches and a set of advertisers, we want to match advertisers to keywords to maximize the total revenue without exceeding any advertiser's daily budget or individual bids. This problem is called on-line because the assignments must be made immediately when each keyword is received. We can describe a similar off-line problem where we don't assign the matching until we have received all of the queries. One way of evaluating the on-line algorithm is to look at the competative ratio of revenue generated by the on-line algorithm to that generated by an optimal off-line algorithm.

In their paper "AdWords and Generalized On-line Matching," Aranyak Mehta et. al. present a deterministic algorithm that achieves a competative ratio of 1 - 1/e. My task will be to understand and implement this algorithm and to use it to test a number potential modifications.

Progress

7-13-06

I've finished a much modified version of the auction simulation program. It supports second price bidding, multiple slots, and constant and variable graphs.

6-23-06

I've added several other naive algorithms to my program. It can now choose bidders based on the algorithm from the paper, the maximum bid, the maximum budget left, and the minimum budget left. I've also created a version that runs all of these algorithms simultaneously for testing and data collection. The source code is available for AuctionHeuristic.c, AuctionParallel.c

6-20-06

I've finished implementing the online algorithm from "Adwords and Generalized On-line Matching." The source code is available in either C or Java.

My initial REU presentation is also available for download: (Keynote)(PowerPoint)(pdf)

References

Bala Kalyansundaram and Kirk R. Pruhs. An optimal deterministic algorithm for online b-matching. Theoretical Computer Science, 233(1-2):319-325, 2000.

R.M. Karp, U.V. Vazirani, and V.V. Vazirani. An optimal algorithm for online bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990.

A. Mehta, A. Saberi, U. Vazirani, and V. Vazirani. Adwords and generalized online matching. In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, 2005.