An algorithm for number-partitioning is called value-monotone if whenever one of the input numbers increases, the objective function (the largest sum or the smallest sum of a subset in the output) weakly increases. This note proves that the List Scheduling algorithm and the Longest Processing Time algorithm are both value-monotone. This is in contrast to another algorithm -- MultiFit -- which is not value-monotone.


翻译:数字分割的算法称为值分子式。 如果输入数字增加, 目标函数( 输出中子数的最大和或最小和) 增长微弱, 则称为值分子式算法。 注意证明列表排制算法和最长处理时间算法都是数值式算法。 这与另一个算法- 多功能法- 而不是数值式算法不同。

0
下载
关闭预览

相关内容

【干货书】机器人元素Elements of Robotics ,311页pdf
专知会员服务
34+阅读 · 2021年4月16日
专知会员服务
76+阅读 · 2021年3月16日
专知会员服务
52+阅读 · 2020年9月7日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
IEEE2018|An Accurate and Real-time 3D Tracking System for Robots
lightgbm algorithm case of kaggle(上)
R语言中文社区
8+阅读 · 2018年3月20日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年12月15日
Arxiv
0+阅读 · 2021年12月13日
VIP会员
相关VIP内容
【干货书】机器人元素Elements of Robotics ,311页pdf
专知会员服务
34+阅读 · 2021年4月16日
专知会员服务
76+阅读 · 2021年3月16日
专知会员服务
52+阅读 · 2020年9月7日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
IEEE2018|An Accurate and Real-time 3D Tracking System for Robots
lightgbm algorithm case of kaggle(上)
R语言中文社区
8+阅读 · 2018年3月20日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员