Temporal graphs have been recently introduced to model changes to a given network that occur throughout a fixed period of time. We introduce and investigate the Temporal $\Delta$ Independent Set problem, a temporal variant of the well known Independent Set problem. This problem is e.g. motivated in the context of finding conflict-free schedules for maximum subsets of tasks, that have certain (changing) constraints on each day they need to be performed. We are specifically interested in the case where each task needs to be performed in a certain time-interval on each day and two tasks are in conflict on a day if their time-intervals overlap on that day. This leads us to considering Temporal $\Delta$ Independent Set on the restricted class of temporal unit interval graphs, i.e. temporal graphs where each layer is unit interval. We present several hardness results for this problem, as well as two algorithms: The first is an constant-factor approximation algorithm for instances where $\tau$, the total number of time steps (layers) of the temporal graph, and $\Delta$, a parameter that allows us to model some tolerance in the conflicts, are constants. For the second result we use the notion of order preservation for temporal unit interval graphs that, informally, requires the intervals of every layer to obey a common ordering. We provide an FPT algorithm parameterized by the size of minimum vertex deletion set to order preservation.


翻译:最近引入了时间图, 用于模拟在固定时间段内对特定网络的修改。 我们引入并调查Temalal $\ Delta$ 独立Set 问题, 这是众所周知的独立Set 问题的一个时间变体。 例如, 这个问题的动机在于为最大任务子集寻找无冲突的时间表, 任务子集在每天需要执行的某些( 变化) 限制。 我们特别感兴趣的是, 每个任务需要每天在某个时间间隔期间执行, 而两个任务如果在一天内时间间隔重叠, 则在某一天发生冲突。 这导致我们考虑Temoral $\ Delta$ 独立Set 问题, 这是在限制的时间单位间隔图表的类别上, 即每个层间距都有时间图的时间图。 我们为这一问题提出一些硬性结果, 以及两个算法: 第一个是每个任务需要在一定时间段内执行, 时间- 时间段的保存总步骤( 级数), 和 $\ Delta$, 一个参数, 使得我们能够用一个固定的时序, 排序。

0
下载
关闭预览

相关内容

因果推断,Causal Inference:The Mixtape
专知会员服务
105+阅读 · 2021年8月27日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
最佳实践:深度学习用于自然语言处理(三)
待字闺中
3+阅读 · 2017年8月20日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
7+阅读 · 2021年10月12日
VIP会员
相关VIP内容
因果推断,Causal Inference:The Mixtape
专知会员服务
105+阅读 · 2021年8月27日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
相关资讯
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
最佳实践:深度学习用于自然语言处理(三)
待字闺中
3+阅读 · 2017年8月20日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员