الگوریتم تقریبی تطابق وزن‌دار در گراف کلی با زمان اجرای تقریبا خطی

امروز با دکتر Seth Pettie از طریق وب‌گاهشان آشنا شدم. خیلی جالب است، بسیاری از موضوعاتی که به دنبالش بودم را اینجا پیدا کردم. مثلا مقاله‌ای در مورد یافتن سریع تطابق تقریبی در گراف کلی وزن‌دار. جالب بود که ایشان روی این موضوع کار کرده‌اند و نتیجه کارشان هم جالب است. کلی هم مقاله دیگر دارند در مورد الگوریتم‌های ابتدایی، مانند پیدا کردن درخت فراگیر کمینه. کلا کارهایشان خیلی جالب است. حیف بود معرفی‌شان نکنم.

مقاله‌ای که از طریق این مقاله وب‌گاهشان را پیدا کردم:

Linear Time Approximation for Maximum Weight Matching
Ran Duan and Seth Pettie
J. ACM 61(1), Article 1, 2014.
PDFBibTex

راستش مقاله‌اش را نخواندم. اما یعنی تطابق را در گراف کلی وزن‌دار سریع‌تر از زمان اجرای لازم برای تطابق بدون وزن در گراف دوبخشی پیدا می‌کند. خیلی جالب است!

ظاهرا ایده کلی به این صورت است که یک وزن‌هایی روی راس‌ها می‌گذارد (مانند الگوریتم معمولی تطابق). بعد در هر مرحله ابتدا وزن‌های برخی راس‌ها را نصف می‌کند. یال‌هایی که وزنشان تقریبا با جمع وزن دوسرشان برابر بود را اجازه می‌دهد در این مرحله از الگوریتم شرکت کنند. یک سری مسیر افزایش راس مجزای ماکسیمال پیدا می‌کند و آن‌ها را اعمال می‌کند. البته این که گفتم الگوریتم برای حالتی است که گراف دور فرد نداشته باشد. ظاهرا همین است. ولی جزئیاتش را هنوز با دقت نخوانده‌ام.

نمی‌دانم پیاده‌سازی درست و حسابی از الگوریتمشان موجود هست یا خیر.

4 Replies to “الگوریتم تقریبی تطابق وزن‌دار در گراف کلی با زمان اجرای تقریبا خطی”

  1. دکتر sanjeev khanna هم روی بعضی مسائل و ورژن های تطابق کار کردن، اخیرا البته بیشتر روی stochastic matching problem کار کردن. ولی مثلا توی این پیپرشون (https://arxiv.org/abs/0909.3346) تطابق کاملو توی گرافای 2بخشی منظم توی nlogn پیدا میکنن. شاید خوشتون اومد.

    1. خلاصه مقاله که خیلی جالب بود. اما در مساله ما گراف منتظم نبود. راستش نویسنده یک مقاله را پیدا کردم و به ایشان ایمیلی زدم و جواب جالبی داد. ایشان گفت اگرچه از لحاظ نظری الگوریتم ما بهتر است، اما الگوریتم‌هایی که با زمان اجرای نظری بدتری داده‌اند، در آزمایش نتایج بسیار بهتری در زمان بسیار بهتری گرفته‌اند. در نهایت گفت برو از همان‌ها استفاده کن!

  2. سلام استاد؛
    روزتان را خیلی تبریک عرض می‌کنم. حضور اساتیدی مثل شما همیشه برای من و بسیاری از دیگر دانشجویان انگیزه بخش بوده و هست.‌
    از مباحث خوب سایتتان هم استفاده می‌کنم اما فضای راکد کامنت‌ها جسارت نظر دادن را کم می‌کند. خیلی وقتها مطالب سایت شما نقش موضوعی برای فکر کردن و گفتگو با اطرافیان دارد.
    ببخشید که کامنتم غیر مرتبط هست!
    ان شاالله که در پناه حق سلامت باشید.

    1. سلام.

      ممنون از اظهار نظرتان. بله متاسفانه فضا کمی راکد است. چه کنیم دیگر؟! این هم یکی از شرایطی است که باید سعی کنیم تغییر بدهیم. مثل خیلی چیزهای دیگر.

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *