تکرار محدود برش کوتاه برای پارتیشن بندی هایپرگراف K-way

عنوان تکرار محدود برش کوتاه برای پارتیشن بندی هایپرگراف K-way
نویسنده یازیجی، ولکان، آیکانات، سی.
تاریخ انتشار: 2014
محل انتشار - اطلاع می دهد
موضوع بهینه سازی ترکیبی، نمودارها، اکتشافی، بهینه سازی، برنامه نویسی، عدد صحیح
نوع دوره ای
زبان انگلیسی
دیجیتال بله
نسخه خطی خیر
کتابخانه: دانشگاه اوزیغین
شناسه دارایی کتابخانه 1526-5528
شماره ثبت c1a12b34-0a70-4ccd-986e-07966fdaf729
محل کتابخانه علوم کامپیوتر
تاریخ 2014
یادداشت‌ها با توجه به محدودیت های کپی رایت، دسترسی به متن کامل این مقاله تنها از طریق اشتراک امکان پذیر است.
متن نمونه Replication یک تکنیک پرکاربرد در سیستم های بازیابی اطلاعات و پایگاه داده برای ارائه تحمل خطا و کاهش هزینه های موازی سازی و پردازش است. مدل‌های ترکیبی مبتنی بر پارتیشن‌بندی هایپرگراف برای مشکلات مختلف ناشی از سیستم‌های بازیابی اطلاعات و پایگاه داده پیشنهاد شده‌اند. ما امکان استفاده از تکرار راس را برای بهبود کیفیت پارتیشن بندی هایپرگراف در نظر می گیریم. در این مطالعه، ما بر روی مشکل تکرار برش محدود (CMCR) تمرکز می‌کنیم، جایی که در ابتدا حداکثر ظرفیت تکرار و یک پارتیشن هایپرگراف K-way با نسبت عدم تعادل اولیه به ما داده می‌شود. هدف در مسئله CMCR یافتن مجموعه‌های تکرار رئوس بهینه برای هر بخش از پارتیشن داده شده است به طوری که اندازه برش اولیه پارتیشن به حداقل برسد، جایی که عدم تعادل اولیه تحت محدودیت ظرفیت تکرار داده شده حفظ یا کاهش می‌یابد. در این مطالعه، ما یک تحلیل پیچیدگی از مشکل CMCR ارائه می‌کنیم و مدلی را بر اساس ترکیبی منحصر به فرد از طرح‌های برنامه‌ریزی خطی درشت و صحیح (ILP) پیشنهاد می‌کنیم. این الگوریتم درشت سازی از یک استفاده جدید از تجزیه Dulmage-Mendelsohn مشتق شده است. آزمایش‌ها نشان می‌دهند که فرمول ILP همراه با درشت‌کردن مبتنی بر تجزیه Dulmage-Mendelsohn نتایج با کیفیت بالایی را در زمان‌های اجرایی عملی برای کاهش اندازه برش یک پارتیشن ابرگراف K-way ارائه می‌کند.
DOI 10.1287/ijoc.2013.0567
Cilt 26
مشاهده در منبع دانشگاه اوزیغین دانشگاه اوزیغین - موتور جستجوی آثار تاریخی، آرشیوها و نشریات
دانشگاه اوزیغین - موتور جستجوی آثار تاریخی، آرشیوها و نشریات دانشگاه اوزیغین

تکرار محدود برش کوتاه برای پارتیشن بندی هایپرگراف K-way

نویسنده یازیجی، ولکان، آیکانات، سی.
تاریخ انتشار 2014
محل انتشار - اطلاع می دهد
موضوع بهینه سازی ترکیبی، نمودارها، اکتشافی، بهینه سازی، برنامه نویسی، عدد صحیح
نوع دوره ای
زبان انگلیسی
دیجیتال بله
نسخه خطی خیر
کتابخانه دانشگاه اوزیغین
شناسه دارایی کتابخانه 1526-5528
شماره ثبت c1a12b34-0a70-4ccd-986e-07966fdaf729
محل کتابخانه علوم کامپیوتر
تاریخ 2014
یادداشت‌ها با توجه به محدودیت های کپی رایت، دسترسی به متن کامل این مقاله تنها از طریق اشتراک امکان پذیر است.
متن نمونه Replication یک تکنیک پرکاربرد در سیستم های بازیابی اطلاعات و پایگاه داده برای ارائه تحمل خطا و کاهش هزینه های موازی سازی و پردازش است. مدل‌های ترکیبی مبتنی بر پارتیشن‌بندی هایپرگراف برای مشکلات مختلف ناشی از سیستم‌های بازیابی اطلاعات و پایگاه داده پیشنهاد شده‌اند. ما امکان استفاده از تکرار راس را برای بهبود کیفیت پارتیشن بندی هایپرگراف در نظر می گیریم. در این مطالعه، ما بر روی مشکل تکرار برش محدود (CMCR) تمرکز می‌کنیم، جایی که در ابتدا حداکثر ظرفیت تکرار و یک پارتیشن هایپرگراف K-way با نسبت عدم تعادل اولیه به ما داده می‌شود. هدف در مسئله CMCR یافتن مجموعه‌های تکرار رئوس بهینه برای هر بخش از پارتیشن داده شده است به طوری که اندازه برش اولیه پارتیشن به حداقل برسد، جایی که عدم تعادل اولیه تحت محدودیت ظرفیت تکرار داده شده حفظ یا کاهش می‌یابد. در این مطالعه، ما یک تحلیل پیچیدگی از مشکل CMCR ارائه می‌کنیم و مدلی را بر اساس ترکیبی منحصر به فرد از طرح‌های برنامه‌ریزی خطی درشت و صحیح (ILP) پیشنهاد می‌کنیم. این الگوریتم درشت سازی از یک استفاده جدید از تجزیه Dulmage-Mendelsohn مشتق شده است. آزمایش‌ها نشان می‌دهند که فرمول ILP همراه با درشت‌کردن مبتنی بر تجزیه Dulmage-Mendelsohn نتایج با کیفیت بالایی را در زمان‌های اجرایی عملی برای کاهش اندازه برش یک پارتیشن ابرگراف K-way ارائه می‌کند.
DOI 10.1287/ijoc.2013.0567
Cilt 26
دانشگاه اوزیغین - موتور جستجوی آثار تاریخی، آرشیوها و نشریات
دانشگاه اوزیغین شما در حال هدایت مجدد هستید...

لطفاً صبر کنید