File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/FOCS46700.2020.00133
- Scopus: eid_2-s2.0-85100329255
- WOS: WOS:000652333400125
- Find via
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: AdWords in a Panorama
Title | AdWords in a Panorama |
---|---|
Authors | |
Keywords | Adwords online matching primal-dual |
Issue Date | 2020 |
Publisher | IEEE, Computer Society. The Journal's web site is located at https://ieeexplore.ieee.org/xpl/conhome/1000292/all-proceedings |
Citation | Proceedings of 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), Durham, NC, USA, 16-19 November 2020, p. 1416-1426 How to Cite? |
Abstract | Three decades ago, Karp, Vazirani, and Vazirani (STOC 1990) defined the online matching problem and gave an optimal (1-1/e)-competitive (about 0.632) algorithm. Fifteen years later, Mehta, Saberi, Vazirani, and Vazirani (FOCS 2005) introduced the first generalization called AdWords driven by online advertising and obtained the optimal (1-1/e) competitive ratio in the special case of small bids. It has been open ever since whether there is an algorithm for general bids better than the 0.5-competitive greedy algorithm. This paper presents a 0.5016-competitive algorithm for AdWords, answering this open question on the positive end. The algorithm builds on several ingredients, including a combination of the online primal dual framework and the configuration linear program of matching problems recently explored by Huang and Zhang (STOC 2020), a novel formulation of AdWords which we call the panorama view, and a generalization of the online correlated selection by Fahrbach, Huang, Tao, and Zadimorghaddam (FOCS 2020) which we call the panoramic online correlated selection. |
Persistent Identifier | http://hdl.handle.net/10722/301409 |
ISSN | |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Huang, Z | - |
dc.contributor.author | Zhang, Q | - |
dc.contributor.author | Zhang, Y | - |
dc.date.accessioned | 2021-07-27T08:10:38Z | - |
dc.date.available | 2021-07-27T08:10:38Z | - |
dc.date.issued | 2020 | - |
dc.identifier.citation | Proceedings of 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), Durham, NC, USA, 16-19 November 2020, p. 1416-1426 | - |
dc.identifier.issn | 1523-8288 | - |
dc.identifier.uri | http://hdl.handle.net/10722/301409 | - |
dc.description.abstract | Three decades ago, Karp, Vazirani, and Vazirani (STOC 1990) defined the online matching problem and gave an optimal (1-1/e)-competitive (about 0.632) algorithm. Fifteen years later, Mehta, Saberi, Vazirani, and Vazirani (FOCS 2005) introduced the first generalization called AdWords driven by online advertising and obtained the optimal (1-1/e) competitive ratio in the special case of small bids. It has been open ever since whether there is an algorithm for general bids better than the 0.5-competitive greedy algorithm. This paper presents a 0.5016-competitive algorithm for AdWords, answering this open question on the positive end. The algorithm builds on several ingredients, including a combination of the online primal dual framework and the configuration linear program of matching problems recently explored by Huang and Zhang (STOC 2020), a novel formulation of AdWords which we call the panorama view, and a generalization of the online correlated selection by Fahrbach, Huang, Tao, and Zadimorghaddam (FOCS 2020) which we call the panoramic online correlated selection. | - |
dc.language | eng | - |
dc.publisher | IEEE, Computer Society. The Journal's web site is located at https://ieeexplore.ieee.org/xpl/conhome/1000292/all-proceedings | - |
dc.relation.ispartof | Symposium on Foundations of Computer Science Annual Proceedings | - |
dc.relation.ispartof | The 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS) | - |
dc.rights | Symposium on Foundations of Computer Science Annual Proceedings. Copyright © IEEE, Computer Society. | - |
dc.rights | ©2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | - |
dc.subject | Adwords | - |
dc.subject | online matching | - |
dc.subject | primal-dual | - |
dc.title | AdWords in a Panorama | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Huang, Z: zhiyi@cs.hku.hk | - |
dc.identifier.authority | Huang, Z=rp01804 | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1109/FOCS46700.2020.00133 | - |
dc.identifier.scopus | eid_2-s2.0-85100329255 | - |
dc.identifier.hkuros | 323370 | - |
dc.identifier.spage | 1416 | - |
dc.identifier.epage | 1426 | - |
dc.identifier.isi | WOS:000652333400125 | - |
dc.publisher.place | United States | - |