Matroid-constrained number partitioning
મેટ્રોઇડ-મર્યાદિત નંબર પાર્ટીશનિંગ એ મલ્ટીવે નંબર પાર્ટીશનિંગ સમસ્યાનો એક પ્રકાર છે, જેમાં પાર્ટીશનમાંના સબસેટ્સ મેટ્રોઇડના સ્વતંત્ર સેટ હોવા જોઈએ. આ સમસ્યાનું ઇનપુટ વસ્તુઓનો સમૂહ S, હકારાત્મક પૂર્ણાંક m, અને સમાન સમૂહ S પર કેટલાક m મેટ્રોઇડ્સ છે. ધ્યેય S ને m સબસેટ્સમાં વિભાજિત કરવાનો છે, જેમ કે દરેક સબસેટ i એ મેટ્રોઇડ i માં સ્વતંત્ર સમૂહ છે. આ અવરોધને આધિન, કેટલાક ઉદ્દેશ્ય કાર્યને ઘટાડવું જોઈએ, ઉદાહરણ તરીકે, સબસેટમાં સૌથી મોટી વસ્તુના કદને ઘટાડવું. વધુ સામાન્ય સ્વરૂપમાં, દરેક m મેટ્રોઇડ્સમાં વજનનું કાર્ય હોય છે, જે ગ્રાઉન્ડ-સેટના દરેક તત્વને વજન સોંપે છે. વિવિધ ઉદ્દેશ્ય કાર્યો પર વિચાર કરવામાં આવ્યો છે. ત્રણ ઓપરેટરોમાંથી દરેક માટે મહત્તમ, લઘુત્તમ, સરવાળો, દરેક ઉપગણમાં વસ્તુઓના વજન પર અને ઉપગણ પર પોતે આ ઓપરેટરનો ઉપયોગ કરી શકે છે. એકંદરે, ત્યાં 9 સંભવિત ઉદ્દેશ્ય કાર્યો છે, જેમાંથી દરેકને મહત્તમ અથવા ન્યૂનતમ કરી શકાય છે. વિશેષ કિસ્સાઓ મેટ્રોઇડ-અવરોધિત પાર્ટીશનિંગ સમસ્યાઓના કેટલાક મહત્વપૂર્ણ વિશેષ કિસ્સાઓ આ પ્રમાણે છેઃ (મહત્તમ, સરવાળો) ઉદ્દેશ એ તમામ ઉપગણ પર, ઉપગણમાં કુલ વજનનો મહત્તમ છે. જ્યારે વસ્તુઓ નોકરીઓનું પ્રતિનિધિત્વ કરે છે અને વજન તેમની લંબાઈનું પ્રતિનિધિત્વ કરે છે, ત્યારે આ ઉદ્દેશ ફક્ત સમયપત્રકનો મેકસ્પેન છે. તેથી, આ ઉદ્દેશને ઓછો કરવો એ મેટ્રોઇડ અવરોધો હેઠળ મેકસ્પેનને ઘટાડવાની સમકક્ષ છે. મહત્તમ (લઘુત્તમ, સરવાળો) ના બેવડા ધ્યેયનો પણ આ સંદર્ભમાં અભ્યાસ કરવામાં આવ્યો છે. ખાસ કેસ જેમાં મેટ્રોઇડ્સ મુક્ત મેટ્રોઇડ્સ છે (કોઈ અવરોધો નથી) અને એમ વજન-કાર્યો સમાન છે તે સમાન-મશીનોના સમયપત્રકને અનુરૂપ છે, જેને મલ્ટીવે નંબર પાર્ટીશનિંગ તરીકે પણ ઓળખવામાં આવે છે. મુક્ત મેટ્રોઇડ્સ અને વિવિધ વજન-કાર્યોનો કેસ અસંબંધિત-મશીનોના સમયપત્રકને અનુરૂપ છે. સમાન મેટ્રોઇડ્સનો વિશેષ કેસ ઉપગણ પર કાર્ડિનાલિટી અવરોધોને અનુરૂપ છે. પાર્ટીશન મેટ્રોઇડ્સનો વધુ સામાન્ય કેસ વર્ગીકૃત કાર્ડિનાલિટી અવરોધોને અનુરૂપ છે. આ સમસ્યાઓ સંતુલિત સંખ્યા પાર્ટીશનિંગ પરના પૃષ્ઠમાં વર્ણવવામાં આવી છે. (સરવાળો, સરવાળો) ઉદ્દેશ એ તમામ ઉપગણમાં તમામ વસ્તુઓના વજનનો સરવાળો છે, જ્યાં દરેક ઉપગણમાં વજનની ગણતરી મેટ્રોઇડ i ના વજન-કાર્ય દ્વારા કરવામાં આવે છે. આ ઉદ્દેશને ઘટાડીને ભારિત મેટ્રોઇડ આંતરછેદ સમસ્યામાં ઘટાડી શકાય છે-મહત્તમ વજનનો સબસેટ શોધવો જે આપેલ બે મેટ્રોઇડ્સમાં એક સાથે સ્વતંત્ર છે. આ સમસ્યા બહુપદી સમયમાં ઉકેલી શકાય છે. (મહત્તમ, મહત્તમ) ઉદ્દેશ એ તમામ સબસેટ્સમાં મહત્તમ વજન છે, જ્યાં દરેક સબસેટ i માં વજનની ગણતરી મેટ્રોઇડ i ના વજન-કાર્ય દ્વારા કરવામાં આવે છે. ગ્રાફિક મેટ્રોઇડ્સ સાથે આ ઉદ્દેશને ઓછો કરવાનો ઉપયોગ વૃક્ષની સમસ્યાને ઉકેલવા માટે કરી શકાય છે. (સરવાળો, લઘુતમ) ઉદ્દેશ એ તમામ ઉપગણમાં લઘુતમ વજનનો સરવાળો છે. આ ઉદ્દેશને મહત્તમ બનાવવો, k સમાન ગ્રાફિકલ મેટ્રોઇડ્સ સાથે, વૃક્ષ વિભાજન સમસ્યામાં ફેલાયેલી મહત્તમ કુલ ક્ષમતાને ઉકેલવા માટે વાપરી શકાય છે. (સરવાળો, મહત્તમ) ઉદ્દેશ એ તમામ ઉપગણમાં મહત્તમ વજનનો સરવાળો છે. આ ઉદ્દેશ સુનિશ્ચિત કરવા માટે જરૂરી કુલ મેમરીનું પ્રતિનિધિત્વ કરી શકે છે, જ્યારે દરેક મેટ્રોઇડ i મશીન i માં શક્ય ફાળવણીનું પ્રતિનિધિત્વ કરે છે. સામાન્ય મેટ્રોઇડ અવરોધો સામાન્ય મેટ્રોઇડ અવરોધોને સૌપ્રથમ બર્કાર્ડ અને યાઓ દ્વારા ધ્યાનમાં લેવામાં આવ્યા હતા. તેઓએ બતાવ્યું કે મેટ્રોઇડ્સના પેટા વર્ગ માટે લોભી અલ્ગોરિધમ દ્વારા બહુપદી સમયમાં લઘુત્તમ (સરવાળો, મહત્તમ) કરી શકાય છે, જેમાં પાર્ટીશન મેટ્રોઇડ્સનો સમાવેશ થાય છે. હ્વાંગ અને રોથબ્લમે વૈકલ્પિક પર્યાપ્ત શરત રજૂ કરી. વુ અને યાઓએ સામાન્ય મેટ્રોઇડ અવરોધો સાથે લઘુત્તમ (મહત્તમ, સરવાળો) માટે અંદાજિત અલ્ગોરિધમ રજૂ કર્યું. અબ્બાસી, મિરોકની અને ઠાકુર મેટ્રોઇડ અવરોધો હેઠળ વિવિધતા મહત્તમકરણની સમસ્યા માટે અંદાજિત અલ્ગોરિધમ રજૂ કરે છે. કાવાસે, કિમુરા, માકિનો અને સુમિતા દર્શાવે છે કે મહત્તમકરણની સમસ્યાઓને ઘટાડીને લઘુતમ સમસ્યાઓ કરી શકાય છે. પછી, તેઓ સાત લઘુતમ સમસ્યાઓનું વિશ્લેષણ કરે છેઃ લઘુતમ (સરવાળો, મહત્તમ): જ્યારે મેટ્રોઇડ અને વજન સમાન હોય ત્યારે પણ સમસ્યા મજબૂત રીતે એન. પી.-સખત હોય છે. સમાન મેટ્રોઇડ અને વજન માટે પી. ટી. એ. એસ. છે. સામાન્ય મેટ્રોઇડ્સ અને વજન માટે, કોઈપણ ε> 0 માટે εm-એપ્રોક્સિમેશન અલ્ગોરિધમ છે. તે પરિબળ ઓ (લોગ એમ) સાથે અંદાજિત કરવા માટે એન. પી.-મુશ્કેલ છે. લઘુત્તમ (લઘુતમ, લઘુતમ), (મહત્તમ, મહત્તમ), (લઘુતમ, મહત્તમ) અને (લઘુતમ, સરવાળો): બહુપદી-સમયના અલ્ગોરિધમ્સ છે. તેઓ સમસ્યાઓને મેટ્રોઇડ પાર્ટીશનિંગ સમસ્યાની શક્યતા સમસ્યામાં ઘટાડે છે. લઘુતમ (મહત્તમ, લઘુતમ) અને (સરવાળો, લઘુતમ): સમાન મેટ્રોઇડ અને વજન માટે બહુપદી-સમયના અલ્ગોરિધમ્સ છે. સામાન્ય કિસ્સામાં, તે અંદાજિત હોવા છતાં પણ મજબૂત રીતે એન. પી.-હાર્ડ હોય છે. અગાઉના કાર્યોમાં અન્ય બે સમસ્યાઓનું વિશ્લેષણ કરવામાં આવ્યું હતુંઃ લઘુત્તમ (મહત્તમ, સરવાળો) ને મજબૂત રીતે એન. પી.-હાર્ડ (3-વિભાજન એક વિશેષ કેસ છે) તરીકે ઓળખવામાં આવે છે, અને લઘુત્તમ (સરવાળો, સરવાળો) ને ભારિત મેટ્રોઇડ આંતરછેદમાં ઘટાડી શકાય છે, જે બહુપદી છે. સંબંધિત સમસ્યાઓ મેટ્રોઇડ પાર્ટીશનિંગ એક અલગ સમસ્યા છે, જેમાં ભાગોની સંખ્યા m નિશ્ચિત નથી. એક જ મેટ્રોઇડ છે, અને તેનો ધ્યેય તેના તત્વોને સ્વતંત્ર સમૂહોની સૌથી નાની સંખ્યામાં વિભાજિત કરવાનો છે. સંદર્ભો મેટ્રોઇડ સિદ્ધાંત નંબર પાર્ટીશનિંગ