Kararlı eşleşmelerden oluşan kafes - Lattice of stable matchings

İçinde matematik, ekonomi, ve bilgisayar Bilimi, istikrarlı eşleşmelerden oluşan kafes bir dağıtıcı kafes kimin elemanları kararlı eşleşmeler. Kararlı eşleme probleminin belirli bir örneği için, bu kafes bir cebirsel soruna yönelik tüm çözümlerin ailesinin tanımı. Başlangıçta 1970'lerde John Horton Conway ve Donald Knuth.^[1][2]

Tarafından Birkhoff'un temsil teoremi, bu kafes şu şekilde temsil edilebilir: alt setler temelde kısmen sıralı küme ve bu setin elemanlarına rotasyon olarak somut bir yapı verilebilir, döngü grafikleri Kafes içindeki bitişik kararlı eşleşmeler arasındaki değişiklikleri açıklar. Tüm rotasyonların ailesi ve bunların kısmi düzenleri, polinom zamanı minimum veya maksimum ağırlıkta kararlı eşleştirme dahil olmak üzere kararlı eşleşmedeki diğer problemler için polinom zamana yol açar. Gale – Shapley algoritması iki özel kafes elemanı, üst ve alt elemanı oluşturmak için kullanılabilir.

Her sonlu dağılımlı kafes, kararlı eşleşmelerden oluşan bir kafes olarak temsil edilebilir. Kafes içindeki elemanların sayısı, ortalama bir durumdan değişebilir. ${ displaystyle e ^ {- 1} n ln n}$ üssel olarak en kötü duruma getirilir. # P-tamamlandı.

Arka fon

En basit haliyle, kararlı eşleştirme probleminin bir örneği, birbiriyle eşleştirilecek aynı sayıda öğenin iki setinden oluşur, örneğin doktorlar ve hastanelerdeki pozisyonlar. Her unsurun diğer türün unsurlarına göre sıralaması vardır: doktorların her birinin hangi hastanede çalışmak istedikleri için farklı tercihleri ​​vardır (örneğin, hangi şehirlerde yaşamayı tercih ettiklerine bağlı olarak) ve hastanelerin her birinin tercihleri ​​vardır. Hangi doktorlar için çalışmak istedikleri (örneğin uzmanlık veya tavsiyelere göre). Amaç, bir eşleşme bulmaktır. kararlı: hiçbir çift doktor ve hastane birbirini belirlenen eşleşmeye tercih etmez. Bu sorunun versiyonları, örneğin, Ulusal Yerleşik Eşleştirme Programı Amerikan tıp öğrencilerini hastanelerle eşleştirmek için.^[3]

Genel olarak, birçok farklı sabit eşleşme olabilir. Örneğin, aşağıdaki tercihlere sahip üç doktor (A, B, C) ve üç hastane (X, Y, Z) olduğunu varsayalım:

A: YXZ B: ZYX C: XZY

X: BAC Y: CBA Z: ACB

Bu eşleştirme düzenlemesinin üç kararlı çözümü vardır:

1. Doktorlar ilk tercihlerini alırlar ve hastaneler üçüncülerini alırlar: AY, BZ, CX.
2. Tüm katılımcılar ikinci tercihlerini alırlar: AX, BY, CZ.
3. Hastaneler ilk tercihlerini, doktorlar üçüncü tercihlerini alıyor: AZ, BX, CY.

Kararlı eşleşmelerden oluşan kafes, herhangi bir kararlı eşleme örneği için bu çözüm koleksiyonunu organize ederek ona bir dağıtıcı kafes.^[1]

Yapısı

Eşleşmelerde kısmi sıralama

Kararlı eşleşmelerin kafesi, aşağıdaki daha zayıf yapıya dayanmaktadır: kısmen sıralı küme kimin unsurları istikrarlı eşleşmelerdir. Bir karşılaştırma işlemi tanımlayın ${ displaystyle leq}$ istikrarlı eşleşmelerde ${ displaystyle P leq Q}$ eğer ve sadece tüm doktorlar eşleşmeyi tercih ederse ${ displaystyle Q}$ eşleştirmek için ${ displaystyle P}$: ya her iki eşleşmede de aynı hastaneye sahipler ya da daha iyi bir hastaneye atanmışlar. ${ displaystyle Q}$ içinde olduklarından ${ displaystyle P}$. Doktorlar hangi eşleşmeyi tercih ettikleri konusunda hemfikir değilse, o zaman ${ displaystyle P}$ ve ${ displaystyle Q}$ karşılaştırılamaz: hiçbiri ${ displaystyle leq}$ diğeri. Aynı karşılaştırma operasyonu, sadece doktorlar ve hastaneler için değil, herhangi iki unsur grubu için aynı şekilde tanımlanabilir. İki grup unsurdan hangisinin doktorların rolünde kullanılacağının seçimi keyfidir. Doktorların ve hastanelerin rollerinin değiştirilmesi, her bir çift öğenin sırasını tersine çevirir, ancak kısmi düzenin yapısını başka türlü değiştirmez.^[1]

