مقاله محاسبه گسترش لبه یک گراف با استفاده از SDP

چکیده

Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two versions of an exact algorithm using semidefinite programming (SDP) to compute this constant for any graph. The SDP relaxation is used to first reduce the search space considerably. One version applies then an SDP-based branch-and-bound algorithm, along with heuristic search. The other version transforms the problem into an instance of a max-cut problem and solves this using a state-of-the-art solver. Numerical results demonstrate that we clearly outperform mixed-integer quadratic solvers as well as another SDP-based algorithm from the literature.

چکیده به فارسی (ترجمه ماشینی)

محاسبه گسترش لبه نمودار یک مشکل مشهور ترکیبی است که برای آن مطالعات تقریبی زیادی انجام شده است.ما دو نسخه از یک الگوریتم دقیق را با استفاده از برنامه نویسی SemideFinite (SDP) ارائه می دهیم تا این ثابت را برای هر نمودار محاسبه کنیم.از آرامش SDP استفاده می شود تا ابتدا فضای جستجو را به میزان قابل توجهی کاهش دهد.یک نسخه سپس یک الگوریتم شاخه و مرز مبتنی بر SDP ، به همراه جستجوی اکتشافی اعمال می شود.نسخه دیگر مشکل را به نمونه ای از یک مشکل حداکثر تبدیل می کند و با استفاده از یک حل کننده پیشرفته ، این مسئله را حل می کند.نتایج عددی نشان می دهد که ما به وضوح از حلال های درجه دوم مخلوط و همچنین الگوریتم مبتنی بر SDP از ادبیات بهتر عمل می کنیم.