مسألهی مکانیابی -p ماکسین شرطی روی شبکه

در این مقاله، مسألهی -pماکسین شرطی را روی شبکه ها بررسی میکنیم. فرض کنید یک شبکه مانندG = (V,E)داده شده باشد؛ که هر رأسViآن دارای وزن مثبتWiاست. در مسأله ی-p ماکسین هدف پیدا کردن یک مجموعه شاملp رأس شبکه بعنوان سرویس دهنده است بگونهای که مجموع ماکسیمم فاصلهی وزندار سایر نقاط تا این مجموعه، بیشترین مقدار شود. در مسألهی -p ماکسین شرطی فرض بر این است که تعدادی سرویس دهنده از قبل موجود است و بایدp تای دیگر به آنها اضافه شود. در این مقاله، دو الگوریتم جدید برای حل مسألهی-p ماکسین شرطی ارائه میشود و نتایج آنها (از جمله زمان حل دو روش در پیدا کردن نقاط بهینه) با هم مقایسه میگردد. از جمله کاربردهای این مقاله، میتواند در کمینه کردن زمان برای تعیین مکان بهینهی ضایعات زباله باشد. ضایعات زباله باید دورترین فاصله را نسبت بهنقاط تقاضا (مناطق خانه نشین) داشته باشند و در عین حال در مکانی باشند که بتوانند به تقاضاها خدمت - رسانی کنند

کلیدواژه ها:

ماکسین-p ، شرطی ، مکانیابی ، شبکه