یک فرم آزاد شدهُ جدید مبتنی بر شبکه برای مسالهُ پوشش مجموعه و استراتژی های قوی تخصیص هزینه

درسه دههُ اخیر استفاده از فرمهای آزاد شدهrelaxations)) برای حل مسالهُ پوشش مجموعه(SCP) مورد توجه محققین قرار گرفته است. با توجه به NP-Complete بودن مسالهُ SCP ، فرمهای آزاد شدهُ آن از اهمیت خاصی برخوردارند. فرمهای آزاد شده مبتنی بر شبکه به واسطهُ داشتن سرعت زیاد جذابیت زیادی دارند. در این مقاله یک فرم آزاد شده جدید برای SCP ارائه می دهیم که کرانهای پایین به مراتب بهتری نسبت به فرمهای آزاد شده دیگر مبتنی بر شبکه بدست می دهد. همچنین استراتژیهایی قوی برای تخصیص هزینه در فرم آزاد شده مبتنی بر مسالهُ کارگماری ( ASP2 ) از مسالهُ SCP ، ارائه شده و نتایج محاسباتی امیدوار کننده ایی حاصل شده است

کلیدواژه ها:

فرم آزاد شده ، پوشش مجموعه ، مسائل شبکه ، کارگماری ، استراتژی