High-multiplicity bin packing
உயர் பெருக்கம் தொட்டி பொதி செய்வது தொட்டி பொதி சிக்கலின் ஒரு சிறப்பு வழக்கு, இதில் வெவ்வேறு பொருள்-அளவுகளின் எண்ணிக்கை சிறியது, அதே நேரத்தில் ஒவ்வொரு அளவையும் கொண்ட பொருட்களின் எண்ணிக்கை பெரியது. பொதுவான பின்-பேக்கிங் சிக்கல் NP-கடினமாக இருக்கும்போது, வெவ்வேறு அளவுகளின் எண்ணிக்கை ஒரு நிலையான மாறிலி என்று கருதி, உயர் பெருக்கம் அமைப்பை பல்லுறுப்புக்கோவை நேரத்தில் தீர்க்க முடியும். சிக்கல் வரையறை சிக்கலுக்கான உள்ளீடுகள் நேர்மறை முழு எண்கள்ஃ d-வெவ்வேறு அளவுகளின் எண்ணிக்கை (சிக்கலின் பரிமாணம் என்றும் அழைக்கப்படுகிறது); B-தொட்டி திறன். s1,., sd-அளவுகள். அளவுகளின் திசையன் s. n1,., nd ஆல் குறிக்கப்படுகிறது-பெருக்கங்கள்; ni என்பது அளவு si கொண்ட உருப்படிகளின் எண்ணிக்கை. பெருக்கங்களின் திசையன் n ஆல் குறிக்கப்படுகிறது. n என்பது மொத்த உருப்படிகளின் எண்ணிக்கையைக் குறிக்கிறது, அதாவது, n = n1 +. + nd. V என்பது சிக்கலின் விளக்கத்தில் தோன்றும் மிகப்பெரிய முழு எண்ணைக் குறிக்கிறது, அதாவது, V = அதிகபட்சம் (s1,., sd, n1,., nd, B) வெளியீடு ஒரு பொதி ஆகும்-ஒவ்வொரு தொட்டியிலும் உள்ள பொருட்களின் மொத்த அளவு அதிகபட்சம் B ஆக இருக்கும் வகையில் தொட்டிகளுக்கு உருப்படிகளை ஒதுக்குவது, இதற்கு உட்பட்டு, தொட்டிகளின் எண்ணிக்கை முடிந்தவரை சிறியதாக இருக்கும். எடுத்துக்காட்டுஃ d = 2, s1 = 30, s2 = 40, n1 = n2 = 5, B = 120 என்று வைத்துக்கொள்வோம். எனவே அளவுகளுடன் n = 10 உருப்படிகள் உள்ளனஃ 30,30,30,30,30,40,40,40,40,40. பின்னர், ஒரு சாத்தியமான பேக்கிங்ஃ {30,30,30,30}, {40,40,40}, {30,40,40}, இது 3 தொட்டிகளைப் பயன்படுத்துகிறது. உள்ளமைவுகள் ஒரு உள்ளமைவு என்பது ஒரு தொட்டியில் பொருந்தக்கூடிய பொருட்களின் தொகுப்பாகும். இது டி முழு எண்களின் திசையன் மூலம் குறிப்பிடப்படலாம், இது உள்ளமைவில் உள்ள வெவ்வேறு அளவுகளின் பெருக்கங்களைக் குறிக்கிறது. முறைப்படி, ஒவ்வொரு உள்ளமைவுக்கும் c நாம் ஒரு முழு எண் திசையன் ac = ac, 1,., ac, d ஐ வரையறுக்கிறோம், அதாவது ac ≤ n மற்றும் ac·s ≤ B. மேலே உள்ள எடுத்துக்காட்டில், உள்ளமைவுகளில் ஒன்று c = {30,40,40}, ஏனெனில் 1 * 30+2 * 40 ≤120. இதனுடன் தொடர்புடைய திசையன் ஏசி = (1,2) ஆகும். பிற அமைப்பு திசையன்கள் (4,0), (3,0), (2,0), (2,1), (1,0), (1,1), (1,2), (0,1), (0,2), (0,3) ஆகும். எங்களிடம் அளவு 3 இன் மூன்று உருப்படிகள் மட்டுமே இருந்தால், (4,0) உள்ளமைவைப் பயன்படுத்த முடியாது. உள்ளமைவு நேரியல் நிரலைப் பயன்படுத்தி சிக்கலை முன்வைக்க முடியும்ஃ ஒவ்வொரு உள்ளமைவுக்கும் c, ஒரு மாறி xc உள்ளது, இது c பயன்படுத்தப்படும் தொட்டிகளின் எண்ணிக்கையைக் குறிக்கிறது. பயன்படுத்தப்படும் தொட்டிகளின் மொத்த எண்ணிக்கை அனைத்து உள்ளமைவுகளுக்கும் xc இன் கூட்டுத்தொகையாகும், இது 1·x ஆல் குறிக்கப்படுகிறது. ஒவ்வொரு அளவிலிருந்தும் பயன்படுத்தப்படும் உருப்படிகளின் மொத்த எண்ணிக்கை அனைத்து உள்ளமைவுகளிலும் உள்ள திசையன்களின் கூட்டுத்தொகையாகும் c. பின்னர், சிக்கல் 1·x ஐக் குறைப்பதாகும், அதாவது அனைத்து உள்ளமைவுகளிலும் c இன் கூட்டுத்தொகை குறைந்தது n ஆக இருக்கும், இதனால் அனைத்து உருப்படிகளும் நிரம்பியிருக்கும். வழிமுறைகள் அடிப்படை வழிமுறைகள் முதலில் அனைத்து உருப்படிகளும் பெரியவை என்று வைத்துக்கொள்வோம், அதாவது, ஒவ்வொரு si குறைந்தபட்சம் சில பின்னங்களுக்கு e·B ஆகும். பின்னர், ஒவ்வொரு தொட்டியிலும் உள்ள மொத்த உருப்படிகளின் எண்ணிக்கை அதிகபட்சம் 1/e ஆகும், எனவே மொத்த உள்ளமைவின் எண்ணிக்கை அதிகபட்சம் d1/e ஆகும். ஒவ்வொரு உள்ளமைவும் அதிகபட்சமாக n நேரங்களில் தோன்றும். எனவே, சரிபார்க்க பெரும்பாலான சேர்க்கைகள் உள்ளன. ஒவ்வொரு கலவையிலும், நாம் d கட்டுப்பாடுகளை சரிபார்க்க வேண்டும் (ஒவ்வொரு அளவிற்கும் ஒன்று), எனவே ரன்-டைம், இது n இல் பல்லுறுப்புக்கோவை, d, e நிலையானதாக இருக்கும்போது. இந்த வழிமுறையின் முக்கிய சிக்கல் (உருப்படிகள் பெரியதாக இருக்கும்போது மட்டுமே இது செயல்படுகிறது என்ற உண்மையைத் தவிர) அதன் இயக்க நேரம் n இல் பல்லுறுப்புக்கோவை, ஆனால் உள்ளீட்டின் நீளம் (பைனரி பிரதிநிதித்துவத்தில்) பதிவு (V) இல் நேரியல் ஆகும், இது பதிவு (n) இன் அளவின் வரிசையில் உள்ளது. உள்ளீட்டு அளவு ஃபிலிப்பி மற்றும் அக்னெட்டிஸில் உள்ள ரன்-டைம் பல்லுறுப்புக்கோவை ஒரு வழிமுறையை வழங்கியது, இது O (பாலி (லாக் V)) நேரத்தில் அதிகபட்சமாக OPT + d-2 தொட்டிகளுடன் ஒரு தீர்வை கண்டுபிடிக்கும். குறிப்பாக, d = 2 வெவ்வேறு அளவுகளுக்கு, அவற்றின் வழிமுறை O (log V) நேரத்தில் உகந்த தீர்வைக் காண்கிறது. கோமேன்ஸ் மற்றும் ரோத்வாஸ் ஆகியோர் எந்தவொரு நிலையான டி-க்கும் ஒரு வழிமுறையை வழங்கினர், இது அனைத்து எண்களும் பைனரி குறியீட்டில் கொடுக்கப்படும்போது உகந்த தீர்வைக் காண்கிறது. அவற்றின் வழிமுறை பின்வரும் சிக்கலைத் தீர்க்கிறதுஃ P மற்றும் Q ஆகிய இரண்டு d-பரிமாண பாலிட்டோப்புகளைக் கொடுத்தால், P இல் உள்ள குறைந்தபட்ச முழு எண் புள்ளிகளைக் கண்டறியவும், அதன் கூட்டுத்தொகை Q இல் உள்ளது. அவற்றின் வழிமுறை சரியான நேரத்தில் இயங்குகிறது. ஒரே மாதிரியான இயந்திரங்களை திட்டமிடுதல் மற்றும் தொடர்பில்லாத இயந்திரங்களை பல்வேறு கட்டுப்பாடுகளுடன் திட்டமிடுதல் போன்ற பிற சிக்கல்களுக்கு அவற்றின் வழிமுறையை மாற்றியமைக்கலாம். ஒரு பொதுவான நிகழ்வை உயர்-பெருக்கல் நிகழ்வுக்கு வட்டமிடுவது பொதுவான தொட்டி-பொதி சிக்கலுக்கான பல தோராயமான வழிமுறைகள் பின்வரும் திட்டத்தை பயன்படுத்துகின்றனஃ உருப்படிகளை "சிறியவை" (eB ஐ விட சிறியவை, சில பின்னங்களுக்கு e இன் (0,1)) மற்றும் "பெரியவை" (குறைந்தபட்சம் eB) என பிரிக்கவும். பெரிய உருப்படிகளை முதலில் கையாளவும்ஃ உருப்படியின் அளவுகளை ஏதேனும் ஒரு வகையில் வட்டமிடவும், இதனால் வெவ்வேறு அளவுகளின் எண்ணிக்கை குறைந்தபட்சம் சில நிலையானதாக இருக்கும். சிறிய பொருட்களை பேராசையுடன் ஒதுக்குங்கள், எ. கா. அடுத்த பொருத்தமான தொட்டி பேக்கிங். புதிய தொட்டிகள் உருவாக்கப்படாவிட்டால், நாங்கள் முடித்துவிட்டோம். புதிய தொட்டிகள் உருவாக்கப்பட்டால், அனைத்து தொட்டிகளும் (கடைசி தொட்டியைத் தவிர) குறைந்தபட்சம் (1-இ) பி வரை நிரம்பியிருக்கும் என்று அர்த்தம். எனவே, தொட்டிகளின் எண்ணிக்கை அதிகபட்சமாக ஒபிடி/(1-இ) + 1 ≤ (1 + 2இ) ஒபிடி + 1 ஆகும். வழிமுறைகள் அவை நிகழ்வை எவ்வாறு சுற்றி வருகின்றன என்பதில் வேறுபடுகின்றன. லீனியர் ரவுண்டிங் லுக்கர் மற்றும் டி-லா-வேகா மற்றும் தகவமைப்பு உள்ளீட்டு ரவுண்டிங் யோசனையை கண்டுபிடித்தனர். பொருட்களை அவற்றின் அளவைப் பொறுத்து வரிசைப்படுத்தி, அவற்றை 1/e2 கார்டினாலிட்டி ne2 குழுக்களாக வகைப்படுத்தவும். ஒவ்வொரு குழுவிலும், குழுவில் அதிகபட்ச அளவு வரை அளவுகளை வட்டமிடவும். இப்போது, d = 1/e2 வெவ்வேறு அளவுகள் மட்டுமே உள்ளன. வட்டமான நிகழ்வின் தீர்வு அசல் நிகழ்வுக்கும் சாத்தியமானது, ஆனால் தொட்டிகளின் எண்ணிக்கை தேவையை விட அதிகமாக இருக்கலாம். இழப்பை அளவிட, முந்தைய குழுவில் அதிகபட்ச அளவிற்கு வட்டமிடப்பட்ட நிகழ்வைக் கவனியுங்கள் (முதல் குழு 0 ஆக வட்டமிடப்பட்டுள்ளது). டி இல் சில நெ2 பூஜ்ஜியங்கள் உள்ளன, அதே நேரத்தில் யு இல் சில நெ2 பெரிய உருப்படிகள் உள்ளன என்பதைத் தவிர, ரவுண்டட்-டவுன் இன்ஸ்டன்ஸ் டி கிட்டத்தட்ட ரவுண்டட்-அப் இன்ஸ்டன்ஸ் யு க்கு சமம்; ஆனால் அவற்றின் அளவு அதிகபட்சம் பி. எனவே, U க்கு D ஐ விட அதிக நெக் 2 தொட்டிகள் தேவைப்படுகின்றன. D க்கு உகந்ததை விட குறைவான தொட்டிகள் தேவைப்படுவதால், அந்த தொட்டிகள் (U) ≤ OPT + நெக் 2 ஐப் பெறுகிறோம், அதாவது, நம்மிடம் ஒரு சேர்க்கை பிழை உள்ளது, இது e ஐத் தேர்ந்தெடுப்பதன் மூலம் நாம் விரும்பும் அளவுக்கு சிறியதாக இருக்கும். அனைத்து பொருட்களும் பெரியதாக இருந்தால் (குறைந்தபட்சம் eB அளவு கொண்டவை), பின்னர் OPT இல் உள்ள ஒவ்வொரு தொட்டியிலும் அதிகபட்சம் 1/e உருப்படிகள் (குறைந்தபட்சம் eB அளவு கொண்டவை) இருக்க வேண்டும், எனவே OPT குறைந்தபட்சம் en ஆக இருக்க வேண்டும். எனவே, தொட்டிகள் (யு) ≤ (1 + இ) ஓபிடி. சிறிய பொருட்களைக் கையாண்ட பிறகு, நாம் அதிகபட்சமாக பெறுகிறோம். வடிவியல் வட்டமயமாக்கல் கர்மார்கர் மற்றும் கார்ப் ஆகியவை மிகவும் திறமையான வட்டமயமாக்கல் முறையை வழங்குகின்றன, அவை வடிவியல் வட்டமயமாக்கல் என்று அழைக்கப்படுகின்றன (டி-லா-வேகா மற்றும் லுக்கரின் நேரியல் வட்டமயமாக்கலுக்கு மாறாக). இந்த கண்டுபிடிப்புகளின் அடிப்படையில், அவை மற்றும் இல் ரன்-டைம் பல்லுறுப்புக்கோவையுடன் ஒரு வழிமுறையை வழங்குகின்றன. அவர்களின் வழிமுறை அதிகபட்ச அளவுடன் ஒரு தீர்வை கண்டுபிடிக்கும். மேம்பாடுகள் இந்த நுட்பம் பின்னர் பல ஆசிரியர்களால் மேம்படுத்தப்பட்டதுஃ ரோத்வாஸ் ஒரு வழிமுறையை வழங்கினார், இது அதிகபட்ச அளவுடன் ஒரு தீர்வை உருவாக்குகிறது. ஹோபர்க் மற்றும் ரோத்வாஸ் இந்த வழிமுறையை மேம்படுத்தி அதிகபட்ச அளவுடன் ஒரு தீர்வை உருவாக்கினர். வழிமுறை சீரற்றதாக உள்ளது, மேலும் அதன் இயங்கும் நேரம் மொத்த உருப்படிகளின் எண்ணிக்கையில் பல்லுறுப்புக்கோவை ஆகும். கட்டிங் ஸ்டாக் சிக்கலையும் பார்க்கவும்-அதிக பெருக்கம் கொண்ட தொட்டி பொதி செய்வது போன்றது, ஆனால் ஒவ்வொரு தொட்டியிலும் வீணாகும் இடத்தின் மொத்த அளவைக் குறைப்பதே குறிக்கோள், தொட்டிகளின் எண்ணிக்கையை விட. மேலும், சில வகைகளில், ஒவ்வொரு அளவிலிருந்தும் உருப்படிகளின் எண்ணிக்கை நிலையானதாக இல்லை, ஆனால் கொடுக்கப்பட்ட சில கீழ் மற்றும் மேல் வரம்புகளுக்கு இடையில் நகரலாம். குறிப்புகள் தொட்டி பொதி