2012 के लिए शीर्ष 10 एल्गोरिथम परिणाम

प्रत्येक वर्ष, 31 दिसंबर को, डेविड एप्पस्टीन ने arxiv.org पर प्रकाशित डेटा संरचनाओं और एल्गोरिदम पर पिछले एक साल से पहले के संकेतों की समीक्षा प्रकाशित की है। लिंक पर आप 2010 और 2011 ( मेरे अनुवाद ) वर्षों के लिए सामग्रियों से परिचित हो सकते हैं।

Cs.DS अनुभाग एक अच्छी गति से विकसित हो रहा है: इस वर्ष एल्गोरिदम और डेटा संरचनाओं पर 935 पूर्व-चिह्न दिखाई दिए, जबकि 2011 में 798 थे। अनुभाग प्रति माह सैकड़ों तक नहीं पहुंचता है, हालांकि जुलाई (98 प्रीप्रिंट) में यह सीमा बहुत थी करीब है।

यह मेरी एक दर्जन से पहले की मेरी व्यक्तिगत सूची है जो मुझे विशेष रूप से दिलचस्प लगती है। हमेशा की तरह, मैं इसमें अपने स्वयं के कार्यों और कुछ अन्य को शामिल नहीं करता हूं जो मैंने पहले के बारे में लिखा था । इसके अलावा, कोई परिणाम नहीं हैं (उदाहरण के लिए, अधिकतम प्रवाह खोजने के लिए एक तेज एल्गोरिथ्म ) जो arxiv.org पर दिखाई नहीं दिया।

यहाँ वे कालानुक्रमिक क्रम में हैं:


