Assume you have a 2-dimensional pizza with $2n$ ingredients that you want to share with your friend. For this you are allowed to cut the pizza using several straight cuts, and then give every second piece to your friend. You want to do this fairly, that is, your friend and you should each get exactly half of each ingredient. How many cuts do you need? It was recently shown using topological methods that $n$ cuts always suffice. In this work, we study the computational complexity of finding such $n$ cuts. Our main result is that this problem is PPA-complete when the ingredients are represented as point sets. For this, we give a new proof that for point sets $n$ cuts suffice, which does not use any topological methods. We further prove several hardness results as well as a higher-dimensional variant for the case where the ingredients are well-separated.


翻译:假设你有一个2维比萨饼, 配有2n美元成份, 你愿意与朋友分享。 对于这一点, 你允许用几条直切, 将披萨切开, 然后将每一秒都分给朋友。 您想要公平这样做, 也就是说, 您的朋友和您应该每人得到每个成份的一半。 您需要多少切口? 最近用地形学方法显示, 削减一美元就足够了。 在这项工作中, 我们研究找到这种减价的计算复杂性。 我们的主要结果是, 当成分被标为点数时, 问题就是 PPA 完成 。 为此, 我们给出一个新的证据, 点设定 $n 的减价足够, 但不使用任何表面学方法 。 我们进一步证明一些硬性结果, 以及一个高维变量, 用于那些成分均匀分的案例 。

0
下载
关闭预览

相关内容

CC在计算复杂性方面表现突出。它的学科处于数学与计算机理论科学的交叉点,具有清晰的数学轮廓和严格的数学格式。官网链接:https://link.springer.com/journal/37
机器学习组合优化
专知会员服务
108+阅读 · 2021年2月16日
专知会员服务
44+阅读 · 2020年10月31日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
71+阅读 · 2020年8月2日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年11月3日
The Algorithmic Complexity of Tree-Clique Width
Arxiv
0+阅读 · 2021年11月3日
Arxiv
0+阅读 · 2021年11月3日
Arxiv
13+阅读 · 2021年5月25日
Arxiv
14+阅读 · 2020年12月17日
VIP会员
相关主题
相关VIP内容
机器学习组合优化
专知会员服务
108+阅读 · 2021年2月16日
专知会员服务
44+阅读 · 2020年10月31日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
71+阅读 · 2020年8月2日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
相关论文
Top
微信扫码咨询专知VIP会员