Balanced number partitioning
બેલેન્સ્ડ નંબર પાર્ટીશનિંગ એ મલ્ટીવે નંબર પાર્ટીશનિંગનો એક પ્રકાર છે જેમાં દરેક સમૂહને ફાળવવામાં આવેલી વસ્તુઓની સંખ્યા પર મર્યાદા હોય છે. સમસ્યાનું ઇનપુટ એ વિવિધ કદની n વસ્તુઓનો સમૂહ છે, અને બે પૂર્ણાંકો m, k. આઉટપુટ એ વસ્તુઓનું m ઉપગણમાં વિભાજન છે, જેમ કે દરેક ઉપગણમાં વસ્તુઓની સંખ્યા મહત્તમ k હોય છે. આને આધિન, તે જરૂરી છે કે m ઉપગણમાં કદનો સરવાળો શક્ય તેટલો સમાન હોય. એક ઉદાહરણ એપ્લિકેશન સમાન-મશીનનું સમયપત્રક છે જ્યાં દરેક મશીનમાં જોબ-ક્યુ હોય છે જે મહત્તમ k નોકરીઓ રાખી શકે છે. આ સમસ્યાનો ઉપયોગ વીએલએસઆઈ ચિપ્સના ઉત્પાદનમાં અને લવચીક ઉત્પાદન પ્રણાલીઓમાં મશીનોને સાધનો સોંપવામાં પણ થાય છે. શ્રેષ્ઠ જોબ શેડ્યુલિંગ સમસ્યાઓ માટે પ્રમાણભૂત ત્રણ-ક્ષેત્ર સંકેતલિપીમાં, સૌથી મોટી રકમને ઘટાડવાની સમસ્યાને કેટલીકવાર "P | #≤ k | Cmax" દ્વારા સૂચવવામાં આવે છે. મધ્ય ક્ષેત્ર "#≤ k" સૂચવે છે કે દરેક મશીનમાં નોકરીઓની સંખ્યા મહત્તમ k હોવી જોઈએ. આ અનિયંત્રિત સંસ્કરણથી વિપરીત છે, જેને "" દ્વારા સૂચવવામાં આવે છે. દ્વિ-માર્ગીય સંતુલિત પાર્ટીશનિંગ એક સામાન્ય વિશેષ કેસ જેને દ્વિ-માર્ગીય સંતુલિત પાર્ટીશનિંગ કહેવાય છે તે છે જ્યારે બે સબસેટ (m = 2) હોવા જોઈએ. બે ઉપગણમાં માળ (એન/2) અને છત (એન/2) વસ્તુઓ હોવી જોઈએ. તે પાર્ટીશન સમસ્યાનો એક પ્રકાર છે. તે નક્કી કરવું એન. પી.-મુશ્કેલ છે કે ત્યાં કોઈ પાર્ટીશન અસ્તિત્વમાં છે કે જેમાં બે સબસેટ્સમાં સરવાળો સમાન છે; સમસ્યા [એસ. પી. 12] જુઓ. એવા ઘણા અલ્ગોરિધમ્સ છે જે સંતુલિત પાર્ટીશન શોધવાનું લક્ષ્ય રાખે છે જેમાં સરવાળો શક્ય તેટલો લગભગ સમાન હોય. કોફમેન, ફ્રેડરિકસન અને લ્યુકર એલ. પી. ટી. અલ્ગોરિધમ (જેને આર. એલ. પી. ટી. કહેવાય છે) નું પ્રતિબંધિત સંસ્કરણ રજૂ કરે છે, જેમાં ઇનપુટ્સ જોડીમાં સોંપવામાં આવે છે. જ્યારે ઇનપુટ્સ સમાનરૂપે વિતરિત રેન્ડમ વેરિયેબલ્સ હોય છે, ત્યારે આરએલપીટીનો અપેક્ષિત સૌથી મોટો સરવાળો બરાબર છે. અપેક્ષિત કાર્ય-તફાવત (સૌથી મોટી અને સૌથી નાની રકમ વચ્ચેનો તફાવત) છે. લ્યુકર એલ. ડી. એમ. અલ્ગોરિધમનો એક પ્રકાર રજૂ કરે છે (જેને જોડી મુજબની ભિન્નતા પદ્ધતિ (પી. ડી. એમ.) કહેવાય છે). તેના અપેક્ષિત કાર્ય-તફાવત છે. ત્સાઈ પ્રતિબંધિત સૌથી મોટો તફાવત (આરએલડી) નામના અલ્ગોરિધમનો રજૂ કરે છે. તેના કામનો તફાવત લગભગ નિશ્ચિત છે. યાકિર એમ = 2 માટે એલડીએમ અલ્ગોરિધમનો સંતુલિત પ્રકાર રજૂ કરે છે, જેને બીએલડીએમ કહેવાય છે. તેના અપેક્ષિત કાર્ય-તફાવત છે. મર્ટન્સ સંતુલિત દ્વિ-માર્ગીય પાર્ટીશનિંગ માટે કોઈપણ સમયે સંપૂર્ણ અલ્ગોરિધમ રજૂ કરે છે. તે બી. એલ. ડી. એમ. અલ્ગોરિધમને સંપૂર્ણ-કર્મકાર-કાર્પ અલ્ગોરિધમ સાથે જોડે છે. 3-પાર્ટીશનિંગ તરીકે ઓળખાતો બીજો ખાસ કેસ એ છે કે જ્યારે દરેક સબસેટમાં વસ્તુઓની સંખ્યા મહત્તમ 3 (k = 3) હોવી જોઈએ. સમાન રકમ સાથે આવા પાર્ટીશન અસ્તિત્વમાં છે કે કેમ તે નક્કી કરવું એ બરાબર 3-પાર્ટીશન સમસ્યા છે, જે મજબૂત રીતે એન. પી.-હાર્ડ તરીકે ઓળખાય છે. ત્યાં અંદાજિત અલ્ગોરિધમ્સ છે જે એક પાર્ટીશન શોધવાનું લક્ષ્ય રાખે છે જેમાં સરવાળો શક્ય તેટલો લગભગ સમાન હોય. કેલર અને વોઇજિંગર એલ. પી. ટી. અલ્ગોરિધમને ત્રિપલ પાર્ટીશનિંગમાં અનુકૂલિત કરે છે (જ્યાં મહત્તમ 3 * મીટર વસ્તુઓ હોય છે, અને દરેક સબસેટમાં મહત્તમ 3 વસ્તુઓ હોવી જોઈએ). તેમના અલ્ગોરિધમને મોડિફાઇડ-એલપીટી અથવા એમએલપીટી કહેવામાં આવે છે. તે મોટીથી નાની વસ્તુઓનો ઓર્ડર આપે છે, અને દરેક વસ્તુને 3 થી ઓછી વસ્તુઓ ધરાવતા ડબ્બામાં સૌથી નાની રકમ સાથે ડબ્બામાં મૂકે છે. તેઓ દર્શાવે છે કે એમ. એલ. પી. ટી. અલ્ગોરિધમ મોટાભાગની લઘુત્તમ સૌથી મોટી રકમ પ્રાપ્ત કરે છે, જે એ જ અંદાજ ગુણોત્તર છે જે એલ. પી. ટી. અનિયંત્રિત સમસ્યા માટે પ્રાપ્ત કરે છે. એમ. એલ. પી. ટી. માટે બાઉન્ડ ચુસ્ત છે. ચેન, હી અને લિન દર્શાવે છે કે, સમાન સમસ્યા માટે, એમ. એલ. પી. ટી. ઓછામાં ઓછી મહત્તમ સૌથી નાની રકમ પ્રાપ્ત કરે છે, જે ફરીથી તે જ ગુણોત્તર છે જે એલ. પી. ટી. અનિયંત્રિત સમસ્યા માટે પ્રાપ્ત કરે છે. કેલર અને કોટોવ એક અલગ અલ્ગોરિધમ રજૂ કરે છે (બરાબર 3 * મીટર વસ્તુઓ સાથેના કેસ માટે), જે મોટાભાગની લઘુત્તમ સૌથી મોટી રકમ પ્રાપ્ત કરે છે. વધુ સામાન્ય કેસ, કે-પાર્ટીશનિંગ કહેવાય છે, જ્યારે દરેક સબસેટમાં વસ્તુઓની સંખ્યા મહત્તમ 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 પરિણામો નીચલા બાઉન્ડને અનુરૂપ છે. કે> 7 માટે, કોઈ ચોક્કસ પરિણામો જાણીતા નથી, પરંતુ નીચલા અને ઉપલા બાઉન્ડ વચ્ચેનો તફાવત 0.3 ટકાથી ઓછો છે. જ્યારે પરિમાણ ઉપગણની સંખ્યા (m) હોય, ત્યારે અંદાજ ગુણોત્તર બરાબર હોય છે. ઝાંગ, મૌરાતિડીસ અને પેંગ દર્શાવે છે કે બી. એલ. ડી. એમ. ઉચ્ચ કાર્ય-તફાવત (સૌથી વધુ અને સૌથી ઓછી રકમ વચ્ચેનો તફાવત) સાથે પાર્ટીશન આપી શકે છે, બંને જ્યારે ઇનપુટ્સ સમાન રીતે વહેંચવામાં આવે છે, અને જ્યારે તેમનું વિતરણ વક્ર હોય છે. તેઓ બે વૈકલ્પિક સંશોધનોની દરખાસ્ત કરે છેઃ જ્યારે વિતરણ એકસમાન હોય ત્યારે એલ. આર. એમ. બી. એલ. ડી. એમ. ના કાર્ય-તફાવતને ઘટાડીને 1/3 કરે છે; જ્યારે વિતરણ વક્ર હોય ત્યારે મેલ્ડ કાર્ય-તફાવત ઘટાડે છે. એક વર્ણસંકર અલ્ગોરિધમ બી. એલ. ડી. એમ., એલ. આર. એમ. અને મેલ્ડને જોડે છે અને વિવિધ ડેટા વિતરણ માટે ગતિશીલ રીતે સ્વીકારે છે. જ્યારે k નિશ્ચિત હોય, ત્યારે સંતુલિત પાર્ટીશનિંગ માટે હોચબૌમ અને સ્મોઇસના પી. ટી. એ. એસ. નો ઉપયોગ કરી શકાય છે. જ્યારે k એ ઇનપુટનો ભાગ હોય, ત્યારે હાલમાં કોઈ PTAS જાણીતું નથી. ડેલ 'એમિકો અને માર્ટેલો જ્યારે તમામ સેટમાં વસ્તુઓની સંખ્યા મહત્તમ k હોય ત્યારે સૌથી મોટી રકમ ઘટાડવાની સમસ્યાનો અભ્યાસ કરે છે. તેઓ દર્શાવે છે કે આ વેરિઅન્ટની રેખીય-પ્રોગ્રામ છૂટછાટ અનિયંત્રિત વેરિઅન્ટની LP છૂટછાટ જેટલું જ શ્રેષ્ઠ મૂલ્ય ધરાવે છે. અભિવ્યક્તિ, જ્યાં xi એ મોટાથી નાના ક્રમના ઇનપુટ્સ છે, તે શ્રેષ્ઠ સૌથી મોટી રકમ માટે નીચલી સીમા છે, અને તેનો સૌથી ખરાબ કેસ રેશિયો બંને પ્રકારોમાં 1/2 છે. સુધારેલ અભિવ્યક્તિમાં સૌથી ખરાબ કેસ રેશિયો અનિયંત્રિત સ્વરૂપમાં 2/3 અને મર્યાદિત સ્વરૂપમાં 1/2 છે. અનિયંત્રિત પ્રકાર માટે સંશોધિત સૂચિ સમયપત્રકનો અંદાજ ગુણોત્તર 1/2 છે, પરંતુ મર્યાદિત પ્રકાર માટે તે 0 છે (તે મનસ્વી રીતે ખરાબ હોઈ શકે છે). સુધારેલા એલ. પી. ટી. અલ્ગોરિધમનો અંદાજ ગુણોત્તર મહત્તમ 2 છે. તેઓ એ પણ દર્શાવે છે કે નીચલા બાઉન્ડનો સૌથી ખરાબ કેસ પરફોર્મન્સ રેશિયો 3/4 છે, અને તેમના PD અલ્ગોરિધમનો ચુસ્ત પરફોર્મન્સ રેશિયો 4/3 છે (જ્યારે m પૂરતા પ્રમાણમાં મોટો હોય છે). તે, તાન, ઝુ અને યાઓ સૌથી નાની રકમને મહત્તમ કરવાની સમસ્યાને ધ્યાનમાં લે છે. તેઓ દર્શાવે છે કે ફોલ્ડિંગ અલ્ગોરિધમનો અંદાજ ગુણોત્તર ચુસ્ત છે. તેઓ ઓછામાં ઓછા સૌથી ખરાબ-કેસ ગુણોત્તર સાથે એક નવું અલ્ગોરિધમ, હાર્મોનિક 1 રજૂ કરે છે. આ બંને અલ્ગોરિધમ્સ ક્રમિક છે-તેઓ વસ્તુઓને તેમના ચોક્કસ મૂલ્યોને બદલે તેમની વચ્ચેના ક્રમના આધારે વિભાજિત કરે છે. તેઓ સાબિત કરે છે કે કોઈપણ ક્રમિક અલ્ગોરિધમનો સૌથી નાનો સરવાળો વધારવા માટે મહત્તમ ગુણોત્તર ધરાવે છે. આ સૂચવે છે કે હાર્મોનિક 1 એસિમ્પ્ટોટિક રીતે શ્રેષ્ઠ છે. કોઈપણ નિશ્ચિત k માટે, કોઈપણ ક્રમિક અલ્ગોરિધમનો ગુણોત્તર સમીકરણના સૌથી નાના મૂળમાં હોય છે. જ્યારે k અનંત તરફ વલણ ધરાવે છે, ત્યારે આ ઉપલી સીમા 0 સુધી પહોંચે છે. સંતુલિત અને અનિયંત્રિત સમસ્યાઓ વચ્ચેના સંબંધો સંતુલિત પાર્ટીશન સમસ્યા અને પ્રમાણભૂત (અનિયંત્રિત) પાર્ટીશન સમસ્યાના અંદાજો વચ્ચે કેટલાક સામાન્ય સંબંધો છે. બેબલ, કેલરર અને કોટોવ સાબિત કરે છે કે અનિયંત્રિત મહત્તમ અને મર્યાદિત મહત્તમ વચ્ચેનો ગુણોત્તર સૌથી વધુ છે, અને તે ચુસ્ત છે. કેલર અને કોટોવ સાબિત કરે છે કે ક્ષમતા k અને અંદાજ-ગુણોત્તર r (લઘુત્તમ સૌથી મોટી રકમ માટે) સાથે સંતુલિત પાર્ટીશનિંગ માટેના દરેક સંશોધનાત્મકનો ઉપયોગ અંદાજ-ગુણોત્તર સાથે અનિયંત્રિત પાર્ટીશનિંગ માટે સંશોધનાત્મક મેળવવા માટે કરી શકાય છે. ખાસ કરીને, ત્રિપલ પાર્ટીશનિંગ (k = 3) માટે તેમના-એપ્રોક્સિમેશન અલ્ગોરિધમનો ઉપયોગ અંદાજ-ગુણોત્તર સાથે અનિયંત્રિત પાર્ટીશનિંગ માટે હ્યુરિસ્ટિક મેળવવા માટે થઈ શકે છે. કાર્ડિનાલિટીની વિવિધ મર્યાદાઓ કાર્ડિનાલિટીની મર્યાદાઓને દરેક સબસેટ પર અલગ અવરોધને મંજૂરી આપીને સામાન્ય કરી શકાય છે. આ પ્રકાર "ખુલ્લી સમસ્યાઓ" વિભાગમાં રજૂ કરવામાં આવ્યો છે, જે કી-પાર્ટીશનિંગ સમસ્યાને કહે છે. તે, ટેન, ઝુ અને યાઓ વિવિધ કાર્ડિનાલિટી મર્યાદાઓ સાથે સૌથી નાના સરવાળાને મહત્તમ કરવા માટે હાર્મોનિક 2 નામનું અલ્ગોરિધમ રજૂ કરે છે. તેઓ સાબિત કરે છે કે તેનો સૌથી ખરાબ કેસ રેશિયો ઓછામાં ઓછો છે. વર્ગીકૃત કાર્ડિનાલિટી મર્યાદાઓ કાર્ડિનાલિટી મર્યાદાઓનું બીજું સામાન્યીકરણ નીચે મુજબ છે. ઇનપુટ વસ્તુઓને k શ્રેણીઓમાં વિભાજિત કરવામાં આવે છે. દરેક શ્રેણી એચ માટે, ક્ષમતાની મર્યાદા કેએચ છે. દરેક એમ ઉપગણમાં એચ શ્રેણીમાંથી મહત્તમ કેએચ વસ્તુઓ હોઈ શકે છે. બીજા શબ્દોમાં કહીએ તોઃ બધા એમ ઉપગણ ચોક્કસ પાર્ટીશન મેટ્રોઇડનો સ્વતંત્ર સમૂહ હોવો જોઈએ. આ સમસ્યાના બે વિશેષ કેસોનો અભ્યાસ કરવામાં આવ્યો છે. કર્નલ સંતુલિત-વિભાજન સમસ્યામાં, કેટલીક m પૂર્વ-નિર્દિષ્ટ વસ્તુઓ કર્નલ હોય છે, અને દરેક m ઉપગણમાં એક જ કર્નલ (અને અમર્યાદિત સંખ્યામાં બિન-કર્નલ) હોવો આવશ્યક છે. અહીં, બે શ્રેણીઓ છેઃ ક્ષમતા 1 સાથે કર્નલ શ્રેણી, અને અમર્યાદિત ક્ષમતા સાથે નોન-કર્નલ શ્રેણી. ચેન, હી અને યાઓ સાબિત કરે છે કે k = 3 માટે પણ સમસ્યા NP-સખત છે (k = 2 માટે તે મહત્તમ વજન મેળ શોધીને અસરકારક રીતે ઉકેલી શકાય છે). ત્યારબાદ તેઓ કર્નલ-એલ. પી. ટી. (કે. એલ. પી. ટી.) નામનું એક અલ્ગોરિધમ રજૂ કરે છેઃ તે દરેક સબસેટને કર્નલ સોંપે છે, અને પછી સંશોધિત એલ. પી. ટી. અલ્ગોરિધમ ચલાવે છે (દરેક વસ્તુને સબસેટમાં સૌથી નાના સરવાળા સાથે મૂકે છે, જેમાં કે કરતા ઓછી વસ્તુઓ હોય છે). તેઓ સાબિત કરે છે કે, 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 એન. પી.-હાર્ડ છેઃ મહત્તમ (લઘુત્તમ, સરવાળો), લઘુત્તમ (મહત્તમ, સરવાળો) અને લઘુત્તમ (તફાવત, સરવાળો). તેઓએ મિનિમાઇઝિંગ (ડિફ, ડિફ) ની સ્થિતિ ખુલ્લી રાખી. મેટ્રોઇડ-મર્યાદિત સંખ્યા પાર્ટીશનિંગ એ એક સામાન્યીકરણ છે જેમાં નિશ્ચિત મેટ્રોઇડને પરિમાણ તરીકે આપવામાં આવે છે, અને દરેક એમ સબસેટ આ મેટ્રોઇડનો સ્વતંત્ર સમૂહ અથવા આધાર હોવો જોઈએ. કાર્ડિનાલિટી અવરોધો એ મેટ્રોઇડ અવરોધોના વિશેષ કિસ્સાઓ છે જેમાં મેટ્રોઇડ એક સમાન મેટ્રોઇડ છે. વર્ગીકૃત કાર્ડિનાલિટી અવરોધો એ એક વિશેષ કેસ છે જેમાં મેટ્રોઇડ એ પાર્ટીશન મેટ્રોઇડ છે. સંદર્ભ સંખ્યા પાર્ટીશનિંગ