SC13 Home > SC13 Schedule > SC13 Presentation - An Improved Parallel Iterative Algorithm for Stable Matching

SCHEDULE: NOV 16-22, 2013

When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.

An Improved Parallel Iterative Algorithm for Stable Matching

SESSION: Research Poster Reception

EVENT TYPE: Posters, Electronic Posters, and Education Posters

TIME: 5:15PM - 7:00PM

AUTHOR(S):Colin R. White, Enyue Lu

ROOM:Mile High Pre-Function

We propose a parallel algorithm for finding a stable matching that converges in O(n log n) average time using n^2 processors. The algorithm is based on the Parallel Iterative Improvement (PII) algorithm, which finds a stable matching with approximately a 90% success rate. Our algorithm, called the PII-SC algorithm, uses a smart initiation method that decreases the number of iterations to find a stable matching, and also applies a cycle detection method to find a stable matching based on patterns in the preference lists. Both methods decrease the number of times it fails to find a stable matching by three orders of magnitude, and when combined, the chance of failure is less than 10^-7.

Chair/Author Details:

Colin R. White - Amherst College

Enyue Lu - Salisbury University

Add to iCal  Click here to download .ics calendar file

Add to Outlook  Click here to download .vcs calendar file

Add to Google Calendarss  Click here to add event to your Google Calendar