حل حداکثر مشکل ذخیره سازی رشته ای با برنامه ریزی خطی

We show that both CMIS and CNIS are NP-complete. We also study the approximation algorithms for the restricted version of CMIS, which is called k  -CMIS (k⩾2k⩾2). Using Linear Programming method, we propose an approximation algorithm for 2-CMIS with approximation ratio 2 and an approximation algorithm for k  -CMIS (k⩾3k⩾3) with approximation ratio k2k2. Based on approximation algorithms for k-CMIS, we get approximation algorithms for k-MPSM with the same approximation ratio.