In multistage perfect matching problems we are given a sequence of graphs on the same vertex set and asked to find a sequence of perfect matchings, corresponding to the sequence of graphs, such that consecutive matchings are as similar as possible. More precisely, we aim to maximize the intersections, or minimize the unions between consecutive matchings. We show that these problems are NP-hard even in very restricted scenarios. We propose new approximation algorithms and present methods to transfer results between different problem variants without loosing approximation guarantees.


翻译:在多阶段完美匹配问题中,在同一个顶点设置上,我们被给定了一个图表序列,要求我们找到一个与图表序列相对应的完美匹配序列,以便相继匹配尽可能相似。更准确地说,我们的目标是尽量扩大交叉点,或者尽量减少连续匹配之间的交汇点。我们显示,这些问题即使在非常有限的情景下也是难以解决的。我们提出了新的近似算法和目前在不同问题变量之间转移结果的方法,而不会失去近似保证。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
吴恩达新书《Machine Learning Yearning》完整中文版
专知会员服务
145+阅读 · 2019年10月27日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
【泡泡汇总】CVPR2019 SLAM Paperlist
泡泡机器人SLAM
14+阅读 · 2019年6月12日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
LibRec 精选:基于参数共享的CNN-RNN混合模型
LibRec智能推荐
6+阅读 · 2019年3月7日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
论文浅尝 | Improved Neural Relation Detection for KBQA
开放知识图谱
13+阅读 · 2018年1月21日
Arxiv
6+阅读 · 2021年6月4日
Arxiv
13+阅读 · 2018年4月6日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
Top
微信扫码咨询专知VIP会员