Connecting a set of circles with minimum sum of radii

ما مسئله اختصاص دادن شعاع به یک مجموعه داده ای از نقاط در هوا را در نظر می گیریم، به طوری که مجموعه نتیجه ای از دیسک ها متصل شده و مجموع شعاع ها به حداقل می رسد. ما ثابت می کنیم که اگر گرافهای بالایی در شعاع ها وجود دارد و مشکل مشابهی در نمودارهای مقیاس چگالی وجود دارد، اثبات مشابهی برای مجموعه های نقطه ای است. برای مواردی که هیچ مرزی بالایی در شعاع وجود ندارد، پیچیدگی باز است؛ ما یک طرح تقریبی چندجملهای را ارائه می دهیم. ما همچنین ضمانت تقریبی ثابت را برای راه حل ها با تعداد محدودی از دیسک ها ارائه می دهیم؛ این نتایج توسط سطوح پایینی پشتیبانی می شوند، که در بعضی از موارد نشان داده شده است که تنگ هستند. در نهایت، ما نشان می دهیم که اگر یک درخت اتصال داده می شود، مشکل حل چند جمله ای است و ما با برخی نتایج آزمایش نتیجه می گیریم.