पेजलाइनर की गणना सबलाइन टाइम के लिए । क्रिश्चियन बोर्ग्स, माइकल ब्रुटबार, जेनिफर चेस और शांग-हुआ टेंग। arXiv: 1202.2771 और WAW 2012 (वेब ​​ग्राफ के लिए एल्गोरिदम और मॉडल पर 9 वीं कार्यशाला)। यह एल्गोरिथ्म एक रैखिक एक की तुलना में बहुत तेज नहीं है (यह आपको उन सभी पृष्ठों को खोजने की अनुमति देता है, जिनका पेजरन ओ (एन / डेल्टा) से परे डेल्टा से बड़ा है, लेकिन यह मेरे लिए दिलचस्प लगता है कि हाइपरलिंक्स द्वारा लिंक किए गए पेज ग्राफ़ के गणना के प्राकृतिक मॉडल में ऐसे अनुमानों को साबित करने में सक्षम हो।

कम से कम फ़्लिप के लिए "सबसे बेईमान" सिक्का ढूँढना । कार्तिकेयन चंद्रशेखरन और रिचर्ड कार्प , arXiv: 1202.3639 इस लेख में हल की गई समस्या बहुत ही मौलिक है, और परिणाम एक इष्टतम समाधान है, पहले से ज्ञात अनुमानों के बजाय, एक निरंतर गुणांक तक।

हैशिंग स्ट्रिंग्स के लिए फास्ट यूनिवर्सल एल्गोरिथ्म। ओवेन केसर और डैनियल लेमायर , arXiv: 1202.4961। हैशिंग स्ट्रिंग्स के लिए एक एल्गोरिथ्म जो एक बाइट को संसाधित करने के लिए प्रोसेसर समय के 0.2 घड़ी चक्र का उपयोग करता है और एक ही समय में सैद्धांतिक रूप से गारंटीकृत विशेषताएं हैं।

EDGE CLIQUE COVER को हल करने के लिए प्रसिद्ध एल्गोरिदम शायद इष्टतम हैं। मारेक साइगन , मार्सिन पिलिप्सीचुक और मिचेल पिलिप्चुक , एएक्सएक्सवी: 1203.1754 और सोडा 2013 । न्यूनतम क्लिकों के साथ ग्राफ के किनारों को कवर करने के लिए एक साधारण FPT एल्गोरिदम है, जिसका रनटाइम, हालांकि, 2 ^{2 o (k)} पाली (n) के समानुपाती है, जहाँ k क्लिक की संख्या है और n ग्राफ में कोने की संख्या है। निस्संदेह , इस मूल्यांकन में सुधार का कार्य काफी लंबा समय रहा है। पिछले साल, यह दिखाया गया था कि कार्य का एक बेहतर कर्नेलीकरण प्राप्त नहीं किया जा सकता है, और यह पूर्व संकेत दिखाता है कि ऐसा अनुमान इष्टतम है कि हम कर्नेल का उपयोग करते हैं या नहीं। कम से कम बशर्ते कि घातीय समय की परिकल्पना सत्य हो ।

पावर लॉ ग्राफ़ में वर्टेक्स कवरेज समस्या के समाधान की स्थिरता। मिकेल गैस्ट और मैथियस हॉन्टमैन , आरएक्सआईवी: 1204.0982 । मुझे ऐसा लगता है कि एल्गोरिदम पर अधिक काम होना चाहिए जो वेब पर उपयोगकर्ताओं या सामाजिक नेटवर्क पर उपयोगकर्ताओं के पेज ग्राफ़ के गुणों का उपयोग करते हैं। यह एल्गोरिथ्म एक अच्छा उदाहरण है: यह किसी भी ग्राफ के लिए वर्टेक्स कवरेज समस्या के लिए अनुमानित डिग्री में सुधार करता है जिसमें वर्टिकल की डिग्री का वितरण होता है जिसमें एक शक्ति कानून का पालन होता है।

क्लस्टरिंग मुश्किल है केवल जब यह आवश्यक नहीं है । अमित डेनियली, नाटी लिनिअल और माइकल सैक्स, arXiv: 1205.4891 । जैसा कि पिछले लेख में, यह समस्या के जटिलता के चरण से लेकर सामान्य मामले में समस्या के कुछ और विशिष्ट उदाहरणों के लिए जटिलता के आकलन तक का वर्णन करता है। मुख्य विचार यह है कि केवल डेटा जो सिद्धांत में क्लस्टर करना मुश्किल है, एल्गोरिदम को क्लस्टर करना मुश्किल है। इस लेख में दी गई "अच्छी क्लस्टरिंग" की परिभाषा बहुत अधिक आउटलेयर या हस्तक्षेप के साथ डेटा के लिए बहुत संवेदनशील लगती है, लेकिन यह अच्छी तरह से आगे के अध्ययन का विषय हो सकता है।

O (n ² ) में आकार nxn के रैखिक समीकरणों की एक प्रणाली को हल करने के लिए एक यादृच्छिक समानांतर एल्गोरिदम । जोर्ज फ्लिजे, arXiv: 1209.3995 । प्रसाद राघवेंद्र द्वारा बनाए गए परिमित क्षेत्रों पर समीकरणों के समाधान के लिए एल्गोरिदम में असली सफलता यहां है, और इसका वर्णन पिछले साल ब्लॉग रिचर्ड लिपटन पर किया गया था। यह आलेख वर्णन करता है कि इसे वास्तविक संख्याओं पर कैसे लागू किया जाए।

एक गतिशील ग्राफ कनेक्टिविटी समस्या के निर्धारक समाधान के आकलन में सुधार। क्रिश्चियन वुल्फ-निल्सन, arXiv: 1209.5608 और सोडा 2013। एक डेटा संरचना प्रस्तुत की गई है जो संशोधित समय के लिए अद्यतन अनुरोधों (किनारों को हटाने या हटाने) का समर्थन करती है O (लॉग ² एन / लॉग लॉग एन) और फॉर्म के अनुरोधों "ग्राफ़ के कोने के बीच एक रास्ता है U और v ”सबसे खराब स्थिति में O (लॉग एन / लॉग लॉग एन) के लिए, जहां ग्राफ में एन वर्टिस की संख्या है। (एप्सटीन को एक अजीब सजा थी - एक ग्राफ अपडेट अनुरोध के लिए पिछला सबसे अच्छा अनुमान ओ था (लॉग ² एन) और यह परिणाम सिर्फ लॉग शेविंग था (वास्तव में, लॉग लॉग शेविंग)।

यात्रा सेल्समैन समस्या के समाधान के 8/5-सन्निकटन। एंड्रस सेब, अर्क्सिव : 1209.3523 और आईपीसीओ 2013 । यह लेख ट्रैवलिंग सेल्समैन समस्या के एक संशोधन के बारे में है, जिसमें उनकी यात्रा के शुरुआती और अंतिम बिंदु आवश्यक रूप से मेल नहीं खाते हैं। मैंने छात्रों को क्रिस्टोफ़ाइड एल्गोरिथ्म के बारे में बताया कि पथ और चक्र की समस्या के बीच अंतर को जानने के लिए पर्याप्त समय है, लेकिन यह तथ्य कि पथ की लंबाई का अनुमान लगाने के लिए अनुमानित गुणांक चक्र की लंबाई का अनुमान लगाने की तुलना में काफी बड़ा है, जो किसी तरह मेरे द्वारा पारित किया गया था।

छद्म सन्निकटन द्वारा के-मध्ययुगीन सन्निकटन। शि ली और ओला स्वेन्सन, arXiv: 1211.0243 । यहाँ k-medians का कार्य वास्तव में k क्लस्टर केंद्रों को खोजना है, प्रत्येक बिंदु से दूरी के योग को क्लस्टर के केंद्र तक पहुँचाना है, जिसमें से यह है, इस समस्या का सन्निकटन k केंद्रों को खोजना है, कुछ सटीकता के साथ उद्देश्य फ़ंक्शन को कम करना और छद्म-सन्निकटन का लगभग पता लगाना है। k केंद्र। जैसा कि लेखक लिखते हैं, यहां तक ​​कि एक अतिरिक्त बिंदु को जोड़ने से उद्देश्य फ़ंक्शन के रूप में काफी बदलाव होता है, इसलिए इस समस्या पर छद्म सन्निकटन लागू होने का तथ्य काफी आश्चर्यजनक है।