Daha sonra bu sıralama, eşleşmelere kısmen sıralı bir setin yapısını verir. Bunu yapmak için, aşağıdaki üç özelliğe uyması gerekir:

• Her eşleşme için ${ displaystyle P}$, ${ displaystyle P leq P}$
• Her iki farklı eşleşme için ${ displaystyle P}$ ve ${ displaystyle Q}$, her ikisi de olamaz ${ displaystyle P leq Q}$ ve ${ displaystyle Q leq P}$ Doğrudur.
• Her üç farklı eşleşme için ${ displaystyle P}$, ${ displaystyle Q}$, ve ${ displaystyle R}$, Eğer ${ displaystyle P leq Q}$ ve ${ displaystyle Q leq R}$, sonra ${ displaystyle P leq R}$.

Kararlı eşleşmeler için, üç özellik de doğrudan karşılaştırma işleminin tanımını takip eder.

Üst ve alt elemanlar

Bir elemanın en iyi eşleşmesini tanımlayın ${ displaystyle x}$ sabit eşleme örneğinin öğesi ${ displaystyle y}$ o ${ displaystyle x}$ en çok, eşleştirilebilecek tüm öğeler arasında tercih eder ${ displaystyle x}$ ve en kötü eşleşmeyi benzer şekilde tanımlayın. Öyleyse iki unsur aynı en iyi eşleşmeye sahip olamaz. ${ displaystyle x}$ ve ${ displaystyle x '}$ her ikisi de ${ displaystyle y}$ en iyi eşleşmeleri ve bu ${ displaystyle y}$ tercih eder ${ displaystyle x}$ -e ${ displaystyle x '}$. Ardından, eşleşen kararlı eşlemede ${ displaystyle x '}$ -e ${ displaystyle y}$ (en iyi eşleşme tanımına göre mevcut olmalıdır ${ displaystyle x '}$), ${ displaystyle x}$ ve ${ displaystyle y}$ kararsız bir çift olurdu çünkü ${ displaystyle y}$ tercih eder ${ displaystyle x}$ -e ${ displaystyle x '}$ ve ${ displaystyle x}$ tercih eder ${ displaystyle y}$ herhangi bir istikrarlı eşleştirmede başka bir ortağa. Bu çelişki, tüm doktorları en iyi eşleşmelerine atamanın bir eşleşme sağladığını göstermektedir. Kararlı bir eşleştirmedir çünkü kararsız herhangi bir çift, en iyi eşleşmeleri tanımlamak için kullanılan eşleştirmelerden biri için de kararsız olacaktır. Tüm doktorları en iyi maçlara atamanın yanı sıra, tüm hastaneleri en kötü maçlarına atar. Eşleşmelerdeki kısmi sıralamada, diğer tüm sabit eşleşmelerden daha büyüktür.^[1]

Simetrik olarak, tüm doktorları en kötü eşleşmelerine atamak ve tüm hastaneleri en iyi eşleşmelerine atamak, başka bir istikrarlı eşleşme sağlar. Eşleşmelerdeki kısmi sıralamada, diğer tüm sabit eşleşmelerden daha azdır.^[1]

Gale – Shapley algoritması Sabit eşleşmelerin oluşturulması için aşağıdaki gibi tanımlanabilecek bir süreç verir: Bir eşleşmeye ulaşılıncaya kadar, algoritma, pozisyonu doldurulmamış keyfi bir hastaneyi seçer ve bu hastane, sahip olduklarından en çok tercih ettiği doktora bir iş teklifinde bulunur. zaten teklifler yapılmadı. Doktor işsizse veya daha az tercih edilen bir görevi varsa, doktor teklifi kabul eder (ve varsa diğer görevinden istifa eder). Süreç her zaman sona erer, çünkü her doktor ve hastane yalnızca bir kez etkileşime girer. Sonlandırıldığında, sonuç, her hastaneyi en iyi eşleşmeye atayan ve tüm doktorları en kötü eşleşmelerine atayan istikrarlı bir eşleşmedir. Doktorların ve hastanelerin rollerini değiştiren bir algoritma (işsiz doktorların hastaneler arasından bir sonraki tercihlerine iş başvurusu göndermeleri ve hastanelerin ya boş pozisyonları olduğunda başvuruları kabul etmeleri ya da yeni başvuranı tercih etmeleri, doktoru işten çıkarmaları) daha önce kabul etmişti) bunun yerine, tüm doktorları en iyi eşleşmelerine ve her hastaneyi en kötü eşleşmeye atayan istikrarlı eşleşmeyi üretir.^[1]

