Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming

• 成果类型: Article
• 署名作者: Wu, Chenchen; Wang, Yishui; Lu, Zaixin; Pardalos, Panos M.; Xu, Dachuan; Zhang, Zhao; Du, Ding-Zhu
• 署名单位: Tianjin University of Technology; Beijing University of Technology; Washington State University; State University System of Florida; University of Florida; Beijing University of Technology; Zhejiang Normal University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1242-z
• 发表日期: 2018
• 页码: 255-275
• 关键词: approximation algorithms; optimization problems

摘要

In this paper, we consider the maximum and minimum versions of degree-concentrated fault-tolerant spanning subgraph problem which has many applications in network communications. We prove that both this two problems are NP-hard. For the maximum version, we use DC programming relaxation to propose a heuristic algorithm. Numerical tests indicate that the proposed algorithm is efficient and effective. For the minimum version, we also formulate it as a DC program, and show that the DC algorithm does not perform well for this problem.