在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2019, Vol. 36 ›› Issue (5): 578-594.doi: 10.3969/j.issn.1005-3085.2019.05.008

• • 上一篇    下一篇

技能集扩张问题的组合最优化方法（英）

林  浩1,  林  澜2   

  1. 1- 河南工业大学理学院，郑州  450001
    2- 同济大学电子与信息工程学院，上海  200092
  • 收稿日期:2017-06-26 接受日期:2019-06-10 出版日期:2019-10-15 发布日期:2019-12-15
  • 通讯作者: 林 浩 E-mail address: linhao@haut.edu.cn
  • 基金资助:
    国家自然科学基金 (61373106; 11571323).

A Combinatorial Optimization Approach for the Competence Set Expansion Problem

LIN Hao1,  LIN Lan2   

  1. 1- School of Science, Henan University of Technology, Zhengzhou 450001
    2- School of Electronics and Information Engineering, Tongji University, Shanghai 200092
  • Received:2017-06-26 Accepted:2019-06-10 Online:2019-10-15 Published:2019-12-15
  • Contact: H. Lin. E-mail address: linhao@haut.edu.cn
  • Supported by:
    The National Natural Science Foundation of China (61373106; 11571323).

PDF (PC)

406

摘要： 最优技能集扩张问题是从一个已有技能集扩张为一个要求技能集，使得扩张过程的获取费用为最小．目前文献中已有基于整数规划的数值方法．本文建立有向网络的连接模型，并提出组合最优化的研究途径．主要结果是证明如下结论：1) 问题是强 NP-困难的；2)  当中间顶点数是常数时，问题可在多项式时间求解；3) 问题存在性能比为2的近似算法．此外，本文还提供精确算法（分枝定界算法）及启发式算法．

关键词: 技能集, NP-完全, 多项式时间算法, 精确算法, 近似算法

Abstract: The optimal competence set expansion problem is to minimize the total acquiring cost in an expansion process from a set of existing skills to a set of required skills. A numerical approach based on integer programming has been developed in the literature. In this paper we establish a directed network connection model and propose a combinatorial optimization approach for the problem. The main results have been proved: 1)  the problem is strongly NP-hard;  2)  the problem can be solved in polynomial time if the number of intermediate vertices is a constant;  3)  the problem admits an  approximation algorithm of performance ratio 2. Moreover, an exact algorithm (branch-and-bound algorithm) and heuristic algorithms are provided.

Key words: competence set, NP-completeness, polynomial-time algorithm, exact algorithm; approximation algorithm

中图分类号: