|
عنوان
|
ک روش نقطه درونی نشدنی با گام کامل NT با پیچیدگی (O(n برای حاصل ضرب دکارتی P_*(k) –HLCP روی مخروط های متقارن با استفاده از تحدب نمایی
|
|
نوع پژوهش
|
مقاله چاپ شده
|
|
کلیدواژه‌ها
|
مساله مکملی خطی افقی، حاصل ضرب دکارتی، روش نقطه درونی نشدنی، پیچیدگی چندجمله ای، مخروط متقارن
|
|
چکیده
|
در این مقاله، با استفاده از خاصیت تحدب نمایی یک تابع مانع، یک روش نقطه درونی نشدنی را برای مساله حاصل ضرب دکارتی مکملی خطی افقی روی مخروط های متقارن ارایه میدهیم. در این روش، از گام های کامل نسترو-تاد استفاده کرده و نشان میدهیم که الگوریتم منظور شده خوش تعریف است. کران تکرار الگوریتم با بهترین کران تکرار شناخته شده برای مسایل حاصل ضرب دکارتی مکملی خطی افقی روی مخروطهای متقارن منطبق است. هزینه اجرای یک تکرار عملیات حسابی است.
|
|
پژوهشگران
|
بهروز خیرفام (نفر اول)، معصومه حقیقی (نفر دوم)
|