Welfare maximization
நலன்புரி அதிகபட்சமாக்கல் சிக்கல் என்பது பொருளாதாரம் மற்றும் கணினி அறிவியலில் ஆய்வு செய்யப்பட்ட ஒரு உகப்பாக்கம் சிக்கலாகும். அதன் குறிக்கோள் வெவ்வேறு பயன்பாட்டு செயல்பாடுகளைக் கொண்ட முகவர்களிடையே பொருட்களின் தொகுப்பைப் பிரிப்பதாகும், அதாவது நலன்புரி-முகவர்களின் பயன்பாடுகளின் கூட்டுத்தொகை என வரையறுக்கப்படுகிறது-முடிந்தவரை அதிகமாக உள்ளது. வேறு வார்த்தைகளில் கூறுவதானால், பயன்பாட்டு விதியை திருப்திப்படுத்தும் ஒரு பொருள் ஒதுக்கீட்டைக் கண்டுபிடிப்பதே குறிக்கோள். ஒருங்கிணைந்த ஏலங்களின் சூழலில் ஒரு சமமான சிக்கல் வெற்றியாளர் தீர்மானித்தல் சிக்கல் என்று அழைக்கப்படுகிறது. இந்த சூழலில், ஒவ்வொரு முகவரும் பொருட்களின் தொகுப்புகளில் ஏலங்களின் பட்டியலை சமர்ப்பிக்கிறார்கள், மேலும் எந்த ஏலம் அல்லது ஏலங்கள் வெல்ல வேண்டும் என்பதை தீர்மானிப்பதே குறிக்கோள், அதாவது வென்ற ஏலங்களின் கூட்டுத்தொகை அதிகபட்சமாகும். வரையறைகள் m உருப்படிகளின் தொகுப்பு M மற்றும் n முகவர்களின் தொகுப்பு N உள்ளது. N இல் உள்ள ஒவ்வொரு முகவர் i க்கும் ஒரு பயன்பாட்டு செயல்பாடு உள்ளது. செயல்பாடு உருப்படிகளின் ஒவ்வொரு சாத்தியமான துணைக்குழுவிற்கும் ஒரு உண்மையான மதிப்பை ஒதுக்குகிறது. பயன்பாட்டு செயல்பாடுகள் பொதுவாக மோனோடோன் செட் செயல்பாடுகள் என்று கருதப்படுகிறது, அதாவது, குறிக்கிறது. என்றும் அனுமானிக்கப்படுகிறது. மோனோடோனிசிட்டியுடன் சேர்ந்து, இது அனைத்து பயன்பாடுகளும் எதிர்மறை அல்லாதவை என்பதைக் குறிக்கிறது. ஒரு ஒதுக்கீடு என்பது பொருட்களை n வேறுபட்ட துணைக்குழுக்களாக வரிசைப்படுத்தப்பட்ட பகிர்வு ஆகும், ஒரு முகவருக்கு ஒரு துணைக்குழு, குறிக்கப்படுகிறது, அதாவது. ஒரு ஒதுக்கீட்டின் நலன் என்பது முகவர்களின் பயன்பாடுகளின் கூட்டுத்தொகையாகும்ஃ நலன்புரி அதிகபட்சமாக்கல் சிக்கல்ஃ W (X) ஐ அதிகப்படுத்தும் ஒரு ஒதுக்கீடு X ஐக் கண்டறியவும். அனுமதிக்கப்பட்ட பயன்பாட்டு செயல்பாடுகளின் வகை, வழிமுறை பயன்பாட்டு செயல்பாடுகளை அணுகக்கூடிய வழி மற்றும் அனுமதிக்கப்பட்ட ஒதுக்கீடுகளில் கூடுதல் கட்டுப்பாடுகள் உள்ளதா என்பதைப் பொறுத்து நலன்புரி அதிகபட்சமாக்கல் சிக்கல் பல வகைகளைக் கொண்டுள்ளது. சேர்க்கை முகவர்கள் ஒரு சேர்க்கை முகவர் ஒரு சேர்க்கை தொகுப்பு செயல்பாட்டைக் கொண்ட ஒரு பயன்பாட்டு செயல்பாட்டைக் கொண்டுள்ளதுஃ ஒவ்வொரு சேர்க்கை முகவர் i மற்றும் உருப்படி j க்கு, ஒரு மதிப்பு உள்ளது, அதாவது ஒவ்வொரு தொகுப்பு Z பொருட்களுக்கும். அனைத்து முகவர்களும் கூட்டாக இருக்கும்போது, நலன்புரி அதிகபட்சமாக்கலை ஒரு எளிய பல்லுறுப்புக்கோவை-நேர வழிமுறை மூலம் செய்ய முடியும்ஃ ஒவ்வொரு உருப்படியையும் அதிகபட்சமாக ஒரு முகவருக்குக் கொடுங்கள் (உறவுகளை தன்னிச்சையாக உடைத்தல்). ஒதுக்கீட்டில் கூடுதல் கட்டுப்பாடுகள் இருக்கும்போது சிக்கல் மிகவும் சவாலானது. நியாயமான கட்டுப்பாடுகள் நியாயமான அனைத்து ஒதுக்கீடுகளிலும் நலனை அதிகரிக்க ஒருவர் விரும்பலாம், எடுத்துக்காட்டாக, ஒரு உருப்படி வரை பொறாமை இல்லாதது (EF1), ஒரு உருப்படிக்கு விகிதாசாரமானது (PROP1), அல்லது ஒரு உருப்படிக்கு சமமானது (EQ1). n மாறுபடும் போது இந்த சிக்கல் வலுவாக NP-கடினமாக இருக்கும். எந்தவொரு நிலையான n ≤ 2 க்கும், சிக்கல் பலவீனமாக NP-கடினமானது, மேலும் டைனமிக் நிரலாக்கத்தை அடிப்படையாகக் கொண்ட போலி-பல்லுறுப்புக்கோவை நேர வழிமுறையைக் கொண்டுள்ளது. n = 2 க்கு, சிக்கல் ஒரு முழுமையான பல்லுறுப்புக்கோவை-நேர தோராய திட்டத்தைக் கொண்டுள்ளது. சில முகவர் வகைகள், சில உருப்படி வகைகள் அல்லது சிறிய மதிப்பு நிலைகள் இருக்கும்போது பல்லுறுப்புக்கோவை நேரத்தில் இந்த சிக்கலைத் தீர்ப்பதற்கான வழிமுறைகள் உள்ளன. முகவர்களின் சேர்க்கை பயன்பாடுகள் பைனரியாக இருக்கும்போது (ஒவ்வொரு பொருளின் மதிப்பும் 0 அல்லது 1 ஆக இருக்கும்), அதே போல் பொதுமைப்படுத்தப்பட்ட பைனரி எனப்படும் பொதுவான வகை பயன்பாடுகளுக்கும் இந்த சிக்கலை பல்லுறுப்புக்கோவை நேரத்தில் தீர்க்க முடியும். மெட்ராய்டு கட்டுப்பாடுகள் ஒதுக்கீட்டில் மற்றொரு தடை என்னவென்றால், மூட்டைகள் ஒரு மெட்ராய்டின் சுயாதீனமான தொகுப்புகளாக இருக்க வேண்டும். எடுத்துக்காட்டாக, ஒவ்வொரு மூட்டையிலும் அதிகபட்சமாக k உருப்படிகள் இருக்க வேண்டும், இங்கு k என்பது ஒரு நிலையான முழு எண் (இது ஒரு சீரான மேட்ராய்டுக்கு ஒத்திருக்கிறது). அல்லது, உருப்படிகள் வகைகளாகப் பிரிக்கப்படலாம், மேலும் ஒவ்வொரு மூட்டையிலும் ஒவ்வொரு வகை சி யிலிருந்தும் அதிகபட்ச கேசி உருப்படிகள் இருக்க வேண்டும் (இது ஒரு பகிர்வு மேட்ராய்டுக்கு ஒத்திருக்கிறது). பொதுவாக, ஒவ்வொரு முகவருக்கும் வெவ்வேறு மேட்ராய்டு இருக்கலாம், மேலும் ஒதுக்கீடு ஒவ்வொரு முகவருக்கும் அவர்களின் சொந்த மேட்ராய்டின் சுயாதீனமான தொகுப்பான ஒரு துணைக்குழுவை வழங்க வேண்டும். பன்முக மெட்ராய்டு கட்டுப்பாடுகளின் கீழ் சேர்க்கை பயன்பாடுகளுடன் நலன்புரி அதிகரிப்பு பல்லுறுப்புக்கோவை நேரத்தில் செய்யப்படலாம், எடையுள்ள மெட்ராய்டு குறுக்குவெட்டு சிக்கலைக் குறைப்பதன் மூலம். மொத்த-மாற்று முகவர்கள் மொத்த-மாற்று பயன்பாடுகள் சேர்க்கை பயன்பாடுகளை விட பொதுவானவை. மொத்த மாற்று முகவர்களுடன் நலன்புரி அதிகரிப்பு பல்லுறுப்புக்கோவை நேரத்தில் செய்யப்படலாம். ஏனென்றால், மொத்த-மாற்று முகவர்களுடன், ஒரு வால்ரேசியன் சமநிலை எப்போதும் உள்ளது, மேலும் இது பயன்பாடுகளின் கூட்டுத்தொகையை அதிகரிக்கிறது. ஒரு வால்ரேசியன் சமநிலையை பல்லுறுப்புக்கோவை நேரத்தில் காணலாம். சப் மாடுலர் முகவர்கள் ஒரு சப் மாடுலர் முகவர் ஒரு பயன்பாட்டு செயல்பாட்டைக் கொண்டுள்ளது, இது ஒரு சப் மாடுலர் செட் செயல்பாடாகும். இதன் பொருள் முகவரின் பயன்பாடு விளிம்புகளைக் குறைக்கிறது என்பதாகும். மொத்த மாற்று பயன்பாடுகளை விட சப் மாடுலர் பயன்பாடுகள் மிகவும் பொதுவானவை. சப் மாடுலர் முகவர்களுடன் கடினத்தன்மை நலன் அதிகபட்சமாக்கல் NP-கடினமானது. மேலும், P = NP இல்லையென்றால், இதை (1-1/e) ≈ 0.632 ஐ விட சிறந்த ஒரு காரணியாக தோராயமாக மதிப்பிட முடியாது. மேலும், (1-1/e) தோராயத்தை விட சிறந்தது, P = NP என்பதைப் பொருட்படுத்தாமல், ஒரு மதிப்பு ஆரக்கிளுக்கு அதிவேக எண்ணிக்கையிலான கேள்விகள் தேவைப்படும். பேராசை வழிமுறை பின்வரும் பல்லுறுப்புக்கோவை-நேர பேராசை வழிமுறை மூலம் அதிகபட்ச நலனை தோராயமாக மதிப்பிடலாம்ஃ X1 = X2 = = Xn = காலியாக துவக்கவும். ஒவ்வொரு உருப்படிக்கும் g (ஒரு தன்னிச்சையான வரிசையில்): கணக்கிடுங்கள், ஒவ்வொரு ஏஜென் i க்கும், g க்கான அவரது விளிம்பு பயன்பாடு, பின்வருமாறு வரையறுக்கப்படுகிறதுஃ ui (xi + g)-ui (xi). மிகப்பெரிய விளிம்பு பயன்பாட்டைக் கொண்ட ஒரு முகவருக்கு உருப்படி ஜி ஐக் கொடுங்கள். பேராசை வழிமுறை ஒன்றரை காரணி தோராயத்தைக் கண்டறிகிறது என்பதை லெஹ்மன், லெஹ்மன் மற்றும் நிசான் நிரூபிக்கின்றனர் (ஃபிஷர், நெம்ஹவுசர் மற்றும் வோல்ஸி ஆகியோரின் விளைவாக ஒரு மேட்ராய்டு மீது ஒற்றை சப் மாடுலர் மதிப்பீட்டை அதிகரிப்பது குறித்து இந்த முடிவு பின்பற்றுகிறது என்பதை அவர்கள் குறிப்பிடுகின்றனர்). ஆதார யோசனை பின்வருமாறு. வழிமுறை ஒரு உருப்படி g ஐ சில முகவர் i க்கு ஒதுக்குகிறது என்று வைத்துக்கொள்வோம். இது நலனுக்கு சில தொகை v க்கு பங்களிக்கிறது, இது அந்த நேரத்தில் i க்கு g இன் ஓரளவு பயன்பாடாகும். உகந்த தீர்வில், g மற்றொரு முகவருக்கு வழங்கப்பட வேண்டும் என்று வைத்துக்கொள்வோம், k என்று சொல்லுங்கள். g ஐ i இலிருந்து k க்கு நகர்த்தினால் நலன்புரி எவ்வாறு மாறுகிறது என்பதைக் கவனியுங்கள்ஃ k இன் பயன்பாடு அதன் விளிம்பு பயன்பாடான g ஆல் அதிகரிக்கிறது, இது பேராசை தேர்வால் அதிகபட்சமாக v ஆகும். i இன் மீதமுள்ள மூட்டையின் விளிம்பு பயன்பாடு அதிகபட்சமாக v ஆல் அதிகரிக்கிறது. இது சப் மாடுலாரிட்டியிலிருந்து பின்வருமாறுஃ g இன் விளிம்பு பயன்பாடு, மீதமுள்ள மூட்டையில் சேர்க்கப்படும்போது, வழிமுறை அதை செயலாக்கும்போது அதன் விளிம்பு பயன்பாட்டை விட அதிகமாக இருக்க முடியாது. எனவே, வழிமுறை நலனுக்கான v இன் ஒவ்வொரு பங்களிப்புக்கும், உகந்த நலனுக்கான சாத்தியமான பங்களிப்பு அதிகபட்சம் 2v ஆக இருக்கலாம். எனவே, உகந்த நலன்புரி அதிகபட்சம் 2 மடங்கு வழிமுறை நலன்புரி ஆகும். பேராசை வழிமுறைக்கு 2 இன் காரணி இறுக்கமாக உள்ளது. எடுத்துக்காட்டாக, இரண்டு உருப்படிகள் x, y மற்றும் மதிப்பீடுகள் உள்ளன என்று வைத்துக்கொள்வோம்ஃ உகந்த ஒதுக்கீடு ஆலிஸ்ஃ {y}, ஜார்ஜ்ஃ {x}, நலன்புரி 2 உடன். ஆனால் பேராசை வழிமுறை முதலில் x ஐ ஒதுக்கினால், அது ஆலிஸுக்கு ஒதுக்கப்படலாம். பின்னர், y எவ்வாறு ஒதுக்கப்பட்டுள்ளது என்பதைப் பொருட்படுத்தாமல், நலன்புரி 1 மட்டுமே. ஒரு மதிப்பு ஆரக்கிளைப் பயன்படுத்தும் வழிமுறைகள் ஒரு மதிப்பு ஆரக்கிள் என்பது ஒரு ஆரக்கிள் ஆகும், இது ஒரு உருப்படிகளின் தொகுப்பைக் கொடுத்தால், முகவரின் மதிப்பை இந்த தொகுப்பிற்குத் திருப்பித் தருகிறது. இந்த மாதிரியில்ஃ டோப்ஜின்ஸ்கி மற்றும் ஷாபிரா ஒரு பாலிடைம்-அப்ராக்ஸிமேஷன் வழிமுறையையும், முகவர்களின் பயன்பாடுகள் செட்-கவரேஜ் செயல்பாடுகளாக இருக்கும் சிறப்பு வழக்குக்கான (1-1/e) ≈ 0.632-approximation வழிமுறையையும் வழங்குகிறார்கள். வோண்ட்ராக் மற்றும் கலினெஸ்கு, செக்குரி, பால் மற்றும் வோண்ட்ராக் ஆகியவை ஒரு சீரற்ற பாலிடைம் வழிமுறையை வழங்குகின்றன, இது அதிக நிகழ்தகவுடன் (1-1/இ)-ஒப்பீட்டைக் கண்டறிகிறது. அவர்களின் வழிமுறை ஒரு தொடர்ச்சியான-பேராசை வழிமுறையைப் பயன்படுத்துகிறது-ஒரு வழிமுறை ஒரு பின்ன மூட்டை (ஒவ்வொரு உருப்படிக்கும் ஒரு பின்னம் pj ஐக் கொண்ட ஒரு மூட்டை) பேராசை திசையில் (சாய்வு வம்சாவளியைப் போலவே) விரிவுபடுத்துகிறது. அவற்றின் வழிமுறையானது பின்ன மூட்டைகளின் மதிப்பைக் கணக்கிட வேண்டும், இது ஒவ்வொரு உருப்படி j யும் நிகழ்தகவு pj உடன் சுயாதீனமாக தேர்ந்தெடுக்கப்படும்போது அடையப்பட்ட மூட்டையின் எதிர்பார்க்கப்படும் மதிப்பாக வரையறுக்கப்படுகிறது. பொதுவாக, ஒரு பின்ன மூட்டையின் மதிப்பைக் கணக்கிடுவதற்கு ஒரு மதிப்பு ஆரக்கிளுக்கு 2 மீ அழைப்புகள் தேவைப்படலாம்; இருப்பினும், சீரற்ற மாதிரி மூலம் அதிக நிகழ்தகவுடன் அதை தோராயமாக கணக்கிட முடியும். இது ஒரு சீரற்ற வழிமுறைக்கு வழிவகுக்கிறது, இது அதிக நிகழ்தகவுடன் ஒரு (1-1/e)-இணக்கத்தை அடைகிறது. பின்ன மூட்டைகளை திறம்பட மதிப்பீடு செய்யக்கூடிய சந்தர்ப்பங்களில் (எ. கா. பயன்பாட்டு செயல்பாடுகள் செட்-கவரேஜ் செயல்பாடுகளாக இருக்கும்போது), வழிமுறையை தீர்மானிக்க முடியும். பொது சப் மாடுலர் செயல்பாடுகளுக்கு ஒரு தீர்மானகரமான பாலிடைம் (1-1/இ)-அப்ராக்ஸிமேஷன் வழிமுறை உள்ளதா என்பதை அவர்கள் ஒரு திறந்த சிக்கலாக குறிப்பிடுகின்றனர். நலன்புரி அதிகபட்சமாக்கல் சிக்கலை (n வெவ்வேறு சப் மாடுலர் செயல்பாடுகளுடன்) ஒரு மேட்ராய்டு கட்டுப்பாட்டிற்கு உட்பட்டு ஒரு ஒற்றை சப் மாடுலர் செட் செயல்பாட்டை அதிகரிக்கும் சிக்கலாகக் குறைக்கலாம்ஃ m உருப்படிகள் மற்றும் n முகவர்களுடன் ஒரு எடுத்துக்காட்டு கொடுக்கப்பட்டால், m * n (முகவர், உருப்படி) ஜோடிகளுடன் ஒரு நிகழ்வை உருவாக்குங்கள், அங்கு ஒவ்வொரு ஜோடியும் ஒரு முகவருக்கு ஒரு பொருளை ஒதுக்குவதைக் குறிக்கிறது. ஒவ்வொரு ஜோடிக்கும், தொடர்புடைய ஒதுக்கீட்டின் மொத்த நலனை ஒதுக்கும் ஒரு செயல்பாட்டை உருவாக்குங்கள். அனைத்து பயன்பாடுகளும் சப் மாடுலர் என்றால், இந்த நலன்புரி செயல்பாடும் சப் மாடுலர் என்பதைக் காட்டலாம். இந்த செயல்பாடு ஒரு பகிர்வு மேட்ராய்டு கட்டுப்பாட்டிற்கு உட்பட்டு அதிகரிக்கப்பட வேண்டும், ஒவ்வொரு உருப்படியும் அதிகபட்சம் ஒரு முகவருக்கு ஒதுக்கப்படுவதை உறுதிசெய்கிறது. டிமாண்ட் ஆரக்கிளைப் பயன்படுத்தும் வழிமுறைகள் முகவர்களின் பயன்பாடுகளை அணுகுவதற்கான மற்றொரு வழி டிமாண்ட் ஆரக்கிளைப் பயன்படுத்துவதாகும் (ஒரு ஆரக்கிள், ஒரு விலை-திசையன் கொடுக்கப்பட்டால், முகவரின் மிகவும் விரும்பிய மூட்டை திரும்பும்). இந்த மாதிரியில்ஃ டோப்ஜின்ஸ்கி மற்றும் ஷாபிரா ஒரு பாலிடைம் (1-1/இ)-அப்ராக்ஸிமேஷன் வழிமுறையை வழங்குகிறார்கள். ஃபைஜ் மற்றும் வோண்ட்ராக் சில சிறிய நேர்மறை ε க்கு இதை (1-1/e + ε) மேம்படுத்துகின்றன (இது மேலே உள்ள கடினத்தன்மை முடிவுக்கு முரணாக இல்லை, ஏனெனில் கடினத்தன்மை முடிவு ஒரு மதிப்பு ஆரக்கிளை மட்டுமே பயன்படுத்துகிறது; கடினத்தன்மை எடுத்துக்காட்டுகளில், டிமாண்ட் ஆரக்கிளுக்கு அதிவேகமாக பல கேள்விகள் தேவைப்படும்). துணைச்சேர்க்கை முகவர்கள் முகவர்களின் பயன்பாடுகள் துணைச்சேர்க்கை தொகுப்பு செயல்பாடுகளாக இருக்கும்போது (துணை மாடுலரை விட பொதுவானவை), ஒரு தோராயத்திற்கு அதிவேக எண்ணிக்கையிலான மதிப்பு வினவல்கள் தேவைப்படும். ஃபைஜ் இந்த சிக்கலுக்கான எல்பி தளர்வுக்கான எந்தவொரு பின்னத் தீர்வையும் குறைந்தபட்சம் பாதி பின்னத் தீர்வின் மதிப்புடன் ஒரு சாத்தியமான தீர்வுக்கு வட்டமிடுவதற்கான ஒரு வழியை வழங்குகிறது. இது பொதுவான துணைச் சேர்க்கை முகவர்களுக்கு 1/2-இணக்கத்தையும், (1-1/e)-பின்ன-சேர்க்கை மதிப்பீடுகளின் சிறப்பு வழக்குக்கு இணக்கத்தையும் அளிக்கிறது. முகவர்களின் பயன்பாடுகள் கூடுதல் தொகுப்பு செயல்பாடுகளாக இருக்கும்போது (சூப்பர் மாடுலரை விட பொதுவானவை), ஒரு தோராயத்திற்கு மதிப்பு வினவல்களின் சூப்பர்-பல்லுறுப்புக்கோவை எண் தேவைப்படும். ஒற்றை எண்ணம் கொண்ட முகவர்கள் ஒரு ஒற்றை எண்ணம் கொண்ட முகவர் ஒரு குறிப்பிட்ட பொருட்களின் தொகுப்பை மட்டுமே விரும்புகிறார். ஒவ்வொரு ஒற்றை எண்ணம் கொண்ட முகவர் i க்கு, ஒரு கோரப்பட்ட தொகுப்பு Di உள்ளது, மற்றும் ஒரு மதிப்பு Vi> 0, அத்தகைய. அதாவது, முகவர் ஒரு நிலையான நேர்மறை பயன்பாட்டைப் பெறுகிறார், அவர்களின் மூட்டை அவர்கள் கோரிய தொகுப்பைக் கொண்டிருந்தால் மட்டுமே. ஒற்றை எண்ணம் கொண்ட முகவர்களுடன் நலன்புரி அதிகரிப்பு NP-கடினமானது, அனைவருக்கும் கூட. இந்த விஷயத்தில், சிக்கல் செட் பேக்கிங்கிற்கு சமம், இது NP ஹார்ட் என்று அறியப்படுகிறது. மேலும், எந்தவொரு நிலையான காரணியிலும் இதை தோராயமாக மதிப்பிட முடியாது (சப் மாடுலர் முகவர்களின் விஷயத்தில் மாறாக). நன்கு அறியப்பட்ட வழிமுறை ஒரு காரணிக்குள் அதை தோராயமாக மதிப்பிடுகிறது. முகவர்கள் தன்னிச்சையான மோனோடோன் பயன்பாட்டு செயல்பாடுகளை (நிரப்பு உருப்படிகள் உட்பட) கொண்டிருக்கும்போது, நலன்புரி அதிகபட்சமாக்கல் எந்தவொரு காரணிக்கும் தோராயமாக மதிப்பிடுவது கடினம். இருப்பினும், மாநில விண்வெளி தேடலை அடிப்படையாகக் கொண்ட வழிமுறைகள் நடைமுறையில் நன்றாக வேலை செய்கின்றன. மேலும் காண்க பயன்பாட்டு அதிகபட்ச சிக்கல் குறிப்புகள் உகப்பாக்கம் வழிமுறைகள் மற்றும் முறைகள்