Matroid-constrained number partitioning
மெட்ராய்டு-கட்டுப்படுத்தப்பட்ட எண் பகிர்வு என்பது பல்வழி எண் பகிர்வு சிக்கலின் ஒரு மாறுபாடு ஆகும், இதில் பகிர்வில் உள்ள துணைக்குழுக்கள் ஒரு மெட்ராய்டின் சுயாதீனமான தொகுப்புகளாக இருக்க வேண்டும். இந்த சிக்கலுக்கான உள்ளீடு உருப்படிகளின் தொகுப்பு S, ஒரு நேர்மறை முழு எண் m, மற்றும் அதே தொகுப்பு S மீது சில m மேட்ராய்டுகள் ஆகும். குறிக்கோள் S ஐ m துணைக்குழுக்களாகப் பிரிப்பதாகும், அதாவது ஒவ்வொரு துணைக்குழுவும் i என்பது மேட்ராய்டு i இல் ஒரு சுயாதீனமான தொகுப்பாகும். இந்த கட்டுப்பாட்டிற்கு உட்பட்டு, சில புறநிலை செயல்பாடு குறைக்கப்பட வேண்டும், எடுத்துக்காட்டாக, ஒரு துணைக்குழுவில் உள்ள மிகப்பெரிய தொகை உருப்படி அளவுகளைக் குறைத்தல். மிகவும் பொதுவான மாறுபாட்டில், எம் மேட்ராய்டுகள் ஒவ்வொன்றும் ஒரு எடை செயல்பாட்டைக் கொண்டுள்ளன, இது தரை-தொகுப்பின் ஒவ்வொரு உறுப்புக்கும் ஒரு எடையை ஒதுக்குகிறது. பல்வேறு புறநிலை செயல்பாடுகள் பரிசீலிக்கப்பட்டுள்ளன. அதிகபட்சம், குறைந்தபட்சம், தொகை ஆகிய மூன்று இயக்கிகள் ஒவ்வொன்றிற்கும், ஒவ்வொரு துணைக்குழுவிலும் உள்ள பொருட்களின் எடைகளிலும், துணைக்குழுக்களிலும் இந்த இயக்கியைப் பயன்படுத்தலாம். மொத்தத்தில், 9 சாத்தியமான புறநிலை செயல்பாடுகள் உள்ளன, அவை ஒவ்வொன்றையும் அதிகரிக்கலாம் அல்லது குறைக்கலாம். சிறப்பு நிகழ்வுகள் மேட்ராய்டு-கட்டுப்படுத்தப்பட்ட பகிர்வு சிக்கல்களின் சில முக்கியமான சிறப்பு நிகழ்வுகள்ஃ (அதிகபட்சம், கூட்டுத்தொகை) நோக்கம் என்பது அனைத்து துணைக்குழுக்களிலும் அதிகபட்சம், துணைக்குழுவில் உள்ள மொத்த எடையாகும். உருப்படிகள் வேலைகளைக் குறிக்கும் போது மற்றும் எடைகள் அவற்றின் நீளத்தைக் குறிக்கும் போது, இந்த நோக்கம் வெறுமனே அட்டவணையின் மேக்ஸ்பான் ஆகும். எனவே, இந்த நோக்கத்தைக் குறைப்பது மேட்ராய்டு கட்டுப்பாடுகளின் கீழ் மேக்ஸ்பனைக் குறைப்பதற்கு சமம். அதிகபட்சம் (குறைந்தபட்சம், தொகை) என்ற இரட்டை இலக்கும் இந்த சூழலில் ஆய்வு செய்யப்பட்டுள்ளது. மேட்ராய்டுகள் இலவச மேட்ராய்டுகள் (கட்டுப்பாடுகள் இல்லை) மற்றும் எம் எடை-செயல்பாடுகள் ஒரே மாதிரியாக இருக்கும் சிறப்பு வழக்கு ஒத்த இயந்திரங்கள் திட்டமிடலுக்கு ஒத்திருக்கிறது, இது மல்ட்வே எண் பகிர்வு என்றும் அழைக்கப்படுகிறது. இலவச மேட்ராய்டுகள் மற்றும் வெவ்வேறு எடை-செயல்பாடுகளின் வழக்கு தொடர்பில்லாத இயந்திரங்களின் திட்டமிடலுக்கு ஒத்திருக்கிறது. சீரான மேட்ராய்டுகளின் சிறப்பு வழக்கு துணைக்குழுக்களில் உள்ள கார்டினாலிட்டி கட்டுப்பாடுகளுக்கு ஒத்திருக்கிறது. பகிர்வு மேட்ராய்டுகளின் மிகவும் பொதுவான வழக்கு வகைப்படுத்தப்பட்ட கார்டினாலிட்டி கட்டுப்பாடுகளுக்கு ஒத்திருக்கிறது. இந்த சிக்கல்கள் சமச்சீர் எண் பகிர்வு பற்றிய பக்கத்தில் விவரிக்கப்பட்டுள்ளன. (கூட்டுத்தொகை, கூட்டுத்தொகை) நோக்கம் என்பது அனைத்து துணைக்குழுக்களிலும் உள்ள அனைத்து பொருட்களின் எடைகளின் கூட்டுத்தொகையாகும், இதில் ஒவ்வொரு துணைக்குழுவிலும் உள்ள எடைகள் மேட்ராய்டு i இன் எடை-செயல்பாட்டால் கணக்கிடப்படுகின்றன. இந்த நோக்கத்தைக் குறைப்பது எடையுள்ள மேட்ராய்டு குறுக்குவெட்டு சிக்கலாகக் குறைக்கப்படலாம்-கொடுக்கப்பட்ட இரண்டு மேட்ராய்டுகளில் ஒரே நேரத்தில் சுயாதீனமான அதிகபட்ச எடை துணைக்குழுவைக் கண்டறிதல். இந்த சிக்கலை பல்லுறுப்புக்கோவை நேரத்தில் தீர்க்க முடியும். (அதிகபட்சம், அதிகபட்சம்) நோக்கம் என்பது அனைத்து துணைக்குழுக்களிலும் அதிகபட்ச எடையாகும், அங்கு ஒவ்வொரு துணைக்குழுவிலும் உள்ள எடைகள் மேட்ராய்டு i இன் எடை-செயல்பாட்டால் கணக்கிடப்படுகின்றன. இந்த நோக்கத்தை கிராஃபிக் மேட்ராய்டுகளுடன் குறைப்பது குறைந்தபட்ச தடையாக பரவியிருக்கும் மரப் பிரச்சினையைத் தீர்க்கப் பயன்படுத்தப்படலாம். (கூட்டுத்தொகை, குறைந்தபட்சம்) குறிக்கோள் என்பது அனைத்து துணைக்குழுக்களிலும் குறைந்தபட்ச எடைகளின் கூட்டுத்தொகையாகும். இந்த நோக்கத்தை அதிகப்படுத்துவது, k ஒத்த வரைகலை மேட்ராய்டுகளுடன், மரப் பகிர்வு சிக்கலில் பரவியிருக்கும் அதிகபட்ச மொத்த திறனைத் தீர்க்கப் பயன்படுத்தப்படலாம். (கூட்டுத்தொகை, அதிகபட்சம்) குறிக்கோள் என்பது அனைத்து துணைக்குழுக்களிலும் அதிகபட்ச எடைகளின் கூட்டுத்தொகையாகும். இந்த நோக்கம் திட்டமிடலுக்குத் தேவையான மொத்த நினைவகத்தைக் குறிக்கலாம், ஒவ்வொரு மேட்ராய்டு i இயந்திரத்தில் சாத்தியமான ஒதுக்கீடுகளைக் குறிக்கும் போது. பொது மேட்ராய்டு கட்டுப்பாடுகள் பொது மேட்ராய்டு கட்டுப்பாடுகள் முதலில் பர்கார்ட் மற்றும் யாவோ ஆகியோரால் பரிசீலிக்கப்பட்டன. பகிர்வு மேட்ராய்டுகளை உள்ளடக்கிய மேட்ராய்டுகளின் துணைப்பிரிவுக்கான பேராசை வழிமுறை மூலம் பல்லுறுப்புக்கோவை நேரத்தில் குறைத்தல் (தொகை, அதிகபட்சம்) செய்ய முடியும் என்பதை அவர்கள் காட்டினர். ஹ்வாங் மற்றும் ரோத்ப்லம் ஒரு மாற்று போதுமான நிபந்தனையை வழங்கினர். வூ மற்றும் யாவோ ஆகியோர் பொதுவான மேட்ராய்டு கட்டுப்பாடுகளுடன் (அதிகபட்சம், தொகை) குறைப்பதற்கான தோராயமான வழிமுறையை வழங்கினர். அப்பாஸி, மிர்ரோக்னி மற்றும் தாக்கூர் ஆகியோர் மேட்ராய்டு கட்டுப்பாடுகளின் கீழ் பன்முகத்தன்மை அதிகபட்சமாக்கல் சிக்கலுக்கான தோராயமான வழிமுறையை வழங்குகிறார்கள். கவாஸே, கிமுரா, மகினோ மற்றும் சுமிதா ஆகியோர் அதிகபட்ச சிக்கல்களை குறைந்தபட்ச சிக்கல்களாக குறைக்க முடியும் என்பதைக் காட்டுகிறார்கள். பின்னர், அவர்கள் ஏழு மினிமைசேஷன் சிக்கல்களை பகுப்பாய்வு செய்கிறார்கள்ஃ மினிமைசிங் (கூட்டுத்தொகை, அதிகபட்சம்): மேட்ராய்டுகள் மற்றும் எடைகள் ஒரே மாதிரியாக இருந்தாலும் கூட சிக்கல் வலுவாக NP-கடினமாக உள்ளது. ஒரே மாதிரியான மேட்ராய்டுகள் மற்றும் எடைகளுக்கு ஒரு பி. டி. ஏ. எஸ் உள்ளது. பொதுவான மேட்ராய்டுகள் மற்றும் எடைகளுக்கு, எந்த ε> 0 க்கும் εm-ஏப்ரோக்ஸிமேஷன் வழிமுறை உள்ளது. இது O (log m) காரணியுடன் தோராயமாக NP-கடினமானது. மினிமைசிங் (குறைந்தபட்சம், குறைந்தபட்சம்), (அதிகபட்சம், அதிகபட்சம்), (குறைந்தபட்சம், அதிகபட்சம்) மற்றும் (குறைந்தபட்சம், தொகை): பல்லுறுப்புக்கோவை-நேர வழிமுறைகள் உள்ளன. அவை மேட்ராய்டு பகிர்வு சிக்கலின் சாத்தியக்கூறு சிக்கலுக்கு சிக்கல்களைக் குறைக்கின்றன. குறைத்தல் (அதிகபட்சம், குறைந்தபட்சம்) மற்றும் (கூட்டுத்தொகை, குறைந்தபட்சம்): ஒரே மாதிரியான மேட்ராய்டுகள் மற்றும் எடைகளுக்கு பல்லுறுப்புக்கோவை-நேர வழிமுறைகள் உள்ளன. பொதுவாக, இது தோராயமாக கூட வலுவாக NP-கடினமாக உள்ளது. மற்ற இரண்டு சிக்கல்களும் முந்தைய படைப்புகளில் பகுப்பாய்வு செய்யப்பட்டனஃ குறைத்தல் (அதிகபட்சம், கூட்டுத்தொகை) வலுவாக NP-கடினமானது (3-பகிர்வு ஒரு சிறப்பு வழக்கு), மற்றும் குறைத்தல் (கூட்டுத்தொகை, கூட்டுத்தொகை) ஐ எடை கொண்ட மேட்ராய்டு குறுக்குவெட்டாக குறைக்கலாம், இது பல்லுறுப்புக்கோவை. தொடர்புடைய சிக்கல்கள் மேட்ராய்டு பகிர்வு ஒரு வித்தியாசமான சிக்கலாகும், இதில் பகுதிகளின் எண்ணிக்கை m சரி செய்யப்படவில்லை. ஒரு ஒற்றை மேட்ராய்டு உள்ளது, மேலும் அதன் கூறுகளை ஒரு சிறிய எண்ணிக்கையிலான சுயாதீன தொகுப்புகளாகப் பிரிப்பதே குறிக்கோள். குறிப்புகள் மேட்ராய்டு கோட்பாடு எண் பகிர்வு