الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.
قیمت
قیمت این مقاله: 38000 تومان
(ایران ترجمه - Irantarjomeh)
توضیح
بخش زیادی از این مقاله بصورت رایگان ذیلا قابل مطالعه می باشد.
دپارتمان علوم کامپیوتر، دانشگاه استنفورد کالیفرنیا، ایالات متحده
مرجع به انگلیسی
Department of Computer Science, Stanford University CA
کشور
ایالات متحده
جایابی امکانات / تسهیلات آنلاین
چکیده
ما گوناگونی های مختلف آنلاین در مبحث جایابی/ موقعیت امکانات/ تسهیلات آنلاین را مد نظر قرار می دهیم، که در آن نقاط تقاضا هر یک در برهه زمانی خاصی پدیدار می شوند و بر این مبنا ما باید مجموعه ای از امکانات جهت سرویس رسانی بدین نقاط را تامین نماییم. ما یک الگوریتم رقابتی- O(1) آنلاین تصادفی را عرضه می نماییم که در آن نقاط در یک مرتبه تصادفی وارد می شوند. در صورتی که نقاط به صورت مجادله آمیزی مرتب شوند، ما نشان خواهیم داد که هیچ گونه الگوریتمی نمی تواند به صورت یک مضمون ثابت- رقابتی مد نظر باشد و بر این مبنا یک الگوریتم O (log n)- رقابتی را عرضه می داریم. الگوریتم های ما با توجه به وابستگی شدید آنها به مفهوم زمان انتظار مورد انتظار به صورت تصادفی ارائه شده و مورد تجزیه و تحلیل قرار می گیرند. ما همچنین تکنیک های خود را با تکنیک های Charikar و Guha ترکیب می نماییم تا آنکه یک تقریب ثابت خطی- زمانی را برای مشکل موقعیت امکانات آفلاین فراهم نماییم.
۱- مقدمه
بسیاری از برنامه های کاربردی در ارتباط با مشکل جایابی امکانات اقدام به ایجاد سناریوها یا راهکارهای طبیعی آنلاین می نمایند. به طور مثال در نظر بگیرید از ما خواسته شده باشد تا نسبت به ایجاد یک شبکه اقدام نماییم. بر این مبنا ما نیازخواهیم داشت تا سرورهای مختلفی را خریداری نموده و هر یک از کلاینت ها را به یکی از این سرورها متصل سازیم. هزینه اتصال یک کلاینت به یک سرور (با توجه به خرید کابل) به صورت خطی با توجه به فاصله بین آنها مشخص خواهد شد. به هنگامی که این شبکه استقرار یافت، ممکن است خواسته باشیم کلاینت های بیشتری را اضافه نماییم. در این حالت، ما باید کابل های بیشتر و احتمالا سرورهای جدیدی را خریداری کنیم تا آنکه قابلیت بهره گیری از آنها بر حسب تقاضا را داشته باشیم. به علاوه ما متمایلیم تا نسبت به کاهش و به حداقل رسانی مجموع هزینه ها اقدام نمائیم.
به عنوان یک نمونه دیگر، مشکل خوشه بندی وب را در نظر بگیرید. با توجه به ویژگی های مختلف، ما قابلیت نگاشت صفحه های وبی در یک فضای محتوایی را خواهیم داشت و بر این مبنا ما متمایل می باشیم تا این صفحات را به تعدادی از خوشه ها تقسیم نماییم. صفحات هر خوشه می بایست در فضای محتوا به طور نسبی نزدیک باشند. از طرف دیگر، ما متمایل به ساخت خوشه های بسیاری نیستیم (به طور مثال، یک خوشه برای هر نقطه، قابل پذیرش نمی باشد). این وب به سرعت رشد نموده و صفحات وبی جدید نیز نیازمند اضافه شدن به چنین خوشه هایی می باشند. ما به هنگام فرارسیدن صفحه های وبی جدید متمایل به حفظ یک سیستم خوشه بندی مناسب بدون پاره شدن خوشه های موجود می باشیم.
…
جایابی امکانات / تسهیلات آنلاین
۲- هزینه های یکنواخت امکانات
ما متمایل به انتخاب و باز نمودن یک مجموعه از امکانات F هستیم تا آنکه بتوانیم سرویسی را در یک مجموعه از تقاضاها u مهیا سازیم. هدف ما به حداقل رسانی مجموع هزینه میباشد. اولین بخش این هزینه به عنوان هزینه امکانات مشخص میشود، در حالیکه دومین بخش هزینه سرویس خواهد بود.
مشکل ما مسئله آنلاین می باشد، که بر اساس آن مجموعه ای از تقاضاهای U قبلا به طورکامل شناخته شده نیستند. در نظر بگیرید که یک رقیب/ مدعی اقدام به ایجاد مجموعه ای از تقاضاها نماید. نقاط تقاضا سپس با توجه به جایگشتی تصادفی (کلیه جایگشت ها به صورت متساوی) مرتب شده و هر یک از آنها در یک برهه زمانی، بنوبت، حاصل میشوند.
به هنگامی که هر نقطه حاصل می گردد، ما می بایست یا اقدام به باز نمودن یک امکان در آن نقطه نماییم (باتوجه به پرداخت هزینه امکانات f) یا آنکه این تقاضا را به برخی دیگر از امکاناتی که قبلا باز شده اند ارسال نماییم (پرداخت هزینه سیر). الگوریتم ما می بایست این انتخاب را بدون داشتن دانش مرتبط با این تقاضاها ( یا تعداد تقاضاها)، که در آینده فرا می رسند، انجام دهد. ما ملاحظه مینماییم که چنین موردی متفاوت از یک مدل متعارف آنلاین و بدینسان می باشد که سفارشی که بر مبنای آن نقاط تقاضا حاصل میشوند به صورت تصادفی بوده و به وسیله یک رقیب یا فرد مدعی انتخاب نشده است. در بخش ۴، ما سناریویی را مد نظر قرار می دهیم که درآن سفارش حالت مجادله ای خواهد داشت.
جایابی امکانات / تسهیلات آنلاین
۳- هزینه های غیر یکنواخت امکانات
ما موردی را در نظر می گیریم که در آن هزینه امکانات منوط به موقعیت آن امکانات خواهد بود. ما بیش از این نمی توانیم خود را محدود به باز نمودن امکانات در نقاط تقاضایی نماییم که قبلا رسیده شده اند. در نظر بگیرید که اکثریت نقاط دارای هزینه امکانات نامحدودی می باشند، همراه با احتمال ثابت یکی از این نقاط در ابتدا رسیده و (از آنجایی که ما می بایست اقدام به گشودن یک امکان در نقطه اول نماییم) بنابر این ما نمی توانیم حالت رقابتی خود، در برابر بهینه سازی آفلاین که اقدام به باز نمودن یک امکان در موقعیت هزینه – محدود/ متناهی می نماید، را اعمال نماییم. به واسطه این امر، ما در نظر می گیریم که دارای فضای متریک کاملی در خلال هزینه های امکانات بر روی گره ها از نقطه شروع هستیم، اما تقاضاها برای سرویس به صورت افزایشی (به صورت یک نظم تصادفی ) در حال رسیدن می باشند.
الگوریتم جدید به شرح ذیل خواهد بود. ما در ابتدا هزینه های امکان را بگونه ای مقیاس بندی می کنیم که آنها به ضریب دو افزایش یابند . ما به سادگی هر یک از این هزینه های امکان به نزدیکترین ضریب دو گرد کرده و از اینجا کار خود را ادامه می دهیم. چنین امری سبب افزایش هزینه امکانات پرداختی به وسیله الگوریتم ما خواهد شد، چرا که هزینه های حقیقی امکانات ممکن است بیش از دو برابر هزینه های فرضی باشند. در نظر بگیرید که پس از این مقیاس بندی، هزینه های امکانات مختلف در یک مرتبه افزایشی با توجه به از f1 الی fn باشند. به هنگامی که نقطه تقاضا حاصل می گردد، ما احتمالا باز نمودن یک امکان جدید برای هر یک از مقادیر هزینه مختلف را مد نظر قرار خواهیم داد.
جایابی امکانات / تسهیلات آنلاین
۴- جایابی امکانات مجادله برانگیز آنلاین
ما هم اکنون مشکلی را مد نظر قرار می دهیم که در آن انتخاب هر دو مجموعه نقاط و نظمی که بر مبنای آن این نقاط می رسند محقق می گردد. ما درابتدا اثبات خواهیم نمود که هیچ یک از الگوریتم های آنلاین نمیتواند برای این مشکل به صورت O(1)-رقابتی باشند. از طرف دیگر، الگوریتمی که ما دربخش های قبلی تشریح نمودیم احتمالا دربردارنده پارامتر O(lon n)–رقابتی خواهد بود.
قضیه ۱-۴٫ هیچ یک از الگوریتم ها نمی توانند برای این مشکل،جایی که نقاط در یک نظم مجادله انگیز وارد می شوند، بصورت O(1)- رقابتی باشند.
جایابی امکانات / تسهیلات آنلاین
۵- جایابی امکانات آفلاین در زمان خطی
کاربرد الگوریتم آنلاین در زمینه مشکل آفلاین جایابی امکانات را در نظر بگیرید. ما میتوانیم این نقاط را در یک نظم تصادفی در زمان جابجا نماییم. به هنگامی که هر نقطه حاصل میشود، ما می بایست فاصله آن، به نزدیکترین امکانی که درحال حاضر باز می باشد (و برای هر امکان بالقوه در مورد غیر یکنواخت)، را محاسبه نموده و اقدام به اتخاذ یک تصمیم تصادفی نماییم. این فرایند در زمان در بدترین حالت (برای مجموعه یکنواخت، چنین موردی به طور حقیقی O(k) خواهد بود، که در آن k تعداد امکانات باز به وسیله این الگوریتم می باشد. با این وجود، این الگوریتم ممکن است قابلیت باز کردن امکانات بسیار بیشتری از راه حل بهینه را داشته باشد). مجموع زمان اجرایی بر این مبنا مقید به می باشد و ما یک تقریب ثابت را حاصل آورده ایم. ما مشخص میسازیم که در حالی که بسیاری از الگوریتم های تقریب- ثابت برای مشکل جایابی امکانات شناخته شده هستند (که غالبا ثابت های کوچکتری را حاصل میکنند)، آنها نیازمند بیش از زمان جهت اجرا خواهند بود. در حقیقت به عنوان زمان خطی میباشد که علت آن نیز را باید در این مبحث جستجو نمود که ورودی، یک ماتریس فاصله های کلیه جفت ها و نقاط، از نظر اندازه می باشد.
ما الگوریتم جستجوی محلی Charikar و Guha [2] را مد نظر قرار میدهیم، که فراهم آورنده یک تقریب در زمان می باشد. این مورد در تحلیل [۲] به صورت تلویحی بیان می شود که اولین زمان صرف شده و سبب حصول یک تقریب – ثابت می شود، درحالی که بعدی صرف ارتقای این ثابت در محدوده مشخص شده خواهد شد. بر این مبنا، ما قابلیت اتخاذ خروجی الگوریتم آنلاین سریع خود را داشته و جستجوی محلی را بر این نتیجه اعمال داریم. این دیدگاه سبب حذف عامل از زمان اجرایی میشود و سبب ارائه یک تقریب در زمان خواهد شد.
لطفا به جای کپی مقالات با خرید آنها به قیمتی بسیار متناسب مشخص شده ما را در ارانه هر چه بیشتر مقالات و مضامین ترجمه شده علمی و بهبود محتویات سایت ایران ترجمه یاری دهید.
