อัลกอริทึม Gale-Shapley

อัลกอริทึม Gale-Shapley ใช้แก้ปัญหาการจับคู่ที่เสถียร (stable marriage problem): วิธีการจับคู่ระหว่างสองกลุ่ม (เช่น แพทย์ประจำบ้านกับโรงพยาบาล, นักเรียนกับโรงเรียน) โดยที่ไม่มีคู่ใดคู่หนึ่งชอบกันและกันมากกว่าคู่ที่ตนเองได้รับมอบหมาย อัลกอริทึมนี้ถูกนำเสนอโดย David Gale และ Lloyd Shapley ในปี 1962 โดยรับประกันการจับคู่ที่เสถียรในเวลาพหุนาม (polynomial time) ผ่านกระบวนการยอมรับแบบเลื่อนเวลา (deferred acceptance) ซึ่งฝ่ายหนึ่งเสนอตัวตามลำดับ และอีกฝ่ายหนึ่งตอบสนอง โดยปรับปรุงการเลือกเมื่อมีตัวเลือกที่ดีกว่าเข้ามา