Nearly three decades ago, Bar-Noy, Motwani and Naor showed that no online edge-coloring algorithm can edge color a graph optimally. Indeed, their work, titled "the greedy algorithm is optimal for on-line edge coloring", shows that the competitive ratio of $2$ of the na\"ive greedy algorithm is best possible online. However, their lower bound required bounded-degree graphs, of maximum degree $\Delta = O(\log n)$, which prompted them to conjecture that better bounds are possible for higher-degree graphs. While progress has been made towards resolving this conjecture for restricted inputs and arrivals or for random arrival orders, an answer for fully general \emph{adversarial} arrivals remained elusive. We resolve this thirty-year-old conjecture in the affirmative, presenting a $(1.9+o(1))$-competitive online edge coloring algorithm for general graphs of degree $\Delta = \omega(\log n)$ under vertex arrivals. At the core of our results, and of possible independent interest, is a new online algorithm which rounds a fractional bipartite matching $x$ online under vertex arrivals, guaranteeing that each edge $e$ is matched with probability $(1/2+c)\cdot x_e$, for a constant $c>0.027$.


翻译:近30年前, Bar-Noy、 Motwani 和 Naor 表示, 任何在线边缘色彩算法都无法优化地显示图表的颜色。 事实上, 他们题为“ 贪婪算法是在线边缘颜色的最佳选择 ” 的作品显示, “ 贪婪算法” 的2美元的竞争性比率是最佳的在线选择。 但是, 他们的下约束要求约束度图, 最大值为$\Delta = O(\log n) $, 这促使他们推测, 高度图形有更好的界限。 虽然在解决限制投入和抵达或随机抵达订单的配方方面已经取得了进展, 但对于完全通用的\emph{对质的到达来说, 答案仍然是难以实现的。 我们用肯定的方式解决了这个三十年的配方的配方, $(1.9+o(1)) 美元 的有竞争力的在线边端算算法 = 美元= 美元= 美元(log n) 的顶值 。 在我们结果的核心, 以及可能的独立利益之下, $= 美元 美元 美元 的顶点 匹配的在线 双平位 。

0
下载
关闭预览

相关内容

专知会员服务
47+阅读 · 2021年4月18日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
28+阅读 · 2019年10月18日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
17种深度强化学习算法用Pytorch实现
新智元
30+阅读 · 2019年9月16日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【收藏】机器学习的Pytorch实现资源集合【附下载链接】
机器学习算法与Python学习
10+阅读 · 2018年9月8日
机器学习的Pytorch实现资源集合
专知
11+阅读 · 2018年9月1日
随波逐流:Similarity-Adaptive and Discrete Optimization
我爱读PAMI
5+阅读 · 2018年2月6日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】树莓派/OpenCV/dlib人脸定位/瞌睡检测
机器学习研究会
9+阅读 · 2017年10月24日
【推荐】TensorFlow手把手CNN实践指南
机器学习研究会
5+阅读 · 2017年8月17日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年7月5日
Arxiv
0+阅读 · 2021年7月5日
Arxiv
0+阅读 · 2021年7月1日
Arxiv
3+阅读 · 2018年10月18日
VIP会员
相关VIP内容
相关资讯
17种深度强化学习算法用Pytorch实现
新智元
30+阅读 · 2019年9月16日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
【收藏】机器学习的Pytorch实现资源集合【附下载链接】
机器学习算法与Python学习
10+阅读 · 2018年9月8日
机器学习的Pytorch实现资源集合
专知
11+阅读 · 2018年9月1日
随波逐流:Similarity-Adaptive and Discrete Optimization
我爱读PAMI
5+阅读 · 2018年2月6日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】树莓派/OpenCV/dlib人脸定位/瞌睡检测
机器学习研究会
9+阅读 · 2017年10月24日
【推荐】TensorFlow手把手CNN实践指南
机器学习研究会
5+阅读 · 2017年8月17日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员