Kafes operasyonları

Herhangi iki sabit eşleşme verildiğinde ${ displaystyle P}$ ve ${ displaystyle Q}$ aynı girdi için iki tane daha eşleştirme oluşturulabilir ${ displaystyle P vee Q}$ ve ${ displaystyle P kama Q}$ Aşağıdaki şekilde:

İçinde ${ displaystyle P vee Q}$her doktor, eşleştikleri iki hastane arasından en iyi seçimini yapar. ${ displaystyle P}$ ve ${ displaystyle Q}$ (eğer bunlar farklıysa) ve her hastane en kötü seçimini alır.

İçinde ${ displaystyle P kama Q}$Her doktor, eşleştiği iki hastane arasından en kötü seçimini yapar ${ displaystyle P}$ ve ${ displaystyle Q}$ (eğer bunlar farklıysa) ve her hastane en iyi seçimini alır.

(Aynı operasyonlar, sadece doktorlar ve hastaneler için değil, herhangi iki unsur grubu için aynı şekilde tanımlanabilir.)^[1]

Sonra ikisi de ${ displaystyle P vee Q}$ ve ${ displaystyle P kama Q}$ Örneğin, iki doktorun aynı en iyi seçeneğe sahip olması ve aynı hastaneyle eşleştirilmesi mümkün değildir. ${ displaystyle P vee Q}$Hastane tarafından iki doktordan hangisini tercih ederse etsin, o doktor ve hastane hangisinde ise kararsız bir çift oluşturacaktır. ${ displaystyle P}$ ve ${ displaystyle Q}$ zaten uyumlu değiller. Çünkü doktorlar ${ displaystyle P vee Q}$hastaneler de eşleştirilmelidir. Aynı mantık simetrik olarak geçerlidir ${ displaystyle P kama Q}$.^[1]

Ek olarak, her ikisi de ${ displaystyle P vee Q}$ ve ${ displaystyle P kama Q}$ Birbirlerini eşleşmelerine tercih eden bir çift doktor ve hastane olamaz, çünkü aynı çift zorunlu olarak en az biri için dengesiz bir çift olacaktır. ${ displaystyle P}$ ve ${ displaystyle Q}$.^[1]

Kafes özellikleri

İki operasyon ${ displaystyle P vee Q}$ ve ${ displaystyle P kama Q}$ Biçimlendirmek katıl ve tanış sonlu operasyonlar dağıtıcı kafes Bu bağlamda, sonlu kafes kısmen sıralı olarak tanımlanır Sınırlı set benzersiz bir minimum öğe ve benzersiz bir maksimum öğe olduğu, her iki öğenin her ikisine de eşit veya daha büyük (birleşimleri) benzersiz bir en küçük öğeye sahip olduğu ve her iki öğenin, şundan küçük veya eşit benzersiz bir en büyük öğeye sahip olduğu ikisi de (buluşmaları).^[1]

Operasyonlar durumunda ${ displaystyle P vee Q}$ ve ${ displaystyle P kama Q}$ yukarıda tanımlanan birleştirme ${ displaystyle P vee Q}$ her ikisinden de büyük veya eşittir ${ displaystyle P}$ ve ${ displaystyle Q}$ çünkü her bir doktora kendi tercihlerini vermek için tanımlanmıştı ve çünkü doktorların bu tercihleri, eşleşmelerdeki sıralamaların nasıl tanımlandığıdır. Her ikisinin de üstünde olan diğer tüm eşleşmelerin altında ${ displaystyle P}$ ve ${ displaystyle Q}$çünkü böyle bir eşleştirme, her bir doktora en az onun kadar iyi olan bir eşleşme vermelidir. Bu nedenle, bir kafesin birleştirme işlemi için gereksinimlere uyar. ${ displaystyle P kama Q}$ karşılama operasyonu gereksinimlerine uyar.^[1]

Tercih sıralamasında eleman bazlı minimum veya element bazlı maksimum kullanılarak tanımlandıkları için, bu iki işlem aynı dağıtım yasaları doğrusal sıralamalarda minimum ve maksimum işlemlere uyulur: her üç farklı eşleşme için ${ displaystyle P}$, ${ displaystyle Q}$, ve ${ displaystyle R}$,

${ Displaystyle P kama (Q vee R) = (P kama Q) vee (P kama R)}$

ve

${ Displaystyle P vee (Q kama R) = (P vee Q) kama (P vee R)}$

Bu nedenle, kararlı eşleşmelerin kafesi bir dağıtıcı kafes.^[1]

Rotasyonlarla temsil

Birkhoff'un temsil teoremi herhangi bir sonlu dağılımlı kafesin bir aile ile temsil edilebileceğini belirtir. sonlu kümeler, birleştirme ve birleştirme işlemleri olarak kesişme ve birleşim ve ilişkili kısmi sipariş için karşılaştırma işlemi olarak bir alt küme olma ilişkisi ile. Daha spesifik olarak, bu setler, alt setler Birkhoff teoreminin genel formunda, bu kısmi düzen, kafesin elemanlarının bir alt kümesi üzerinde indüklenen sıra olarak alınabilir, birleşim indirgenemez elemanlar (iki diğerinin birleşimi olarak oluşturulamayan elemanlar) elementler).^[4] Kararlı eşleşmelerin kafesi için, kısmi düzenin elemanları bunun yerine adı verilen yapılar açısından tanımlanabilir. rotasyonlar, Tarafından tanımlanan Irving ve Deri (1986).^[5]

İki farklı kararlı eşleştirmenin ${ displaystyle P}$ ve ${ displaystyle Q}$ karşılaştırılabilir ve kısmi sırada aralarında üçüncü sabit eşleşme yoktur. (Yani, ${ displaystyle P}$ ve ${ displaystyle Q}$ bir çift oluşturmak kapsayan ilişki Kararlı eşleşmelerin kısmi sırasına göre.) Daha sonra, birinde eşleşen ancak her ikisinde birden eşleşmeyen öğe çiftleri kümesi. ${ displaystyle P}$ ve ${ displaystyle Q}$ ( simetrik fark eşleşmiş çift kümelerinden) dönme olarak adlandırılır. Oluşturur döngü grafiği kenarları iki eşleşme arasında değişiyor. Benzer şekilde, dönüş, iki eşleşmeden düşük olanı daha yüksek olana değiştirmek için yapılması gereken değişiklikler kümesi olarak tanımlanabilir (daha düşük ve daha yüksek, kısmi sıra kullanılarak belirlenir). İki farklı sabit eşleme ayrı ayrı aynı dönüş için daha yüksek eşleşme ise, o zaman bunların buluşması da öyledir. Bunu, herhangi bir rotasyon için, rotasyonla bağlanan bir çiftin en yükseği olabilen sabit eşlemeler kümesinin benzersiz bir en düşük öğeye sahip olduğu sonucu çıkar. Bu en düşük eşleşme indirgenemez bir birleşimdir ve bu, dönüşler ile indirgenemez birleştirme kararlı eşleşmeleri arasında bire bir yazışma sağlar.^[5]

Rotasyonlara, karşılık gelen birleşik indirgenemez kararlı eşleşmeleriyle aynı kısmi sıralama verilirse, Birkhoff'un temsil teoremi, düşük rotasyon setleri ve tüm kararlı eşleşmeler arasında bire bir karşılık verir. Verilen herhangi bir kararlı eşleşmeyle ilişkili dönüşler kümesi, verilen eşleşmeyi kısmi sıralamada aşağı doğru dönüşlerle değiştirerek, her adımda hangi dönüşün en alttaki öğeye ulaşana kadar keyfi olarak gerçekleştirileceğini seçerek ve bu sırada kullanılan dönüşleri listeleyerek elde edilebilir. değişiklikler. Herhangi bir düşük rotasyon setiyle ilişkili stabil eşleştirme, rotasyonları stabil eşleşmelerden oluşan kafesin alt elemanına uygulayarak, birden fazla uygulanabildiğinde hangi rotasyonun uygulanacağını keyfi olarak seçerek elde edilebilir.^[5]

Her çift ${ displaystyle (x, y)}$ Belirli bir sabit eşleme örneğinin öğelerinin sayısı en fazla iki dönüşe aittir: iki eşleşmenin alt kısmına uygulandığında diğer atamaları kaldıran bir dönüş ${ displaystyle x}$ ve ${ displaystyle y}$ ve bunun yerine bunları birbirlerine atar ve iki eşleşmenin alt kısmına uygulandığında çifti kaldıran ikinci bir dönüş ${ displaystyle (x, y)}$ eşleştirmeden ve bu iki öğe için diğer atamaları bulur. Çünkü var ${ displaystyle n ^ {2}}$ eleman çiftleri var ${ displaystyle O (n ^ {2})}$ rotasyonlar.^[5]

Matematiksel özellikler

Evrensellik

Sonlu bir dağıtıcı kafes olmanın ötesinde, kararlı eşleşmelerin kafes yapısı üzerinde başka hiçbir kısıtlama yoktur. Bunun nedeni, her sonlu dağılım kafesi için ${ displaystyle L}$, kararlı eşleşmelerin kafesi ile izomorfik olan kararlı bir eşleme örneği vardır. ${ displaystyle L}$.^[6]Daha güçlü olarak, eğer sonlu bir dağıtım kafesi varsa ${ displaystyle k}$ öğeler, daha sonra en fazla olan kararlı bir eşleme örneği kullanılarak gerçekleştirilebilir. ${ displaystyle k ^ {2} -k + 4}$ doktorlar ve hastaneler.^[7]

Kafes elemanlarının sayısı

Kararlı eşleşmelerin kafesi, hesaplama karmaşıklığı belirli bir örneğin kararlı eşleşmelerinin sayılması. Kararlı eşleşmelerin kafesleri ile keyfi sonlu dağıtıcı kafesler arasındaki eşdeğerliğinden, bu problemin keyfi bir sonlu dağılım kafesindeki elemanların sayısını saymaya veya Antikalar keyfi kısmen sıralı bir kümede. Kararlı eşleştirme sayısının hesaplanması # P-tamamlandı.^[5]

İstikrarlı evlilik probleminin tekdüze rastgele bir örneğinde ${ displaystyle n}$ doktorlar ve ${ displaystyle n}$ Hastaneler, ortalama istikrarlı eşleştirme sayısı asimptotiktir ${ displaystyle e ^ {- 1} n ln n}$.^[8] Farklı sabit eşleşmelerin sayısını en üst düzeye çıkarmak için seçilen istikrarlı bir evlilik örneğinde, bu sayı en az olabilir ${ displaystyle 2 ^ {n-1}}$,^[5]ve biz de üst sınırlı tarafından üstel fonksiyon nın-nin n (saf olandan önemli ölçüde daha küçük faktöryel eşleşme sayısına bağlıdır).^[9]

Algoritmik sonuçlar

Dönme ailesi ve bunların kısmi sıralaması, polinom zamanı belirli bir kararlı eşleştirme örneğinden ve tüm kararlı eşleşmelerin ailesine kısa bir sunum sağlar; bu, bazı örnekler için açıkça listelendiğinde katlanarak daha büyük olabilir. Bu, kararlı eşleştirme örneklerinde birkaç başka hesaplamanın verimli bir şekilde gerçekleştirilmesine izin verir.^[10]

Ağırlıklı sabit eşleştirme ve kapanma

Kararlı bir eşleme örneğindeki her bir eleman çiftine gerçek değerli bir ağırlık atanırsa, minimum veya maksimum ağırlık kararlı eşleşmesini bulmak mümkündür. polinom zamanı. Bunun için olası bir yöntem uygulamaktır doğrusal programlama için politop sipariş etmek kısmi dönme sırasına veya kararlı eşleşen politop.^[11] Aynı kısmi sıraya göre alternatif, kombinatoryal bir algoritma mümkündür.^[12]

Eleman çiftleri üzerindeki ağırlıklardan, her bir dönüşe ağırlıklar atanabilir; burada belirli bir sabit eşleşmeyi, sabit eşleşmelerin kısmi sıralamasında daha yüksek bir dönüşle değiştiren bir dönüş, neden olduğu ağırlık değişikliğine atanır: toplam ağırlık daha yüksek eşleşme eksi düşük eşlemenin toplam ağırlığı. Kararlı eşleşmeler ve daha düşük dönme setleri arasındaki uygunluk sayesinde, herhangi bir eşleşmenin toplam ağırlığı, karşılık gelen alt kümesinin toplam ağırlığı artı eşleştirme kafesinin alt elemanının ağırlığına eşittir. Minimum veya maksimum ağırlık sabit eşleşmesini bulma sorunu, bu şekilde, kısmen sıralı bir polinom boyutu kümesinde, kısmen sıralı dönüşler kümesinde minimum veya maksimum ağırlık alt kümesini bulma sorununa eşdeğer hale gelir.^[12]

Bu optimal düşük küme problemi, kapanma sorunu, köşe ağırlıklı bir sorun yönlendirilmiş grafikler burada amaç, dışarıya çıkan kenarları olmayan optimum ağırlıkta bir köşe alt kümesi bulmaktır. Optimal alt set, bir Yönlendirilmiş döngüsüz grafiği köşeleri olarak kısmi düzenin öğelerine sahip olan ${ displaystyle alpha}$ -e ${ displaystyle beta}$ her ne zaman ${ displaystyle alpha leq beta}$ kısmi sırayla. Kapanma problemi de polinom zamanda onu bir örneğe dönüştürerek çözülebilir. maksimum akış sorunu.^[12]

Minimum pişmanlık

Gusfield (1987) Kararlı bir eşleşmede bir katılımcının pişmanlığını, atadığı maçın tercih listesinin en üstünden uzaklığı olarak tanımlar. Sabit bir eşleşmenin pişmanlığını, herhangi bir katılımcının maksimum pişmanlığı olarak tanımlar. Daha sonra, eşleştirme kafesinin alt öğesinde başlayan ve daha sonra bir katılımcının pişmanlığını azaltan herhangi bir dönüşü tekrar tekrar uygulayan basit bir açgözlü algoritma ile minimum pişmanlık kararlı eşleşmeyi bulabilir, ta ki bu, başka bir katılımcının neden olacağı kadar daha büyük pişmanlık duymak.^[10]

Medyan sabit eşleme

Herhangi bir dağıtım kafesinin elemanları bir medyan grafik herhangi üç unsurun bulunduğu bir yapı ${ displaystyle P}$, ${ displaystyle Q}$, ve ${ displaystyle R}$ (burada, sabit eşleşmeler) benzersiz bir medyan öğeye sahiptir ${ displaystyle m (P, Q, R)}$ bu, ikisi arasındaki en kısa yolda yatıyor. Şu şekilde tanımlanabilir:^[13]

${ Displaystyle m (P, Q, R) = (P kama Q) vee (P kama R) vee (Q kama R) = (P vee Q) kama (P vee R) kama (Q vee R).}$

Kararlı eşleşmelerden oluşan kafes için, bu medyan, her bir doktora, o doktorla eşleşen üç hastanenin doktor tercihlerinde ortanca atanarak element bazında alınabilir. ${ displaystyle P}$, ${ displaystyle Q}$, ve ${ displaystyle R}$ ve benzer şekilde, her hastaneye eşleşen üç doktorun medyanını atayarak. Daha genel olarak, herhangi bir dağıtıcı kafesin (veya medyan grafiğin) tek sayıdaki elemanlarından oluşan herhangi bir set, bir medyana, verilen sete olan uzaklıklarının toplamını en aza indiren benzersiz bir elemana sahiptir.^[14] Tek sayıdaki sabit eşleşmelerin medyanı için, her katılımcı, verilen eşleşmelerden kendi maçlarının çoklu setinin medyan unsuruyla eşleştirilir. Düzgün bir sabit eşleme dizisi için, bu, her bir doktoru iki medyan unsurdan daha yüksek olana ve her hastaneyi iki medyan unsurdan daha düşük olana eşleştiren görev seçilerek netleştirilebilir. Özellikle, bu, tüm kararlı eşleşmelerin setinde medyan eşleşmesi için bir tanıma götürür.^[15] Ancak, kararlı eşleştirme sorununun bazı örnekleri için, tüm kararlı eşleşmelerin bu medyanını bulmak NP-zor.^[16]

Referanslar