亲爱的研友该休息了!由于当前在线用户较少,发布求助请尽量完整的填写文献信息,科研通机器人24小时在线,伴您度过漫漫科研夜!身体可是革命的本钱,早点休息,好梦!

AdWords in a Panorama

展开图 计算机科学 计算机视觉 数学 人工智能
作者
Zhiyi Huang,Qiankun Zhang,Yuhao Zhang
出处
期刊:SIAM Journal on Computing [Society for Industrial and Applied Mathematics]
卷期号:53 (3): 701-763
标识
DOI:10.1137/22m1478896
摘要

.Three decades ago, Karp, Vazirani, and Vazirani [Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990, pp. 352–358] defined the online matching problem and gave an optimal \(1-\frac{1}{e} \approx 0.632\)-competitive algorithm. Fifteen years later, Mehta et al. [J. ACM, 54 (2007), pp. 22:1–22:19] introduced the first generalization called AdWords driven by online advertising and obtained the optimal \(1-\frac{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 [Proceedings of the 52nd ACM Symposium on Theory of Computing, 2020], a novel formulation of AdWords which we call the panorama view, and a generalization of the online correlated selection by Fahrbach et al. [Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science, 2020], which we call the panoramic online correlated selection.Keywordsonline matchingAdWords problemcompetitive ratioprimal dualonline correlated selectionMSC codes68W27
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
更新
大幅提高文件上传限制,最高150M (2024-4-1)

科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
kaginagain发布了新的文献求助10
2秒前
4秒前
jiyang应助白华苍松采纳,获得20
9秒前
9秒前
万能图书馆应助dusjsj采纳,获得10
9秒前
Owen应助kaginagain采纳,获得10
29秒前
45秒前
勤恳慕蕊完成签到 ,获得积分10
49秒前
奋斗的蓝蜗牛完成签到,获得积分10
52秒前
1分钟前
1分钟前
迅速的蜡烛完成签到 ,获得积分10
1分钟前
1分钟前
领导范儿应助科研通管家采纳,获得10
1分钟前
科研通AI2S应助科研通管家采纳,获得10
1分钟前
2分钟前
Shicheng完成签到,获得积分10
2分钟前
2分钟前
炸鸡年糕完成签到,获得积分10
2分钟前
绝尘发布了新的文献求助10
2分钟前
学术垃圾产出完成签到,获得积分10
3分钟前
3分钟前
陈媛发布了新的文献求助10
3分钟前
DD完成签到 ,获得积分10
3分钟前
3分钟前
成就的笑南完成签到 ,获得积分10
3分钟前
3分钟前
丸子鱼完成签到 ,获得积分10
3分钟前
陈媛发布了新的文献求助10
3分钟前
豆包完成签到 ,获得积分10
3分钟前
爆米花应助科研通管家采纳,获得10
3分钟前
科研通AI2S应助科研通管家采纳,获得10
3分钟前
完美世界应助陈媛采纳,获得10
4分钟前
李爱国应助绝尘采纳,获得10
4分钟前
4分钟前
4分钟前
HOW完成签到 ,获得积分10
4分钟前
4分钟前
陈媛发布了新的文献求助10
4分钟前
Xii完成签到 ,获得积分10
4分钟前
高分求助中
Earth System Geophysics 1000
Co-opetition under Endogenous Bargaining Power 666
Medicina di laboratorio. Logica e patologia clinica 600
Handbook of Marine Craft Hydrodynamics and Motion Control, 2nd Edition 500
Sarcolestes leedsi Lydekker, an ankylosaurian dinosaur from the Middle Jurassic of England 500
《关于整治突出dupin问题的实施意见》(厅字〔2019〕52号) 500
Language injustice and social equity in EMI policies in China 500
热门求助领域 (近24小时)
化学 医学 生物 材料科学 工程类 有机化学 生物化学 物理 内科学 纳米技术 计算机科学 化学工程 复合材料 基因 遗传学 催化作用 物理化学 免疫学 量子力学 细胞生物学
热门帖子
关注 科研通微信公众号,转发送积分 3213132
求助须知:如何正确求助?哪些是违规求助? 2861908
关于积分的说明 8131154
捐赠科研通 2527829
什么是DOI,文献DOI怎么找? 1361847
科研通“疑难数据库(出版商)”最低求助积分说明 643516
邀请新用户注册赠送积分活动 615877