Thumbnail
Access Restriction
Subscribed

Author Mehta, Aranyak ♦ Saberi, Amin ♦ Vazirani, Umesh ♦ Vazirani, Vijay
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2007
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Keyword auctions ♦ Online algorithms ♦ Search engines
Abstract How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a trade-off revealing LP and use it to derive an optimal algorithm achieving a competitive ratio of $1™1/\textit{e}$ for this problem.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2007-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 54
Issue Number 5


Open content in new tab

   Open content in new tab
Source: ACM Digital Library