مهدی جهانگیری

یافتن راه حلی برای مسائل بهینه سازی ترکیبی به دلیل کاربرد آن ها در مدل سازی مساله های جهان واقعی همیشه حائز اهمیت بوده است. اما اکثر آنها ‎$‎‎\mathrm{NP}‎‎‎$‎‎‏-کامل و غیرقابل حل در زمان چند جمله ای هستند. بنابراین الگوریتم های تقریبی برای آنها طراحی شده است. مساله مجموعه احاطه گر تام یکی از این مساله ها است. در این مقاله، یک مدل بهینه سازی عدد صحیح درجه دوم جدید را برای این مساله ارائه و یک روش تقریبی برای یافتن یک کران پایین برای عدد احاطه گر تام طراحی می کنیم.