Heuristic algorithms for diversity-aware balanced multi-way number partitioning
Heuristic algorithms for diversity-aware balanced multi-way number partitioning
复制标题
用于多样性感知平衡多路数字划分的启发式算法
DOI：
10.1016/j.patrec.2020.05.022
复制
发表时间：
2020-08
影响因子：
5.1
通讯作者：
Xuelian Deng
中科院分区：
文献类型：
--
作者：
Jilian Zhang;Kaimin Wei;Xuelian Deng
数划分是人工智能中的一个经典问题。而平衡多路数划分问题（BMNP）的目标是将一组数划分为多个子集，使得（1）每个子集包含相同数量的数，（2）子集和相等。BMNP问题在真实的世界中有着广泛的应用，包括任务分配、CPU调度、数据中心文件放置、多源数据处理等。DBMNP与BMNP的不同之处在于每个数字都与一个类型属性相关联。除了BMNP的两个目标外，DBMNP还要求每个子集中的数字类型尽可能多样化。为了解决这个问题，我们提出了三个启发式算法，以最小化子集和之间的差异，同时最大化每个子集的多样性。大量的实验进行评估我们提出的算法的有效性。
Number partitioning is a classic problem in artificial intelligence. And balanced multi-way number partitioning problem (BMNP) aims to partition a set of numbers into multiple subsets, such that (1) each subset contains the same number of numbers and (2) the subset sums are equal. The BMNP problem has various applications in real world scenarios, including task allocation, CPU scheduling, file placement in data center, multi-source data processing, etc. In this paper, we consider the problem of diversity-aware balanced multi-way number partitioning (DBMNP). DBMNP differs from BMNP, in that each number is associated with a type attribute. In addition to the two goals of BMNP, DBMNP also requires that the types of numbers in each subset are as diversified as possible. To solve the problem, we propose three heuristic algorithms to minimize the difference between subset sums and at the same time maximize diversify of each subset. Extensive experiments are conducted to evaluate the effectiveness of our proposed algorithms.
登录
查看更多内容
在成本敏感型学习中有效利用缺失数据
DOI：
10.1109/tkde.2019.2956530
发表时间：
2019-11
影响因子：
8.9
作者：
Zhu Xiaofeng;Yang Jianye;Zhang Chengyuan;Zhang Shichao
通讯作者：
Zhang Shichao
DOI：
10.1145/3130348.3130369
发表时间：
1998-08
期刊：
ACM SIGIR Forum
影响因子：
--
作者：
J. Carbonell;Jade Goldstein-Stewart
通讯作者：
J. Carbonell;Jade Goldstein-Stewart
DOI：
--
发表时间：
2017-12
期刊：
ArXiv
影响因子：
--
作者：
Jinyu Wang;Minquan Cheng;Qifa Yan;Xiaohu Tang
通讯作者：
Jinyu Wang;Minquan Cheng;Qifa Yan;Xiaohu Tang
影响因子：
10.6
作者：
Guo Y;Gao Y;Shen D
通讯作者：
Shen D
影响因子：
2.7
作者：
A. Thesen
通讯作者：
A. Thesen