नवीनतम घटनाएँ
श्री यशदीप सिंह द्वारा रिसर्च सेमिनार 28 नवंबर, 2025 को दोपहर 12 बजे
वार्ता का शीर्षक: लोकप्रिय मिलान
दिनांक, समय और स्थान: 28 नवंबर, 2025 को दोपहर 12 बजे सेमिनार कक्ष, गणित विभाग में
सार: लोकप्रिय मिलान एक ग्राफ़-सैद्धांतिक ढाँचा है जो "सामाजिक रूप से पसंदीदा" मिलान चुनने के लिए होता है, जब शीर्ष अपने संभावित भागीदारों को रैंक करते हैं, जहाँ एक मिलान को दूसरे पर वरीयता दी जाती है यदि अधिकांश शीर्ष व्यक्तिगत रूप से इसके पक्ष में हों। ऐसे मॉडल रूममेट आवंटन, छात्र-परियोजना असाइनमेंट और छोटे-समूह गठन जैसी स्थितियों में सामने आते हैं, जहाँ एजेंट संभावित जोड़ियों पर अपनी प्राथमिकताएँ व्यक्त करते हैं। एक मिलान को लोकप्रिय कहा जाता है यदि कोई अन्य मिलान बहुमत मतों में उसे पराजित नहीं करता है।
इस व्याख्यान के पहले भाग में, मैं बुनियादी परिभाषाएँ प्रस्तुत करूँगा, अलोकप्रियता कारक की व्याख्या करूँगा, और छोटे-छोटे उदाहरणों का उपयोग करके यह समझाऊँगा कि बहुसंख्यक तुलनाएँ कैसे काम करती हैं और साधारण ग्राफ़ में भी लोकप्रिय मिलान क्यों नहीं हो पाता। इसके बाद हम गैर-द्विपक्षीय ग्राफ़ और 3-समान 3-पक्षीय हाइपरग्राफ़ सहित अधिक सामान्य संरचनाओं की ओर बढ़ेंगे, जो अनुप्रयोगों में आने वाले व्यावहारिक आवंटन परिदृश्यों को बेहतर ढंग से दर्शाते हैं।
दूसरे भाग में, मैं इन परिस्थितियों में हाल के परिणामों को संक्षेप में प्रस्तुत करूँगा। एकतरफ़ा वरीयताओं वाले 3-समान 3-भागीय हाइपरग्राफ़ के लिए, मैं दर्शाता हूँ कि किसी लोकप्रिय मिलान के अस्तित्व का निर्धारण करना गणना-संबंधी रूप से कठिन है और अलोकप्रियता कारक के माध्यम से किसी भी मिलान की लोकप्रियता के कितने निकट हो सकती है, इसकी सीमा प्राप्त करता हूँ। गैर-द्विभागीय ग्राफ़ के लिए, मैं दर्शाता हूँ कि उपघन और कैक्टस ग्राफ़ हमेशा अधिकतम 2 के अलोकप्रियता कारक वाले मिलानों को स्वीकार करते हैं, जो कि इष्टतम है।
वक्ता के बारे में: श्री यशदीप सिंह, प्रो. सुशांत कर्माकर के मार्गदर्शन में आईआईटी गुवाहाटी से कंप्यूटर विज्ञान एवं इंजीनियरिंग में अपनी पीएचडी पूरी कर रहे हैं। वे नॉन-बाइलेक्टिक ग्राफ़ और हाइपरग्राफ़ में लोकप्रिय मिलान समस्याओं पर काम कर रहे हैं। उनके शोध योगदानों में एनपी-हार्डनेस परिणाम और सन्निकटन एल्गोरिदम शामिल हैं, जिनके प्रकाशन IWOCA, CANDAR, और कॉन्करेंसी एंड कंप्यूटेशन: प्रैक्टिस एंड एक्सपीरियंस में हुए हैं। उन्होंने आईआईटी गुवाहाटी से कंप्यूटर विज्ञान एवं इंजीनियरिंग में एम.टेक. की डिग्री भी प्राप्त की है और वर्तमान में अपनी पीएचडी डिफेंस की प्रतीक्षा कर रहे हैं।
