کوتاهترین ابررشته - اصلاحیه

S: مجموعه رشته های ورودی

M: مجموعه شامل همه ی ابررشته های بهینه هر دو رشته (از اعضای S)

Set(x): مجموعه اعضای S که زیررشته ی x هستند. (=x ابررشته ی آنهاست)

هزینه ی Set(x) طول رشته x است یعنی |x|.

OPTs: جواب بهینه ی پوشش مجموعه ای که در آن اعضای مجموعه مرجع رشته ها و مجموعه ها Set(x) ها هستند که x اجتماع M و S است.

OPT: طول کوتاهترین ابررشته شامل همه ی رشته ها (جواب بهینه مساله)

الگوریتم:

1- با استفاده از الگوریتم تقریبی پوشش مجموعه ای یک جواب پیدا کن. (به تعریف OPTs نگاه کنید.)

فرض کنید رشته هایی که این الگوریتم برگرداند a_1,...,a_k باشند.

2- این رشته ها را با هر ترتیبی به هم بچسبانید. (دلخواه)

3- رشته ی حاصل را به عنوان جواب برگردانید.

تحلیل:

(چون هزینه ای که مینیمم می کند، طول رشته ها است احتمالا جواب خوبی به دست می آید.)

لم: OPT <OPTs <2.OPTs

(جواب بهینه ی مساله ی پوشش مجموعه ای جواب تقریبی برای این مساله با ضریب 2 است.)

اثبات نامساوی اول ساده است: طول جواب بهینه کمتر از طول جوابی است که پوشش مجموعه ای بر می گرداند. (در واقع فقط باید ثابت کنیم جواب پوشش مجموعه ای یک جواب برای این مساله است.) می دانیم جوابی که پوشش مجموعه ای بر می گرداند حاصل اتصال رشته های a_i است که برای هر رشته ی S حداقل یک a_i هست که ابررشته ی آن باشد.

اثبات نامساوی دوم: کافی است ثابت کنیم جواب الگوریتم پوششی با هزینه ی کمتر از 2 برابر جواب بهینه است. اولین مکانی که هر رشته ی S در جواب الگوریتم ما ظاهر می شود علامت بزنید. این مکان ها متمایزند چون هیچ رشته ای زیر مجموعه ی رشته ی دیگر نیست. (اگر دو رشته مکان شروع یکسان داشته باشند رشته ای که زودتر تمام می شود زیررشته ی رشته ی دیگر می شود). با استدلال مشابه پایان این رشته ها هم متمایز است. آنها را به این ترتیب شماره گذاری می کنیم. این لیست را روی رشته های a_i افراز می کنیم (جزء مساله). (اشتراک a_i ها کمتر از یک رشته در S است در غیر این صورت بهینه نمی شدند.). هزینه ی جواب الگوریتم ما جمع طول ابررشته های a_i است. بدیهی است که a_i و a_i+2 با هم اشتراک ندارند. پس هر رشته حداکثر در دو تا از ابررشته ها (a_i و a_i+1) آمده است پس هزینه کمتر از دو برابر جمع طول a_i ها است که آن هم از جواب بهینه بیشتر است.