الگوریتم تقریبی تطابق وزن‌دار در گراف کلی با زمان اجرای تقریبا خطی
امروز با دکتر Seth Pettie از طریق وب‌گاهشان آشنا شدم. خیلی جالب است، بسیاری از موضوعاتی که به دنبالش بودم را اینجا پیدا کردم. مثلا مقاله‌ای در مورد یافتن سریع تطابق تقریبی در گراف کلی وزن‌دار. جالب بود که ایشان روی این موضوع کار کرده‌اند و نتیجه کارشان هم جالب است. کلی هم مقاله دیگر دارند در مورد الگوریتم‌های ابتدایی، مانند پیدا کردن درخت فراگیر کمینه. کلا کارهایشان خیلی جالب است. حیف بود معرفی‌شان نکنم.
مقاله‌ای که از طریق این مقاله وب‌گاهشان را پیدا کردم:
Linear Time Approximation for Maximum Weight Matching
Ran Duan and Seth Pettie
J. ACM 61(1), Article 1, 2014. PDF, BibTex
راستش مقاله‌اش را نخواندم. اما یعنی تطابق را در گراف کلی وزن‌دار سریع‌تر از زمان اجرای لازم برای تطابق بدون وزن در گراف دوبخشی پیدا می‌کند. خیلی جالب است!
ظاهرا ایده کلی به این صورت است که یک وزن‌هایی روی راس‌ها می‌گذارد (مانند الگوریتم معمولی تطابق). بعد در هر مرحله ابتدا وزن‌های برخی راس‌ها را نصف می‌کند. یال‌هایی که وزنشان تقریبا با جمع وزن دوسرشان برابر بود را اجازه می‌دهد در این مرحله از الگوریتم شرکت کنند. یک سری مسیر افزایش راس مجزای ماکسیمال پیدا می‌کند و آن‌ها را اعمال می‌کند. البته این که گفتم الگوریتم برای حالتی است که گراف دور فرد نداشته باشد. ظاهرا همین است. ولی جزئیاتش را هنوز با دقت نخوانده‌ام.
نمی‌دانم پیاده‌سازی درست و حسابی از الگوریتمشان موجود هست یا خیر.
جالب بود؟
نوشته‌های دیگری که شاید برای شما جالب باشند: