Atama problemi aslında bir doğrusal programlama modelidir, ama özel
yapısı sayesinde simpleks gerekmez. Dayandığı gözlem şu: bir satırın
(ya da sütunun) bütün hücrelerinden aynı sayıyı çıkarmak optimal atamayı
değiştirmez — her atama o satırdan tam bir hücre kullanır, yani bütün
atamaların toplamı aynı miktarda azalır.
Algoritma bu serbestliği kullanarak matrisi, sıfırlardan tam bir
atama kurulabilene kadar dönüştürür.
1 · Satır indirgeme
Her satırdan kendi en küçük değeri çıkarılır. Her satırda en az bir sıfır
oluşur.
2 · Sütun indirgeme
Her sütundan kendi en küçük değeri çıkarılır. Artık her satırda ve her
sütunda en az bir sıfır var.
3 · Örtme
Bütün sıfırları örten en az sayıda yatay/dikey çizgi bulunur.
Çizgi sayısı n ise birbirini engellemeyen n tane sıfır vardır ve atama
kurulur — algoritma biter.
4 · İyileştirme
Çizgi sayısı n'den küçükse: örtülmemiş en küçük değer k bulunur.
Örtülmemiş bütün hücrelerden k çıkarılır, iki çizginin kesiştiği
hücrelere k eklenir, tek çizgiyle örtülenler değişmez. Bu işlem en az bir
yeni sıfır üretir ve 3. adıma dönülür.
"En az çizgi" gözle mi bulunuyor?
Hayır — gözle çizgi çekmek bir algoritma değildir ve yanlış çekilebilir.
Bu uygulama König teoremini kullanır: en az örtü = en büyük
eşleşme. Sıfırların oluşturduğu iki parçalı çizgede artırıcı yol
yöntemiyle en büyük eşleşme bulunur, sonra klasik işaretleme kurallarıyla
örtü türetilir:
- Ataması olmayan satırlar işaretlenir.
- İşaretli satırlarda sıfırı olan sütunlar işaretlenir.
- İşaretli sütunlarda ataması olan satırlar işaretlenir. Değişim bitene
kadar tekrarlanır.
- Çizgiler: işaretlenmeyen satırlar + işaretlenen sütunlar.
Böylece çizgi sayısı her zaman en büyük eşleşmeye eşittir ve
"çizgiyi yanlış çektim" durumu oluşamaz.
Tam kesir
Bütün işlemler çıkarma ve toplamadır; hiçbir yerde bölme ya da karekök
yoktur. Sayfa baştan sona tam kesirlidir.