Balanced number partitioning
சமநிலையான எண் பகிர்வு என்பது பல வழி எண் பகிர்வின் ஒரு மாறுபாடு ஆகும், இதில் ஒவ்வொரு தொகுப்புக்கும் ஒதுக்கப்பட்ட உருப்படிகளின் எண்ணிக்கையில் கட்டுப்பாடுகள் உள்ளன. சிக்கலுக்கான உள்ளீடு வெவ்வேறு அளவுகளில் உள்ள n உருப்படிகளின் தொகுப்பாகும், மேலும் இரண்டு முழு எண்கள் m, k. வெளியீடு என்பது உருப்படிகளை m துணைக்குழுக்களாகப் பிரிப்பதாகும், அதாவது ஒவ்வொரு துணைக்குழுவிலும் உள்ள உருப்படிகளின் எண்ணிக்கை அதிகபட்சம் k ஆகும். இதற்கு உட்பட்டு, m துணைக்குழுக்களில் உள்ள அளவுகளின் கூட்டுத்தொகை முடிந்தவரை ஒத்ததாக இருக்க வேண்டும். ஒரு எடுத்துக்காட்டு பயன்பாடு ஒரே மாதிரியான இயந்திரங்கள் திட்டமிடல் ஆகும், அங்கு ஒவ்வொரு இயந்திரமும் அதிகபட்ச k வேலைகளை வைத்திருக்கக்கூடிய ஒரு வேலை-கியூவைக் கொண்டுள்ளது. விஎல்எஸ்ஐ சில்லுகளின் உற்பத்தியிலும், நெகிழ்வான உற்பத்தி அமைப்புகளில் இயந்திரங்களுக்கு கருவிகளை ஒதுக்குவதிலும் இந்த சிக்கல் பயன்பாடுகளைக் கொண்டுள்ளது. உகந்த வேலை திட்டமிடல் சிக்கல்களுக்கான நிலையான மூன்று-புல குறியீட்டில், மிகப்பெரிய தொகையைக் குறைப்பதில் உள்ள சிக்கல் சில நேரங்களில் "P | #≤ k | Cmax" ஆல் குறிக்கப்படுகிறது. நடுத்தர புலம் "#≤ k" என்பது ஒவ்வொரு இயந்திரத்திலும் உள்ள வேலைகளின் எண்ணிக்கை அதிகபட்சமாக k ஆக இருக்க வேண்டும் என்பதைக் குறிக்கிறது. இரு வழி சமநிலையான பகிர்வு இரண்டு துணைக்குழுக்கள் (m = 2) இருக்க வேண்டும் போது இரு வழி சமநிலையான பகிர்வு என்று அழைக்கப்படும் ஒரு பொதுவான சிறப்பு வழக்கு. இரண்டு துணைக்குழுக்களும் தரை (n/2) மற்றும் கூரை (n/2) உருப்படிகளைக் கொண்டிருக்க வேண்டும். இது பகிர்வு சிக்கலின் ஒரு மாறுபாடு ஆகும். இரண்டு துணைக்குழுக்களில் உள்ள தொகைகள் சமமாக இருக்கும் ஒரு பகிர்வு இருக்கிறதா என்பதை தீர்மானிக்க NP-கடினமாக உள்ளது; சிக்கலைப் பார்க்கவும் [SP12]. பல வழிமுறைகள் உள்ளன, அவை ஒரு சீரான பகிர்வை கண்டுபிடிப்பதை நோக்கமாகக் கொண்டுள்ளன, இதில் தொகை முடிந்தவரை சமமாக இருக்கும். காஃப்மேன், ஃப்ரெடெரிக்சன் மற்றும் லுக்கர் ஆகியோர் எல். பி. டி வழிமுறையின் (ஆர். எல். பி. டி என்று அழைக்கப்படும்) கட்டுப்படுத்தப்பட்ட பதிப்பை வழங்குகிறார்கள், இதில் உள்ளீடுகள் ஜோடிகளாக ஒதுக்கப்படுகின்றன. உள்ளீடுகள் ஒரே சீராக விநியோகிக்கப்படும்போது, RLPT இன் எதிர்பார்க்கப்படும் மிகப்பெரிய தொகை சரியாக இருக்கும். எதிர்பார்க்கப்படும் வேலை-வேறுபாடு (மிகப்பெரிய மற்றும் மிகச்சிறிய தொகைக்கு இடையிலான வேறுபாடு). லுக்கர் எல். டி. எம் வழிமுறையின் ஒரு மாறுபாட்டை முன்வைக்கிறார் (ஜோடி வாரியான வேறுபாடு முறை (பி. டி. எம்) என்று அழைக்கப்படுகிறது). அதன் எதிர்பார்க்கப்பட்ட வேலை-வேறுபாடு. சாய் கட்டுப்படுத்தப்பட்ட மிகப்பெரிய வேறுபாடு (ஆர். எல். டி) எனப்படும் ஒரு வழிமுறையை முன்வைக்கிறார். அதன் வேலை-வேறுபாடு கிட்டத்தட்ட நிச்சயமாக உள்ளது. பி. எல். டி. எம் என்று அழைக்கப்படும் எம் = 2 க்கான எல். டி. எம் வழிமுறையின் சீரான மாறுபாட்டை யாக்கிர் முன்வைக்கிறார். அதன் எதிர்பார்க்கப்பட்ட வேலை-வேறுபாடு. மெர்டன்ஸ் சமநிலையான இரு வழி பகிர்வுக்கான முழுமையான எந்த நேரத்திலும் வழிமுறையை வழங்குகிறது. இது பி. எல். டி. எம் வழிமுறையை முழுமையான கர்மார்கர்-கார்ப் வழிமுறையுடன் ஒருங்கிணைக்கிறது. 3-பகிர்வு என்று அழைக்கப்படும் மற்றொரு சிறப்பு வழக்கு, ஒவ்வொரு துணைக்குழுவிலும் உள்ள உருப்படிகளின் எண்ணிக்கை அதிகபட்சம் 3 (k = 3) ஆக இருக்க வேண்டும். சமமான தொகைகளுடன் அத்தகைய பகிர்வு இருக்கிறதா என்பதைத் தீர்மானிப்பது சரியாக 3-பகிர்வு சிக்கலாகும், இது வலுவாக NP-கடினமாக அறியப்படுகிறது. மொத்த தொகை முடிந்தவரை கிட்டத்தட்ட சமமாக இருக்கும் ஒரு பகிர்வை கண்டுபிடிப்பதை நோக்கமாகக் கொண்ட தோராயமான வழிமுறைகள் உள்ளன. கெல்லர் மற்றும் வோயிஞ்சர் LPT வழிமுறையை மூன்று மடங்கு பகிர்வுக்கு மாற்றியமைக்கிறார்கள் (அதிகபட்சம் 3 * மீ உருப்படிகள் உள்ளன, மேலும் ஒவ்வொரு துணைக்குழுவிலும் அதிகபட்சம் 3 உருப்படிகள் இருக்க வேண்டும்). அவற்றின் வழிமுறை மாற்றியமைக்கப்பட்ட-எல்பிடி அல்லது எம்எல்பிடி என்று அழைக்கப்படுகிறது. இது பெரியது முதல் சிறியது வரை பொருட்களை ஆர்டர் செய்கிறது, மேலும் ஒவ்வொரு பொருளையும் 3 க்கும் குறைவான பொருட்களைக் கொண்ட தொட்டிகளில் மிகச்சிறிய தொகையுடன் தொட்டியில் வைக்கிறது. எம்எல்பிடி வழிமுறை குறைந்தபட்ச மிகப்பெரிய தொகையின் பெரும்பகுதியை அடைகிறது என்பதை அவை காட்டுகின்றன, இது கட்டுப்பாடற்ற சிக்கலுக்கு எல்பிடி அடையும் அதே தோராய விகிதமாகும். எம்எல்பிடிக்கு எல்லை இறுக்கமாக உள்ளது. சென், ஹீ மற்றும் லின், அதே சிக்கலுக்கு, எம். எல். பி. டி குறைந்தபட்சம் அதிகபட்ச மிகச்சிறிய தொகையை அடைகிறது என்பதைக் காட்டுகிறது, இது மீண்டும் கட்டுப்பாடற்ற சிக்கலுக்கு எல். பி. டி அடையும் அதே விகிதமாகும். கெல்லர் மற்றும் கோட்டோவ் ஒரு வித்தியாசமான வழிமுறையை முன்வைக்கிறார்கள் (சரியாக 3 * மீ உருப்படிகளின் விஷயத்தில்), இது குறைந்தபட்ச மிகப்பெரிய தொகையின் பெரும்பகுதியை அடைகிறது. பெரிய கார்டினாலிட்டிகளுடன் சமநிலையான பகிர்வு k-பகிர்வு என்று அழைக்கப்படும் ஒரு பொதுவான வழக்கு, ஒவ்வொரு துணைக்குழுவிலும் உள்ள உருப்படிகளின் எண்ணிக்கை அதிகபட்சமாக k ஆக இருக்க வேண்டும், அங்கு k எந்த நேர்மறை முழு எண்ணாகவும் இருக்கலாம். பாபெல், கெல்லர் மற்றும் கோட்டோவ் ஒரு மாறுபாட்டை ஆய்வு செய்கிறார்கள், இதில் k × m உருப்படிகள் உள்ளன (சில முழு எண் k க்கு), மேலும் ஒவ்வொரு m தொகுப்புகளும் சரியாக k உருப்படிகளைக் கொண்டிருக்க வேண்டும். குறைந்தபட்ச மிகப்பெரிய கூட்டுத்தொகையை தோராயமாக மதிப்பிடுவதற்கான பல ஹூரிஸ்டிக் வழிமுறைகளை அவை வழங்குகின்றனஃ மடிப்பு வழிமுறைஃ m = 2 க்கு உகந்த, பொதுவாக இறுக்கமான தோராய விகிதத்தைக் கொண்டுள்ளது. பரிமாற்ற வழிமுறைஃ இறுக்கமான தோராய விகிதம். இது பல்லுறுப்புக்கோவை நேரத்தில் இயங்குகிறதா என்பது தெரியவில்லை. முதன்மை-இரட்டை வழிமுறை (எல்பிடி மற்றும் மல்டிஃபிட் ஆகியவற்றின் கலவை): அதிகபட்ச தோராய விகிதம். m போதுமான அளவு பெரியதாக இருக்கும்போது இது k = 4 க்கு இறுக்கமாக இருக்கும்; துல்லியமான கீழ் வரம்பு). மாற்றியமைக்கப்பட்ட-எல். பி. டி ஒரு தோராயமான விகிதத்தைக் கொண்டுள்ளது என்ற அனுமானமும் உள்ளது. தற்போது, இந்த அனுமானம் k = 3 க்கு மட்டுமே உண்மை என்று அறியப்படுகிறது. k> 3 ஐப் பொறுத்தவரை, அதன் தோராய விகிதம் அதிகபட்சம் 2 என்று அறியப்படுகிறது. மைக்கேல்ஸ், கோர்ஸ்ட், ஆர்ட்ஸ், வான் லீயுவென் மற்றும் ஸ்பிக்ஸ்மா ஆகியோர் ஒரு மாறுபாட்டை ஆய்வு செய்கிறார்கள், இதில் ஒவ்வொரு எம் செட்டிலும் உச்சவரம்பு (என்/மீ) அல்லது தரை (என்/மீ) உருப்படிகள் இருக்க வேண்டும் (எனவே கே = உச்சவரம்பு (என்/மீ)). அவை சமநிலையான-எல். டி. எம் (பி. எல். டி. எம்) ஐ எம் = 2 முதல் பொதுவான எம் வரை நீட்டிக்கின்றன. பொதுவான வழிமுறை காலப்போக்கில் இயங்குகிறது. குறைந்தபட்ச மிகப்பெரிய தொகைக்கான அதன் தோராயமான விகிதம் k = 3 க்கு 4/3, k = 4 க்கு 19/12, k = 5 க்கு 103/60, k = 6 க்கு 643/360 மற்றும் k = 7 க்கு 4603/2520 என்று அவை நிரூபிக்கின்றன. கலப்பு முழு எண் நேரியல் நிரலைத் தீர்ப்பதன் மூலம் விகிதங்கள் கண்டறியப்பட்டன. பொதுவாக (எந்த k க்கும்), தோராய விகிதம் குறைந்தபட்சம் மற்றும் அதிகபட்சமாக இருக்கும். 3,4,5,6,7 க்கான சரியான MILP முடிவுகள் கீழ் வரம்பிற்கு ஒத்திருக்கின்றன. k> 7 க்கு, சரியான முடிவுகள் எதுவும் தெரியவில்லை, ஆனால் கீழ் மற்றும் மேல் வரம்புக்கு இடையிலான வேறுபாடு 0.3% க்கும் குறைவாக உள்ளது. அளவுரு என்பது துணைக்குழுக்களின் எண்ணிக்கை (மீ) ஆக இருக்கும்போது, தோராயமான விகிதம் சரியாக இருக்கும். உள்ளீடுகள் ஒரே மாதிரியாக விநியோகிக்கப்படும் போதும், அவற்றின் விநியோகம் வளைக்கப்படும் போதும் பி. எல். டி. எம் அதிக வேலை-வேறுபாடு (மிக உயர்ந்த மற்றும் மிகக் குறைந்த தொகைக்கு இடையிலான வேறுபாடு) கொண்ட பகிர்வுகளை வழங்கக்கூடும் என்பதை ஜாங், மௌரடிடிஸ் மற்றும் பாங் காட்டுகின்றன. அவர்கள் இரண்டு மாற்று ஆராய்ச்சிகளை முன்மொழிகிறார்கள்ஃ LRM வேலை-வேறுபாட்டை மூன்றில் ஒரு பங்காகக் குறைக்கிறது, விநியோகம் ஒரே மாதிரியாக இருக்கும்போது BLDM இன் வேலை-வேறுபாடு; விநியோகம் வளைக்கப்படும்போது மெல்ட் வேலை-வேறுபாட்டைக் குறைக்கிறது. ஒரு கலப்பின வழிமுறை பி. எல். டி. எம், எல். ஆர். எம் மற்றும் மெல்ட் ஆகியவற்றை ஒருங்கிணைக்கிறது மற்றும் வெவ்வேறு தரவு விநியோகங்களுக்கு மாறும் வகையில் மாற்றியமைக்கிறது. கே சரிசெய்யப்படும்போது, ஹோக்பாம் மற்றும் ஷ்மோய்களின் பி. டி. ஏ. எஸ் சமநிலையான பகிர்வுக்கு பயன்படுத்தப்படலாம். k என்பது உள்ளீட்டின் ஒரு பகுதியாக இருக்கும்போது, தற்போது PTAS எதுவும் அறியப்படவில்லை. அனைத்து செட்களிலும் உள்ள பொருட்களின் எண்ணிக்கை அதிகபட்சமாக k ஆக இருக்கும்போது மிகப்பெரிய தொகையை குறைப்பதில் உள்ள சிக்கலை டெல் 'அமிகோ மற்றும் மார்டெல்லோ ஆய்வு செய்கிறார்கள். இந்த மாறுபாட்டின் நேரியல்-நிரல் தளர்வு கட்டுப்பாடற்ற மாறுபாட்டின் LP தளர்வுக்கு சமமான உகந்த மதிப்பைக் கொண்டுள்ளது என்பதை அவர்கள் காட்டுகிறார்கள். வெளிப்பாடு, xi என்பது பெரியது முதல் சிறியது வரை வரிசைப்படுத்தப்பட்ட உள்ளீடுகள், உகந்த மிகப்பெரிய தொகைக்கு குறைந்த வரம்பாகும், மேலும் அதன் மோசமான-வழக்கு விகிதம் இரண்டு வகைகளிலும் 1/2 ஆகும். மேம்பட்ட வெளிப்பாடு கட்டுப்பாடற்ற மாறுபாட்டில் 2/3 மற்றும் கட்டுப்படுத்தப்பட்ட மாறுபாட்டில் 1/2 என்ற மோசமான விகிதத்தைக் கொண்டுள்ளது. மாற்றியமைக்கப்பட்ட பட்டியல் திட்டமிடலின் தோராயமான விகிதம் கட்டுப்பாடற்ற மாறுபாட்டிற்கு 1/2 ஆகும், ஆனால் இது கட்டுப்படுத்தப்பட்ட மாறுபாட்டிற்கு 0 ஆகும் (இது தன்னிச்சையாக மோசமாக இருக்கலாம்). மாற்றியமைக்கப்பட்ட LPT வழிமுறையின் தோராய விகிதம் அதிகபட்சம் 2 ஆகும். கீழ் எல்லை 3/4 என்ற இறுக்கமான மோசமான செயல்திறன் விகிதத்தைக் கொண்டுள்ளது என்பதையும், அவற்றின் PD வழிமுறை 4/3 என்ற இறுக்கமான செயல்திறன் விகிதத்தைக் கொண்டுள்ளது என்பதையும் அவை காட்டுகின்றன (m போதுமான அளவு பெரியதாக இருக்கும்போது). அவர், டான், ஜு மற்றும் யாவோ ஆகியோர் மிகச்சிறிய தொகையை அதிகரிப்பதில் உள்ள சிக்கலைக் கருத்தில் கொள்கிறார்கள். ஃபோல்டிங் வழிமுறை இறுக்கமான தோராய விகிதத்தைக் கொண்டுள்ளது என்பதை அவை காட்டுகின்றன. அவர்கள் ஒரு புதிய வழிமுறையை முன்வைக்கிறார்கள், ஹார்மோனிக் 1, குறைந்தபட்சம் மோசமான-வழக்கு விகிதத்துடன். இந்த இரண்டு வழிமுறைகளும் வரிசைப்படுத்தப்பட்டவை-அவை உருப்படிகளை அவற்றின் சரியான மதிப்புகளை விட அவற்றுக்கிடையேயான வரிசையின் அடிப்படையில் மட்டுமே பிரிக்கின்றன. எந்தவொரு வரிசை வழிமுறைக்கும் மிகச்சிறிய கூட்டுத்தொகையை அதிகரிக்க அதிகபட்ச விகிதம் உள்ளது என்பதை அவை நிரூபிக்கின்றன. இது ஹார்மோனிக் 1 அறிகுறியற்ற வகையில் உகந்ததாக இருப்பதைக் குறிக்கிறது. எந்தவொரு நிலையான k க்கும், எந்தவொரு வரிசை வழிமுறையும் சமன்பாட்டின் மிகச்சிறிய மூலத்தின் விகிதத்தைக் கொண்டுள்ளது. k முடிவிலிக்குச் செல்லும்போது, இந்த மேல் வரம்பு 0 ஐ அணுகுகிறது. சமநிலையான மற்றும் கட்டுப்பாடற்ற சிக்கல்களுக்கு இடையிலான உறவுகள் சமநிலையான பகிர்வு சிக்கலுக்கான தோராயங்களுக்கும் நிலையான (கட்டுப்பாடற்ற) பகிர்வு சிக்கலுக்கும் இடையே சில பொதுவான உறவுகள் உள்ளன. பாபெல், கெல்லர் மற்றும் கோட்டோவ் ஆகியோர் கட்டுப்பாடற்ற உகந்த மற்றும் கட்டுப்படுத்தப்பட்ட உகந்த இடையேயான விகிதம் அதிகபட்சம் மற்றும் இறுக்கமானது என்பதை நிரூபிக்கின்றனர். கெல்லர் மற்றும் கோட்டோவ் ஆகியோர் k திறன் மற்றும் தோராயமான விகிதத்துடன் சமச்சீர் பகிர்வுக்கான ஒவ்வொரு ஆய்வையும் (குறைந்தபட்ச மிகப்பெரிய தொகைக்கு) தோராயமான விகிதத்துடன் கட்டுப்பாடற்ற பகிர்வுக்கான ஆய்வைப் பெற பயன்படுத்தலாம் என்பதை நிரூபிக்கின்றனர். குறிப்பாக, மும்மடங்கு பகிர்வுக்கான (k = 3) அவற்றின்-அணுகுமுறை வழிமுறை தோராயமான விகிதத்துடன் கட்டுப்பாடற்ற பகிர்வுக்கான ஒரு ஹூரிஸ்டிக்கைப் பெற பயன்படுத்தப்படலாம். வெவ்வேறு கார்டினாலிட்டி கட்டுப்பாடுகள் ஒவ்வொரு துணைக்குழுவிலும் வெவ்வேறு கட்டுப்பாடுகளை அனுமதிப்பதன் மூலம் கார்டினாலிட்டி கட்டுப்பாடுகளை பொதுமைப்படுத்தலாம். இந்த மாறுபாடு கி-பகிர்வு சிக்கலை அழைக்கும் "திறந்த சிக்கல்கள்" பிரிவில் அறிமுகப்படுத்தப்பட்டுள்ளது. அவர், டான், ஜு மற்றும் யாவோ ஆகியோர் வெவ்வேறு கார்டினாலிட்டி கட்டுப்பாடுகளுடன் மிகச்சிறிய கூட்டுத்தொகையை அதிகரிக்க ஹார்மோனிக் 2 என்ற வழிமுறையை முன்வைக்கின்றனர். குறைந்தபட்சம் அதன் மோசமான-வழக்கு விகிதம் என்பதை அவை நிரூபிக்கின்றன. வகைப்படுத்தப்பட்ட கார்டினாலிட்டி கட்டுப்பாடுகள் கார்டினாலிட்டி கட்டுப்பாடுகளின் மற்றொரு பொதுமைப்படுத்தல் பின்வருமாறு. உள்ளீட்டு உருப்படிகள் k வகைகளாக பிரிக்கப்பட்டுள்ளன. ஒவ்வொரு வகை எச்-க்கும், திறன் கட்டுப்பாடு கே. எச் உள்ளது. எம் துணைக்குழுக்கள் ஒவ்வொன்றும் அதிகபட்சமாக எச் வகையைச் சேர்ந்த கே. எச் உருப்படிகளைக் கொண்டிருக்கலாம். வேறு வார்த்தைகளில் கூறுவதானால்ஃ அனைத்து எம் துணைக்குழுக்களும் ஒரு குறிப்பிட்ட பகிர்வு மேட்ராய்டின் சுயாதீனமான தொகுப்பாக இருக்க வேண்டும். இந்தப் பிரச்சினையின் இரண்டு சிறப்பு நிகழ்வுகள் ஆய்வு செய்யப்பட்டுள்ளன. கர்னல் சமச்சீர்-பகிர்வு சிக்கலில், சில m முன் குறிப்பிடப்பட்ட உருப்படிகள் கர்னல்கள், மேலும் m துணைக்குழுக்கள் ஒவ்வொன்றும் ஒரு கர்னலைக் கொண்டிருக்க வேண்டும் (மற்றும் வரம்பற்ற எண்ணிக்கையிலான கர்னல்கள் அல்லாதவை). இங்கே, இரண்டு பிரிவுகள் உள்ளனஃ திறன் 1 கொண்ட கர்னல் வகை, மற்றும் வரம்பற்ற திறன் கொண்ட கர்னல் அல்லாத வகை. k = 3 க்கு கூட சிக்கல் NP-கடினமானது என்பதை சென், ஹீ மற்றும் யாவோ நிரூபிக்கின்றனர் (k = 2 க்கு அதிகபட்ச எடை பொருத்தத்தைக் கண்டுபிடிப்பதன் மூலம் அதை திறமையாக தீர்க்க முடியும்). பின்னர் அவர்கள் கர்னல்-எல்பிடி (கேஎல்பிடி) என்று அழைக்கப்படும் ஒரு வழிமுறையை முன்வைக்கிறார்கள்ஃ இது ஒவ்வொரு துணைக்குழுவிற்கும் ஒரு கர்னலை ஒதுக்குகிறது, பின்னர் மாற்றியமைக்கப்பட்ட எல்பிடி வழிமுறையை இயக்குகிறது (ஒவ்வொரு உருப்படியையும் k உருப்படிகளுக்கு குறைவாக உள்ளவற்றில் மிகச்சிறிய தொகையுடன் துணைக்குழுவில் வைக்கிறது). k = 3 உடன், KLPT குறைந்தபட்ச மிகப்பெரிய தொகைக்கு தோராயமான விகிதத்தைக் கொண்டுள்ளது என்பதை அவை நிரூபிக்கின்றன. இருப்பினும், சென், ஹீ மற்றும் லின் ஆகியோர் அதன் இறுக்கமான தோராய விகிதம் குறைந்தபட்ச மிகப்பெரிய தொகைக்கும், அதிகபட்ச மிகச்சிறிய தொகைக்கும் என்று கூறுகின்றனர். இந்த சிக்கலின் மற்றொரு மாறுபாட்டில், அளவு m இன் சில k பிரிவுகள் உள்ளன, மேலும் ஒவ்வொரு துணைக்குழுவிலும் ஒவ்வொரு வகையிலிருந்தும் சரியாக ஒரு உருப்படி இருக்க வேண்டும். அதாவது, ஒவ்வொரு வகைக்கும் கே = 1 எச். வூ மற்றும் யாவோ அடுக்கு எல்பிடி வழிமுறையை வழங்கினர்-இது எல்பிடி வழிமுறையின் ஒரு மாறுபாடு. அதன் தோராயமான விகிதம் மிகப்பெரிய தொகையைக் குறைப்பதற்கும், பொதுவான விஷயத்தில் மிகச்சிறிய தொகையை அதிகரிப்பதற்கும், சில சிறப்பு சந்தர்ப்பங்களில், பொதுவான k மற்றும் k = 3 க்கு மேம்படுத்தப்படலாம் என்பதை அவை நிரூபிக்கின்றன. லி மற்றும் லி ஒரே சிக்கலுக்கான வெவ்வேறு வழிமுறைகளை வழங்கினர். மிகப்பெரிய கூட்டுத்தொகையைக் குறைக்க, அவை மாறிலி k க்கு ஒரு EPTAS ஐ வழங்குகின்றன, மேலும் மாறிலி m க்கு FPTAS ஐ வழங்குகின்றன. சிறிய கூட்டுத்தொகையை அதிகரிக்க, அவை பொதுவான வழக்கில் 1/(k−1) தோராயமான வழிமுறையையும், மாறிலி k க்கு ஒரு EPTAS ஐ வழங்குகின்றன. அவை மிகவும் பொதுவான நோக்கத்தையும் ஆய்வு செய்கின்றனஃ தொகைகளின் திசையனின் lp-நெறிமுறையைக் குறைத்தல். அடுக்கு-எல்பிடி வழிமுறை அனைத்து விதிமுறைகளுக்கும் 2-இணக்கமான வழிமுறை என்பதை அவை நிரூபிக்கின்றன. டெல் 'ஓல்மோ, ஹான்சென், பல்லோட்டினோ மற்றும் ஸ்டோர்ச்சி ஆகியோர் இந்த சிக்கலுக்கான 32 வெவ்வேறு நோக்கங்களை ஆய்வு செய்கிறார்கள். நான்கு இயக்கிகள் ஒவ்வொன்றிற்கும் அதிகபட்சம், குறைந்தபட்சம், தொகை, வேறுபாடு, ஒவ்வொரு துணைக்குழுவிலும் உள்ள k உருப்படிகளுக்கு ஒரு ஆபரேட்டரைப் பயன்படுத்தலாம், பின்னர் வெவ்வேறு துணைக்குழுக்களுக்கான m முடிவுகளுக்கு ஒரு ஆபரேட்டரைப் பயன்படுத்தலாம். இந்த 16 குறிக்கோள்களில் ஒவ்வொன்றையும் அதிகபட்சம் அல்லது குறைக்கலாம், மொத்தம் 32. இவற்றில் 21 சிக்கல்களை நேரியல் நேரத்தில் தீர்க்க முடியும் என்பதை அவை காட்டுகின்றன; 7 க்கு மிகவும் சிக்கலான, ஆனால் இன்னும் பல்லுறுப்புக்கோவை-நேரம், வழிமுறைகள் தேவைப்படுகின்றன; 3 என்பி-கடினமானவைஃ அதிகபட்சம் (குறைந்தபட்சம், கூட்டுத்தொகை), குறைத்தல் (அதிகபட்சம், கூட்டுத்தொகை) மற்றும் குறைத்தல் (வேறுபாடு, கூட்டுத்தொகை). அவர்கள் மினிமைசிங் (வேறுபாடு, வேறுபாடு) நிலையை திறந்து விட்டனர். மெட்ராய்டு-கட்டுப்படுத்தப்பட்ட எண் பகிர்வு என்பது ஒரு பொதுமைப்படுத்தலாகும், இதில் ஒரு நிலையான மெட்ராய்டு ஒரு அளவுருவாக வழங்கப்படுகிறது, மேலும் எம் துணைக்குழுக்கள் ஒவ்வொன்றும் ஒரு சுயாதீனமான தொகுப்பாகவோ அல்லது இந்த மெட்ராய்டின் அடித்தளமாகவோ இருக்க வேண்டும். கார்டினலிட்டி கட்டுப்பாடுகள் என்பது மேட்ராய்டு கட்டுப்பாடுகளின் சிறப்பு நிகழ்வுகளாகும், இதில் மேட்ராய்டு ஒரு சீரான மேட்ராய்டு ஆகும். வகைப்படுத்தப்பட்ட கார்டினாலிட்டி கட்டுப்பாடுகள் ஒரு சிறப்பு வழக்கு, இதில் மேட்ராய்டு ஒரு பகிர்வு மேட்ராய்டு ஆகும். குறிப்புகள் எண் பகிர்வு