Revisiting k-sum optimization

• 成果类型: Article
• 署名作者: Puerto, J.; Rodriguez-Chia, A. M.; Tamir, A.
• 署名单位: University of Sevilla; Universidad de Cadiz; Tel Aviv University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1096-1
• 发表日期: 2017
• 页码: 579-604
• 关键词: lexicographic bottleneck problems; ordered median problems; tree-shaped facilities; location-problems; discrete optimization; knapsack-problem; algorithms; networks; graph; centers

摘要

In this paper, we address continuous, integer and combinatorial k-sum optimization problems. We analyze different formulations of this problem that allow to solve it through the minimization of a relatively small number of minisum optimization problems. This approach provides a general tool for solving a variety of k-sum optimization problems and at the same time, improves the complexity bounds of many ad-hoc algorithms previously reported in the literature for particular versions of this problem. Moreover, the results developed for k-sum optimization have been extended to the more general case of the convex ordered median problem, improving upon existing solution approaches.