An improved approximation algorithm for the minimum common integer partition problem

被引：0
|
作者：
Lin, Guohui [1 ]
Tong, Weitian [2 ]
机构：
[1] Univ Alberta, Dept Comp Sci, Edmonton, AB T6G 2E8, Canada
[2] Georgia Southern Univ, Dept Comp Sci, Statesboro, GA 30458 USA
来源：
INFORMATION AND COMPUTATION | 2021年 / 281卷
基金：
加拿大自然科学与工程研究理事会;
关键词：
Approximation algorithm; Integer partition; Weighted set packing; Amortized analysis;
D O I：
10.1016/j.ic.2021.104784
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Given a collection of multisets {X-1, X-2, . . . , Xk} (k >= 2) of positive integers, a multiset S is a common integer partition for them if S is an integer partition of every multiset X-i, 1 <= i <= k. The minimum common integer partition (k-MCIP) problem is defined as to find a CIP for {X-1, X-2, . . . , X-k} with the minimum cardinality. We present a 6/5-approximation algorithm for the 2-MCIP problem, improving the previous best algorithm of performance ratio 5/4 designed by Chen et al. in 2006. We then extend it to obtain an absolute 0.6k-approximation algorithm for k-MCIP when k is even (when k is odd, the approximation ratio is 0.6k + 0.4). (C) 2021 Elsevier Inc. All rights reserved.
引用
收藏
页数：13
相关论文
共 50 条
12345