We introduce a model involving two adversaries Buster and Fixer taking turns modifying a connected graph, where each round consists of Buster deleting a subset of edges and Fixer responding by adding edges from a reserve set of weighted edges to leave the graph connected. With the weights representing the cost for Fixer to use specific reserve edges to reconnect the graph, we provide a reasonable definition for what should constitute an optimal strategy for Fixer to keep the graph connected for as long as possible as cheaply as possible, and prove that a greedy strategy for Fixer satisfies our conditions for optimality.


翻译:我们引入了一种模式,其中涉及两名对手Buster和Fixer轮流修改一个链接的图表,每轮由Buster删除一组边缘和Fixer,从一组加权边缘的储备中添加边缘,以留下相连接的图表。由于Sixer使用特定储备边缘重新连接图形的成本,我们提供了一个合理的定义,说明什么应该构成Fixer尽可能廉价地保持该图表连接的最佳战略,并证明Cixer的贪婪策略满足了我们最优化的条件。

0
下载
关闭预览

相关内容

专知会员服务
17+阅读 · 2020年9月6日
【Google】平滑对抗训练,Smooth Adversarial Training
专知会员服务
48+阅读 · 2020年7月4日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
154+阅读 · 2020年5月26日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年3月26日
Arxiv
0+阅读 · 2021年3月26日
Arxiv
7+阅读 · 2020年6月29日
VIP会员
相关VIP内容
专知会员服务
17+阅读 · 2020年9月6日
【Google】平滑对抗训练,Smooth Adversarial Training
专知会员服务
48+阅读 · 2020年7月4日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
154+阅读 · 2020年5月26日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员