Optimal kidney exchange
உகந்த சிறுநீரக பரிமாற்றம் (OKE) என்பது சிறுநீரக ஜோடி நன்கொடைகளுக்கான திட்டங்களால் எதிர்கொள்ளப்படும் ஒரு உகப்பாக்கம் சிக்கலாகும் (இது சிறுநீரக பரிமாற்ற திட்டங்கள் என்றும் அழைக்கப்படுகிறது). இத்தகைய திட்டங்கள் நோயாளி-நன்கொடையாளர் ஜோடிகளின் பெரிய தரவுத்தளங்களைக் கொண்டுள்ளன, அங்கு நன்கொடையாளர் நோயாளிக்கு உதவுவதற்காக ஒரு சிறுநீரகத்தை தானம் செய்ய தயாராக இருக்கிறார், ஆனால் மருத்துவ பொருந்தாத தன்மை காரணமாக அவ்வாறு செய்ய முடியாது. மையங்கள் அத்தகைய ஜோடிகளுக்கு இடையில் பரிமாற்றங்களை ஏற்பாடு செய்ய முயற்சிக்கின்றன. எடுத்துக்காட்டாக, ஜோடி A இல் நன்கொடையாளர் ஜோடி B இல் நோயாளிக்கு நன்கொடை அளிக்கிறார், ஜோடி B இல் நன்கொடையாளர் ஜோடி C இல் நோயாளிக்கு நன்கொடை அளிக்கிறார், ஜோடி C இல் நன்கொடையாளர் ஜோடி A இல் நோயாளிக்கு நன்கொடை அளிக்கிறார். OKE சிக்கலின் நோக்கம் அத்தகைய பரிமாற்றங்களின் உகந்த ஏற்பாட்டைக் கண்டுபிடிப்பதாகும். "உகந்த" என்பது வழக்கமாக மாற்று அறுவை சிகிச்சைகளின் எண்ணிக்கை முடிந்தவரை அதிகமாக இருப்பதைக் குறிக்கிறது, ஆனால் பிற நோக்கங்களும் இருக்கலாம். இந்த உகப்பாக்கம் சிக்கலில் ஒரு முக்கியமான தடை என்னவென்றால், ஒரு நன்கொடையாளர் தனது நோயாளிக்கு இணக்கமான சிறுநீரகத்தைப் பெற்றால் மட்டுமே ஒரு சிறுநீரகத்தை வழங்குகிறார், இதனால் எந்த ஜோடியும் பங்கேற்பதால் ஒரு சிறுநீரகத்தை இழக்காது. இந்த தேவை சில நேரங்களில் தனிப்பட்ட பகுத்தறிவு என்று அழைக்கப்படுகிறது. OKE சிக்கல் பல வகைகளைக் கொண்டுள்ளது, அவை ஒவ்வொரு பரிமாற்றத்தின் அனுமதிக்கப்பட்ட அளவு, புறநிலை செயல்பாடு மற்றும் பிற காரணிகளில் வேறுபடுகின்றன. வரையறைகள் உள்ளீடு OKE இன் ஒரு எடுத்துக்காட்டு பொதுவாக ஒரு இயக்கப்பட்ட வரைபடமாக விவரிக்கப்படுகிறது. ஒவ்வொரு முனையும் ஒரு நோயாளி-நன்கொடையாளர் ஜோடியைக் குறிக்கிறது. ஜோடி A முதல் ஜோடி B வரை ஒரு திசை வளைவு என்பது ஜோடி A இல் உள்ள நன்கொடையாளர் ஜோடி B இல் உள்ள நோயாளியுடன் மருத்துவ ரீதியாக இணக்கமாக இருப்பதைக் குறிக்கிறது (பொருந்தக்கூடிய தன்மை நன்கொடையாளர் மற்றும் நோயாளியின் இரத்த வகைகளின் அடிப்படையில் தீர்மானிக்கப்படுகிறது, அதே போல் அவர்களின் இரத்தத்தில் உள்ள குறிப்பிட்ட ஆன்டிஜென்கள் போன்ற பிற காரணிகளும்). பொருந்தக்கூடிய வரைபடத்தில் ஒரு இயக்க சுழற்சி ஒரு சாத்தியமான பரிமாற்றத்தைக் குறிக்கிறது. அளவு 2 இன் ஒரு இயக்க சுழற்சி (எ. கா. A-> B-> A) என்பது சாத்தியமான ஜோடி வாரியான பரிமாற்றத்தைக் குறிக்கிறது-ஒரு ஜோடி ஜோடிக்கு இடையிலான பரிமாற்றம். OKE இன் மிகவும் பொதுவான மாறுபாடு இரண்டாவது வகையின் முனைகளையும் கருதுகிறது, அவை தன்னலமற்ற நன்கொடையாளர்களைக் குறிக்கின்றன-ஒரு நோயாளிக்கு ஜோடியாக இல்லாத நன்கொடையாளர்கள் மற்றும் இணக்கமான எந்த நோயாளிக்கும் ஒரு சிறுநீரகத்தை தானம் செய்ய தயாராக உள்ளனர். அல்ட்ரூஸ்டிக் நன்கொடையாளர் முனைகள் வெளிச்செல்லும் வளைவுகளை மட்டுமே கொண்டுள்ளன. பரோபகார நன்கொடையாளர்களுடன், சுழற்சிகளுடன் மட்டுமல்லாமல் சங்கிலிகளுடனும் பரிமாற்றங்களை ஏற்பாடு செய்ய முடியும், இது ஒரு பரோபகார நன்கொடையாளரிடமிருந்து தொடங்குகிறது. வரைபடத்தில் உள்ள வளைவுகள் எடைகளைக் கொண்டிருக்கலாம், எ. கா. சம்பந்தப்பட்ட மாற்று அறுவை சிகிச்சையின் வெற்றிக்கான நிகழ்தகவு. அவர்களுக்கு முன்னுரிமைகளும் இருக்கலாம், எ. கா. மருத்துவ அவசரத்தால் அல்லது நோயாளி மாற்று வரிசையில் காத்திருக்கும் நேரத்திற்குள். வெளியீடு OKE இன் வெளியீடு என்பது ஜோடி வாரியாக-வேறுபட்ட இயக்க சுழற்சிகளின் தொகுப்பாகும் (மேலும் தன்னலமற்ற நன்கொடையாளர்கள் இருந்தால் இயக்கப்படும் சங்கிலிகள் இருக்கலாம்). OKE இன் எளிய நோக்கம் ஒரு சிறுநீரகத்தைப் பெறும் நோயாளிகளின் எண்ணிக்கையை அதிகரிப்பதாகும். பிற பொதுவான நோக்கங்கள்ஃ சிறுநீரக பரிமாற்றங்களின் எடையுள்ள கூட்டுத்தொகையை அதிகரிப்பதுஃ வரைபடத்தில் உள்ள ஒவ்வொரு விளிம்புக்கும் ஒரு எடை உள்ளது, மேலும் பரிமாற்றத்தில் பயன்படுத்தப்படும் அனைத்து விளிம்புகளிலும் உள்ள எடைகளின் கூட்டுத்தொகையை அதிகரிக்கும் ஒரு பரிமாற்றத்தைக் கண்டுபிடிப்பதே குறிக்கோள். மாற்று அறுவை சிகிச்சை செய்பவர்களின் ஆயுட்காலம் அல்லது அவர்களின் தரமான சரிசெய்யப்பட்ட ஆயுட்காலம் ஆகியவற்றை அதிகப்படுத்துதல். கட்டுப்பாடற்ற சுழற்சி நீளம் ஆரம்பத்தில், பரிமாற்ற சுழற்சிகளின் நீளத்திற்கு எந்த வரம்பும் இல்லாமல் சிக்கல் ஆய்வு செய்யப்பட்டது. ரோத், சோன்மெஸ் மற்றும் அன்வர் ஆகியோர் சிறந்த வர்த்தக சுழற்சி பொறிமுறையின் விரிவாக்கத்தின் அடிப்படையில், பரேட்டோ-உகந்த மற்றும் ஊக்க-இணக்கமான வழியில் பரிமாற்ற சுழற்சிகளைக் கண்டுபிடிப்பதற்கான ஒரு பொறிமுறையை முன்வைத்தனர். ஆபிரகாம், ப்ளம் மற்றும் சாண்ட்ஹோம், வரம்பற்ற சுழற்சி நீளத்துடன், அதிகபட்ச-கார்டினாலிட்டி மற்றும் அதிகபட்ச எடை பரிமாற்றத்தை பல்லுறுப்புக்கோவை நேரத்தில் காணலாம் என்பதைக் காட்டுகின்றன. எடுத்துக்காட்டாக, ஒரு மேக்சியம்-கார்டினாலிட்டி பரிமாற்றத்தைக் கண்டறிய, அசல் இயக்கப்பட்ட வரைபடம் G கொடுக்கப்பட்டால், ஒரு திசைதிருப்பப்படாத இருதரப்பு வரைபடத்தை உருவாக்கவும் H (X + Y, E) இதில்ஃ G இல் உள்ள ஒவ்வொரு ஜோடி j க்கும் இரண்டு முனைகள் உள்ளனஃ xj (நன்கொடையாளரைக் குறிக்கும்) மற்றும் yj (நோயாளியைக் குறிக்கும்). அவை எடை 1 இன் விளிம்பால் இணைக்கப்பட்டுள்ளன. G இல் உள்ள ஒவ்வொரு விளிம்புக்கும் i-> j, H இல் ஒரு விளிம்பில் xi-- yj எடையை 1 + 1/n இல் சேர்க்கவும். எச் இல் அதிகபட்ச எடை பொருத்தத்தைக் கண்டறியவும். ஜி இல் உள்ள ஒவ்வொரு அதிகபட்ச-கார்டினாலிட்டி பரிமாற்றமும் எச் இல் அதிகபட்ச எடை பொருத்தத்திற்கு ஒத்திருக்கிறது. எச் இல் உள்ள ஒவ்வொரு அதிகபட்ச எடை பொருத்தமும் சரியானது என்பதை எடைகள் உத்தரவாதம் செய்கின்றன என்பதை நினைவில் கொள்க, இதனால் ஒவ்வொரு நோயாளியும் பொருந்தக்கூடிய நன்கொடையாளருடன் அல்லது அவரது சொந்த நன்கொடையாளருடன் பொருந்துகிறது. எனவே எந்தவொரு நன்கொடையாளரும் தனது நோயாளிக்கு ஒரு சிறுநீரகத்தைப் பெறாவிட்டால் ஒரு சிறுநீரகத்தைக் கொடுக்கவில்லை, இது தனிப்பட்ட பகுத்தறிவின் தேவையை பூர்த்தி செய்கிறது. இந்த வழிமுறையை அதிகபட்ச எடை பரிமாற்றங்களுக்கு விரிவுபடுத்துவதும், தன்னலமற்ற நன்கொடையாளர்களை இணைப்பதும் எளிது. 2004 ஆம் ஆண்டில் நியூ இங்கிலாந்தில் ஒரு சிறுநீரக பரிமாற்றத் திட்டத்தை செயல்படுத்துவதற்கான விவாதங்களில், தளவாட ரீதியாக, ஜோடி வாரியாக பரிமாற்றங்கள் மட்டுமே சாத்தியமாகும் என்பது கண்டறியப்பட்டது. ஏனென்றால், ஒரு பரிமாற்றத்தில் உள்ள அனைத்து நடவடிக்கைகளும் ஒரே நேரத்தில் செய்யப்பட வேண்டும். இந்த தேவை தனிப்பட்ட பகுத்தறிவுத் தடையை உறுதி செய்வதை நோக்கமாகக் கொண்டுள்ளது-ஒரு நன்கொடையாளர் தனது நோயாளிக்கு சிறுநீரகம் கிடைத்த பிறகு தானம் செய்ய மறுக்கும் அபாயத்தைத் தவிர்க்க. k அளவு கொண்ட ஒரு பரிமாற்ற சுழற்சிக்கு ஒரே நேரத்தில் 2k செயல்பாடுகள் தேவைப்படுகின்றன. அந்த நேரத்தில், ஒரே நேரத்தில் 4 க்கும் மேற்பட்ட செயல்பாடுகளை ஏற்பாடு செய்வது நடைமுறையில் இல்லை, எனவே சுழற்சிகளின் அளவு 2 ஆக மட்டுப்படுத்தப்பட்டது. இந்த அமைப்பில், வழிநடத்தப்பட்ட பொருந்தக்கூடிய வரைபடத்தை ஒரு திசைதிருப்பப்படாத வரைபடத்திற்கு குறைக்க முடியும், அங்கு ஏ-> பி மற்றும் பி-> ஏ இருந்தால் மட்டுமே ஏ மற்றும் பி ஜோடிகள் இணைக்கப்பட்டுள்ளன. அதிகபட்ச-கார்டினாலிட்டி ஜோடி வாரியான பரிமாற்றத்தைக் கண்டுபிடிப்பது அந்த திசைதிருப்பப்படாத வரைபடத்தில் அதிகபட்ச கார்டினாலிட்டி பொருத்தத்தைக் கண்டுபிடிப்பதற்கு சமம். மேலும், ஜோடி வாரியாக பரிமாற்றங்கள் மட்டுமே அனுமதிக்கப்படும்போது, அதிகபட்ச கார்டினாலிட்டி இருந்தால் மட்டுமே ஒரு பொருத்தம் பரேட்டோ-திறமையானதாக இருக்கும். எனவே, அத்தகைய பரிமாற்றத்தை பல்லுறுப்புக்கோவை நேரத்தில் காணலாம். ரோத், சோன்மெஸ் மற்றும் அன்வர் எளிய அதிகபட்ச-கார்டினாலிட்டி பரிமாற்றத்தின் இரண்டு நீட்டிப்புகளை ஆய்வு செய்கிறார்கள்ஃ நோயாளிகள் அல்லது மாற்று அறுவை சிகிச்சைகளை விட முன்னுரிமை தரவரிசை கொடுக்கப்பட்டால், பல்லுறுப்புக்கோவை நேரத்தில் முன்னுரிமை பொருத்தத்தைக் கண்டறிய முடியும்-இது அனைத்து அதிகபட்ச-கார்டினாலிட்டி பொருத்துதல்களிலும், அதிக முன்னுரிமை நோயாளிகளின் எண்ணிக்கையை அதிகரிக்கிறது. மேலும், ஒவ்வொரு நோயாளியும் முடிந்தவரை பல நன்கொடையாளர்களை அமைப்புக்குள் கொண்டு வருவதன் மூலமும், முடிந்தவரை பல சிறுநீரகங்களை ஏற்றுக்கொள்வதற்கு ஒப்புக்கொள்வதன் மூலமும் பொருந்தும் வாய்ப்பை அதிகரிக்கிறது என்ற அர்த்தத்தில் இந்த வழிமுறைகளை ஊக்க-இணக்கமாக்க முடியும். சான்றுகள் கல்லாய்-எட்மண்ட்ஸ் சிதைவு போன்ற வரைபடக் கோட்பாட்டிலிருந்து கருத்துகளைப் பயன்படுத்துகின்றன. ஒரு சீரற்ற பரிமாற்றத்தைக் கண்டுபிடிக்க முடியும், அங்கு அனைத்து அதிகபட்ச-கார்டினாலிட்டி பொருத்தங்களிலிருந்தும் சீரற்ற முறையில் ஒரு பொருத்தம் தேர்ந்தெடுக்கப்படுகிறது. சமத்துவ பொறிமுறை ஒரு நோயாளிக்கு சிறுநீரகம் கிடைப்பதற்கான மிகச்சிறிய நிகழ்தகவை அதிகரிப்பதை நோக்கமாகக் கொண்டுள்ளது. சமத்துவ பொறிமுறை முன்னுரிமை பொறிமுறையைப் போலவே ஊக்குவிப்பு-இணக்கமானது. k நீள சுழற்சிகள் பிற்காலங்களில், தளவாட மேம்பாடுகள் அதிக எண்ணிக்கையிலான ஒரே நேரத்தில் செயல்பாடுகளை செயல்படுத்த அனுமதித்தன. அதன்படி, மூன்று அல்லது அதற்கு மேற்பட்ட ஜோடிகளை உள்ளடக்கிய பரிமாற்ற சுழற்சிகள் சாத்தியமாக்கப்பட்டன. அதிகபட்ச-கார்டினாலிட்டி பரிமாற்றத்தைக் கண்டுபிடிப்பது, வரைபடக் கோட்பாட்டு சொற்களில், அதிகபட்ச சுழற்சி பொதி என்று அழைக்கப்படுகிறது. அதிகபட்சமாக k நீள சுழற்சிகளைக் கொண்ட அதிகபட்ச சுழற்சி பொதி, எந்த நிலையான k ± 3 க்கும், ஒரு NP-கடினமான கணக்கீட்டு சிக்கலாகும் (இது ஒரு ஹைபர் கிராஃப்பில் 3 பரிமாண பொருத்தத்தின் சிக்கலில் இருந்து குறைப்பதன் மூலம் நிரூபிக்கப்படலாம்). ஆபிரகாம், ப்ளம் மற்றும் சாண்ட்ஹோம் அதிகபட்ச சுழற்சி பொதிக்கான இரண்டு நுட்பங்களை வழங்குகிறார்கள்ஃ நெடுவரிசை உருவாக்கம் மற்றும் கட்டுப்பாடு உருவாக்கம். நெடுவரிசை உருவாக்கம் மிகவும் சிறப்பாக அளவிடப்படுகிறது என்று அவர்கள் தெரிவிக்கின்றனர். அவர்களின் வழிமுறை ஜோடி சிறுநீரக நன்கொடைகளுக்கான கூட்டணியில் செயல்படுத்தப்பட்டுள்ளது. விளிம்புகள் எடைகளைக் கொண்டிருந்தாலும் கூட இந்த சிக்கலைத் தீர்ப்பதற்கான இரண்டு அணுகுமுறைகளை பைரோ, மேன்லோவ் மற்றும் ரிசி பரிந்துரைக்கின்றனர் (இந்த விஷயத்தில் இது அதிகபட்ச எடை சுழற்சி பொதி என்று அழைக்கப்படுகிறது): அதிகபட்ச எடை சுயாதீன தொகுப்புக்கான அறியப்பட்ட தோராய வழிமுறைகளின் அடிப்படையில் ஒரு தோராயமான வழிமுறை; ஒரு சரியான வழிமுறை, சுழற்சிகளின் ஹைப்பர் கிராஃப்பை ஒரு வரைபடமாக மாற்றுவதற்கான அனைத்து வழிகளையும் முறையாகச் சரிபார்க்கிறது. வழிமுறை காலப்போக்கில் இயங்குகிறது, அங்கு s என்பது ஒவ்வொரு 3-சுழற்சியிலிருந்தும் ஒரு வளைவைக் கொண்ட ஒரு தொகுப்பின் அளவு. k நீளத்தின் சுழற்சிகள் மற்றும் வரம்பற்ற நீளத்தின் சங்கிலிகள் அல்ட்ருயிஸ்டிக் நன்கொடையாளர்கள் பரிமாற்றங்களின் சங்கிலியைத் தொடங்க பயன்படுத்தப்படலாம், அது ஒரு சுழற்சி அல்ல. அத்தகைய சங்கிலியில், அறுவை சிகிச்சைகள் ஒரே நேரத்தில் செய்யப்பட வேண்டியதில்லைஃ ஒவ்வொரு நோயாளிக்கும் அவரது நன்கொடையாளர் ஒரு சிறுநீரகத்தை வழங்குவதற்கு முன்பு அவர் ஒரு சிறுநீரகத்தைப் பெறுகிறார் என்று உத்தரவாதம் அளிக்க முடியும். ஒரு நன்கொடையாளர் குறைபாடுகள் இருந்தால், அது சங்கிலியை உடைக்கிறது, ஆனால் அது ஏற்கனவே ஒரு சிறுநீரகத்தை வழங்கிய நோயாளிகளுக்கு தீங்கு விளைவிக்காது, எனவே அது தனிப்பட்ட பகுத்தறிவை உடைக்காது. ஆண்டர்சன், அஷ்லாகி, கமர்னிக் மற்றும் ரோத் ஆகியோர் அதிகபட்ச-கார்டினாலிட்டி பேக்கிங்கை அதிகபட்ச கே நீள சுழற்சிகள் மற்றும் வரம்பற்ற நீள சங்கிலிகளில் கண்டுபிடிப்பதற்கான இரண்டு வழிமுறைகளை வழங்குகிறார்கள்ஃ ஒன்று முழு எண் நேரியல் நிரலாக்கம் மற்றும் கட்டுப்பாடு உற்பத்தியை அடிப்படையாகக் கொண்டது; மற்றொன்று பயண விற்பனையாளர் சிக்கலுக்கான தீர்வை அடிப்படையாகக் கொண்டது. நிச்சயமற்ற மாற்று அறுவை சிகிச்சைகள் OKE இல் ஆரம்ப கோட்பாட்டு படைப்புகள், பரிமாற்றங்களின் தொகுப்பு தீர்மானிக்கப்பட்டவுடன், அவை அனைத்தும் செயல்படுத்தப்படும் என்று கருதின. இருப்பினும், நடைமுறையில், மாற்று அறுவை சிகிச்சைகள் ரத்து செய்யப்படலாம். எடுத்துக்காட்டாக, மாற்று அறுவை சிகிச்சைக்கு சற்று முன்பு செய்யப்பட்ட மருத்துவ பரிசோதனையில், தரவுத்தளத்தில் அவை இணக்கமாக பதிவு செய்யப்பட்டிருந்தாலும், நன்கொடையாளர் நோயாளியுடன் பொருந்தவில்லை என்பதை வெளிப்படுத்தலாம். எனவே, புதிய பணிகள் எதிர்பார்க்கப்படும் மாற்று அறுவை சிகிச்சைகளின் எண்ணிக்கையை அதிகரிப்பதை நோக்கமாகக் கொண்டுள்ளன. எடுத்துக்காட்டாக, ஆல்வெலோஸ், க்ளிமென்டோவா மற்றும் வியானா ஆகியோர் இந்த சிக்கலுக்கான கிளை மற்றும் விலை வழிமுறையை வழங்குகிறார்கள். மேலும் குறிப்புகள் சிறுநீரக பரிமாற்றத்திற்கான முழு எண்-நிரலாக்க மாதிரிகள். குறிப்புகள் உகப்பாக்கம் வழிமுறைகள் மற்றும் முறைகள் உறுப்பு நன்கொடை