The world is dynamic and changes over time, thus any optimization problem used to model real life problems must address this dynamic nature, taking into account the cost of changes to a solution over time. The multistage model was introduced with this goal in mind. In this model we are given a series of instances of an optimization problem, corresponding to different times, and a solution is provided for each instance. The strive for obtaining near-optimal solutions for each instance on one hand, while maintaining similar solutions for consecutive time units on the other hand, is quantified and integrated into the objective function. In this paper we consider the Generalized Multistage $d$-Knapsack problem, a generalization of the multistage variants of the Multiple Knapsack problem, as well as the $d$-Dimensional Knapsack problem. We present a PTAS for Generalized Multistage $d$-Knapsack.


翻译:世界是动态的,随着时间的变化而变化,因此,用于模拟现实生活问题的任何优化问题都必须解决这种动态性质,同时考虑到随着时间的推移改变解决办法的成本。多阶段模式是本着这一目标引入的。在这个模式中,我们得到了一系列与不同时间相对应的优化问题实例,并为每个实例提供了解决办法。努力为每个实例获得接近最佳的解决方案,同时为连续时间单位保留类似的解决方案,将量化,并纳入到目标功能中。在本文件中,我们考虑了通用多阶段多阶段美元-Knapsack问题,多级Knapsack问题多阶段变体的概括化,以及美元-Dimensional Knapsack问题。我们为通用多级多阶段的美元-Knapsack提供了一种PATAS。我们为通用多级的多级元-Knapsack 提供了一种通用的 PTAS。

0
下载
关闭预览

相关内容

机器学习组合优化
专知会员服务
110+阅读 · 2021年2月16日
【CVPR2020】MSG-GAN:用于稳定图像合成的多尺度梯度GAN
专知会员服务
29+阅读 · 2020年4月6日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
154+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
177+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
已删除
将门创投
4+阅读 · 2019年5月8日
逆强化学习-学习人先验的动机
CreateAMind
16+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Arxiv
92+阅读 · 2020年2月28日
Efficiently Embedding Dynamic Knowledge Graphs
Arxiv
14+阅读 · 2019年10月15日
Arxiv
7+阅读 · 2018年3月21日
VIP会员
相关VIP内容
机器学习组合优化
专知会员服务
110+阅读 · 2021年2月16日
【CVPR2020】MSG-GAN:用于稳定图像合成的多尺度梯度GAN
专知会员服务
29+阅读 · 2020年4月6日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
154+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
177+阅读 · 2019年10月11日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
已删除
将门创投
4+阅读 · 2019年5月8日
逆强化学习-学习人先验的动机
CreateAMind
16+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Top
微信扫码咨询专知VIP会员