उपप्रतिरूपक समुच्चय फलन

गणित में, एक सबमॉड्यूलर फलन समुच्चय करें (जिसे सबमॉड्यूलर फलन के रूप में भी जाना जाता है) एक समुच्चय फलन होता है, जिसका मूल्य,अनौपचारिक रूप से, यह गुण रखता है कि इनपुट समुच्चय में जोड़े जाने पर एकल तत्व जो फलन बनाता है, उसके वृद्धिशील मूल्य में अंतर इनपुट समुच्चय का आकार बढ़ने के साथ घटता जाता है। सबमॉड्यूलर फलन में एक प्राकृतिक ह्रासमान रिटर्न गुण होता है जो उन्हें कई अनुप्रयोगों के लिए उपयुक्त बनाता है, जिसमें सन्निकटन एल्गोरिदम, खेल सिद्धांत (उपयोगकर्ता प्राथमिकताओं को मॉडलिंग करने वाले फलन के रूप में) और विद्युत नेटवर्क सम्मिलित होता हैं। हाल ही में, यंत्र अधिगम और कृत्रिम होशियारी में कई वास्तविक दुनिया की समस्याओं में सबमॉड्यूलर फलन को अत्यधिक उपयोगिता मिली है, जिसमें स्वचालित सारांशीकरण, बहु-दस्तावेज़ सारांशीकरण, फ़ीचर चयन, सक्रिय शिक्षण (मशीन लर्निंग), सेंसर प्लेसमेंट, छवि संग्रह सारांशीकरण और कई अन्य डोमेन सम्मिलित होता हैं।^[1]^[2]^[3]^[4]

परिभाषा

अगर $\Omega$ एक परिमित समुच्चय (गणित) है, सबमॉड्यूलर फलन एक समुच्चय फलन है $f:2^{\Omega }\rightarrow \mathbb {R}$ , कहाँ $2^{\Omega }$ पावर समुच्चय को दर्शाता है उपसमुच्चय को कार्यों के रूप में प्रस्तुत करना $\Omega$ , जो निम्नलिखित समकक्ष शर्तों में से एक को संतुष्ट करता है।^[5]

सभी के लिए $X,Y\subseteq \Omega$ साथ $X\subseteq Y$ और हर $x\in \Omega \setminus Y$ हमारे पास वह है $f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)$ .
सभी के लिए $S,T\subseteq \Omega$ हमारे पास वह है $f(S)+f(T)\geq f(S\cup T)+f(S\cap T)$ .
सभी के लिए $X\subseteq \Omega$ और $x_{1},x_{2}\in \Omega \backslash X$ ऐसा है कि $x_{1}\neq x_{2}$ हमारे पास वह है $f(X\cup \{x_{1}\})+f(X\cup \{x_{2}\})\geq f(X\cup \{x_{1},x_{2}\})+f(X)$ .

एक नॉननेगेटिव सबमोड्युलर भी एक सबएडिटिव समुच्चय फलन है, लेकिन एक सबएडिटिव फलन को सबमॉड्यूलर होने की आवश्यकता नहीं होता है।

अगर $\Omega$ यदि इसे परिमित नहीं माना जाता है, तो उपरोक्त स्थितियाँ समतुल्य नहीं होता हैं। विशेष रूप से एक समारोह

 $f$  द्वारा परिभाषित  $f(S)=1$  अगर  $S$  परिमित है और  $f(S)=0$  अगर  $S$  अनंत है

उपरोक्त पहली शर्त को संतुष्ट करता है, लेकिन दूसरी शर्त विफल हो जाती है $S$ और $T$ परिमित प्रतिच्छेदन वाले अनंत समुच्चय होता हैं।

सबमॉड्यूलर फलन के प्रकार और उदाहरण

मोनोटोन

एक समुच्चय फलन $f$ यदि प्रत्येक के लिए एकरस है $T\subseteq S$ हमारे पास वह है $f(T)\leq f(S)$ . मोनोटोन सबमॉड्यूलर फलन के उदाहरणों में सम्मिलित होता हैं:

रैखिक (मॉड्यूलर) फलन: प्रपत्र का कोई भी कार्य $f(S)=\sum _{i\in S}w_{i}$ एक रैखिक फलन कहलाता है। इसके अतिरिक्त यदि $\forall i,w_{i}\geq 0$ तब f एकस्वर होता है।
बजट-योगात्मक मूल्यांकन: प्रपत्र का कोई भी कार्य $f(S)=\min \left\{B,~\sum _{i\in S}w_{i}\right\}$ प्रत्येक के लिए $w_{i}\geq 0$ और $B\geq 0$ बजट योगात्मक कहा जाता है।^[6]; कवरेज फलन: चलो $\Omega =\{E_{1},E_{2},\ldots ,E_{n}\}$ कुछ मैंट्रोइड के उपसमुच्चय का संग्रह बनें $\Omega '$ . कार्यक्रम $f(S)=\left|\bigcup _{E_{i}\in S}E_{i}\right|$ के लिए $S\subseteq \Omega$ कवरेज फलन कहा जाता है. इसे तत्वों में गैर-नकारात्मक भार जोड़कर सामान्यीकृत किया जा सकता है।
एन्ट्रॉपी (सूचना सिद्धांत): $\Omega =\{X_{1},X_{2},\ldots ,X_{n}\}$ यादृच्छिक चर का एक समुच्चय बना होता है। फिर किसी के लिए $S\subseteq \Omega$ हमारे पास वह है $H(S)$ एक सबमॉड्यूलर फलन होता है, जहां $H(S)$ यादृच्छिक चर के समुच्चय की एन्ट्रापी होता है $S$ , एक तथ्य जिसे एंट्रोपिक वेक्टर शैनन-प्रकार की असमानताएं और Γn|शैनन की असमानता के रूप में जाना जाता है।^[7] एन्ट्रॉपी फलन के लिए और भी असमानताएँ बनी रहने के लिए जानी जाती हैं, एन्ट्रोपिक वेक्टर देखा जाता है।
मैट्रोइड रैंक फलन: $\Omega =\{e_{1},e_{2},\dots ,e_{n}\}$ वह ग्राउंड समुच्चय हो जिस पर मैट्रोइड को परिभाषित किया गया है। फिर मैट्रोइड का रैंक फलन एक सबमॉड्यूलर फलन होता है।^[8]

गैर-नीरस

एक सबमॉड्यूलर फलन जो मोनोटोन नहीं है उसे नॉन-मोनोटोन कहा जाता है।

सममित

एक गैर-मोनोटोन सबमॉड्यूलर फलन $f$ यदि प्रत्येक के लिए सममित कहा जाता है $S\subseteq \Omega$ हमारे पास वह है $f(S)=f(\Omega -S)$ .

सममित गैर-मोनोटोन सबमॉड्यूलर फलन के उदाहरणों में सम्मिलित होता हैं:

ग्राफ़ कट्स: $\Omega =\{v_{1},v_{2},\dots ,v_{n}\}$ एक ग्राफ़ (अलग गणित) के शीर्ष बनें। शीर्षों के किसी भी समुच्चय के लिए $S\subseteq \Omega$ होने देना $f(S)$ किनारों की संख्या को निरूपित करें $e=(u,v)$ ऐसा है कि $u\in S$ और $v\in \Omega -S$ . इसे किनारों पर गैर-नकारात्मक भार जोड़कर सामान्यीकृत किया जा सकता है।
आपसी जानकारी: $\Omega =\{X_{1},X_{2},\ldots ,X_{n}\}$ यादृच्छिक चर का एक समुच्चय बनें। फिर किसी के लिए $S\subseteq \Omega$ हमारे पास वह है $f(S)=I(S;\Omega -S)$ एक सबमॉड्यूलर फलन है, जहां $I(S;\Omega -S)$ आपसी जानकारी है.

असममित

एक गैर-मोनोटोन सबमॉड्यूलर फलन जो सममित नहीं है, असममित कहलाता है।

निर्देशित कटौती: $\Omega =\{v_{1},v_{2},\dots ,v_{n}\}$ एक निर्देशित ग्राफ के शीर्ष बनें। शीर्षों के किसी भी समुच्चय के लिए $S\subseteq \Omega$ होने देना $f(S)$ किनारों की संख्या को निरूपित करें $e=(u,v)$ ऐसा है कि $u\in S$ और $v\in \Omega -S$ . इसे निर्देशित किनारों पर गैर-नकारात्मक भार जोड़कर सामान्यीकृत किया जा सकता है।

सतत विस्तार

परिभाषा

एक समुच्चय फलन $f:2^{\Omega }\rightarrow \mathbb {R}$ साथ $|\Omega |=n$ को फलन के रूप में भी दर्शाया जा सकता है $\{0,1\}^{n}$ , प्रत्येक को संबद्ध करके $S\subseteq \Omega$ एक बाइनरी वेक्टर के साथ $x^{S}\in \{0,1\}^{n}$ ऐसा है कि $x_{i}^{S}=1$ कब $i\in S$ , और $x_{i}^{S}=0$ अन्यथा।

निरंतर Restriction_(mathematics)#Extension_of_a_function का $f$ किसी भी सतत कार्य के रूप में परिभाषित किया गया है $F:[0,1]^{n}\rightarrow \mathbb {R}$ जैसे कि यह के मूल्य से मेल खाता हो $f$ पर $x\in \{0,1\}^{n}$ , अर्थात। $F(x^{S})=f(S)$ .

सबमॉड्यूलर फलन के संदर्भ में, निरंतर एक्सटेंशन के कुछ उदाहरण हैं जो आमतौर पर उपयोग किए जाते हैं, जिनका वर्णन इस प्रकार है।

उदाहरण

राइडर एक्सटेंशन

इस एक्सटेंशन का नाम गणितज्ञ लास्ज़लो लोवाज़ के नाम पर रखा गया है।^[9]किसी भी वेक्टर पर विचार करें $\mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}$ ऐसा कि प्रत्येक $0\leq x_{i}\leq 1$ . तब लोवेज़ एक्सटेंशन को इस प्रकार परिभाषित किया गया है $f^{L}(\mathbf {x} )=\mathbb {E} (f(\{i|x_{i}\geq \lambda \}))$ जहां उम्मीद खत्म हो गई $\lambda$ अंतराल पर समान वितरण (निरंतर) से चुना गया $[0,1]$ . लोवेज़ एक्सटेंशन एक उत्तल फलन है यदि $f$ एक सबमॉड्यूलर फलन है.

बहुरेखीय विस्तार

किसी भी वेक्टर पर विचार करें $\mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}$ ऐसा कि प्रत्येक $0\leq x_{i}\leq 1$ . फिर बहुरेखीय विस्तार को इस प्रकार परिभाषित किया गया है $F(\mathbf {x} )=\sum _{S\subseteq \Omega }f(S)\prod _{i\in S}x_{i}\prod _{i\notin S}(1-x_{i})$ .

उत्तल समापन

किसी भी वेक्टर पर विचार करें $\mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}$ ऐसा कि प्रत्येक $0\leq x_{i}\leq 1$ . फिर उत्तल समापन को इस प्रकार परिभाषित किया गया है $f^{-}(\mathbf {x} )=\min \left(\sum _{S}\alpha _{S}f(S):\sum _{S}\alpha _{S}1_{S}=\mathbf {x} ,\sum _{S}\alpha _{S}=1,\alpha _{S}\geq 0\right)$ . किसी भी समुच्चय फलन का उत्तल समापन उत्तल होता है $[0,1]^{n}$ .

अवतल बंद होना

किसी भी वेक्टर पर विचार करें $\mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}$ ऐसा कि प्रत्येक $0\leq x_{i}\leq 1$ . फिर अवतल समापन को इस प्रकार परिभाषित किया गया है $f^{+}(\mathbf {x} )=\max \left(\sum _{S}\alpha _{S}f(S):\sum _{S}\alpha _{S}1_{S}=\mathbf {x} ,\sum _{S}\alpha _{S}=1,\alpha _{S}\geq 0\right)$ .

एक्सटेंशन के बीच कनेक्शन

ऊपर चर्चा किए गए एक्सटेंशन के लिए, यह दिखाया जा सकता है $f^{+}(\mathbf {x} )\geq F(\mathbf {x} )\geq f^{-}(\mathbf {x} )=f^{L}(\mathbf {x} )$ कब $f$ सबमॉड्यूलर है.^[10]

गुण

सबमॉड्यूलर फलन का वर्ग गैर-नकारात्मक रैखिक संयोजन के तहत बंद (गणित) है। किसी भी सबमॉड्यूलर फलन पर विचार करें $f_{1},f_{2},\ldots ,f_{k}$ और गैर-नकारात्मक संख्याएँ $\alpha _{1},\alpha _{2},\ldots ,\alpha _{k}$ . फिर फलन $g$ द्वारा परिभाषित $g(S)=\sum _{i=1}^{k}\alpha _{i}f_{i}(S)$ सबमॉड्यूलर है.
किसी भी सबमॉड्यूलर फलन के लिए $f$ , द्वारा परिभाषित फलन $g(S)=f(\Omega \setminus S)$ सबमॉड्यूलर है.
कार्यक्रम $g(S)=\min(f(S),c)$ , कहाँ $c$ एक वास्तविक संख्या है, जब भी सबमॉड्यूलर होता है $f$ मोनोटोन सबमॉड्यूलर है. आम तौर पर अधिक, $g(S)=h(f(S))$ किसी भी गैर घटते अवतल फलन के लिए सबमॉड्यूलर है $h$ .
एक यादृच्छिक प्रक्रिया पर विचार करें जहां एक समुच्चय $T$ प्रत्येक तत्व के साथ चुना जाता है $\Omega$ में शामिल किया जा रहा है $T$ संभाव्यता के साथ स्वतंत्र रूप से $p$ . तब निम्नलिखित असमानता सत्य है $\mathbb {E} [f(T)]\geq pf(\Omega )+(1-p)f(\varnothing )$ कहाँ $\varnothing$ खाली समुच्चय है. अधिक आम तौर पर निम्नलिखित यादृच्छिक प्रक्रिया पर विचार करें जहां एक समुच्चय $S$ निम्नानुसार निर्मित किया गया है। प्रत्येक के लिए $1\leq i\leq l,A_{i}\subseteq \Omega$ CONSTRUCT $S_{i}$ प्रत्येक तत्व को सम्मिलित करके $A_{i}$ स्वतंत्र रूप से $S_{i}$ संभाव्यता के साथ $p_{i}$ . इसके अलावा चलो $S=\cup _{i=1}^{l}S_{i}$ . तब निम्नलिखित असमानता सत्य है $\mathbb {E} [f(S)]\geq \sum _{R\subseteq [l]}\Pi _{i\in R}p_{i}\Pi _{i\notin R}(1-p_{i})f(\cup _{i\in R}A_{i})$ .

अनुकूलन समस्याएँ

सबमॉड्यूलर फलन में ऐसे गुण होते हैं जो उत्तल फलन और अवतल फलन के समान होते हैं। इस कारण से, एक अनुकूलन समस्या जो उत्तल या अवतल फलन को अनुकूलित करने से संबंधित है, उसे कुछ बाधाओं के अधीन एक सबमॉड्यूलर फलन को अधिकतम या छोटा करने की समस्या के रूप में भी वर्णित किया जा सकता है।

सबमॉड्यूलर समुच्चय फलन न्यूनतमकरण

सबमॉड्यूलर समुच्चय फलन को न्यूनतम करने की कठोरता समस्या पर लगाई गई बाधाओं पर निर्भर करती है।

सबमॉड्यूलर फलन को न्यूनतम करने की अप्रतिबंधित समस्या बहुपद समय में गणना योग्य है,^[11]^[12]और यहां तक कि दृढ़-बहुपद समय में भी।^[13]^[14]ग्राफ़ में न्यूनतम कटौती की गणना करना इस न्यूनतमकरण समस्या का एक विशेष मामला है।
कार्डिनैलिटी निचली सीमा के साथ एक सबमॉड्यूलर फलन को कम करने की समस्या एनपी कठिन है, सन्निकटन कारक पर बहुपद कारक निचली सीमा के साथ।^[15]^[16]

सबमॉड्यूलर समुच्चय फलन अधिकतमकरण

न्यूनतमकरण के मामले के विपरीत, एक सामान्य सबमॉड्यूलर फलन को अधिकतम करना अप्रतिबंधित सेटिंग में भी एनपी-हार्ड है। इस प्रकार, इस क्षेत्र में अधिकांश कार्य बहुपद-समय सन्निकटन एल्गोरिदम से संबंधित हैं, जिनमें लालची एल्गोरिदम या स्थानीय खोज (अनुकूलन) सम्मिलित होता हैं।

एक गैर-नकारात्मक सबमॉड्यूलर फलन को अधिकतम करने की समस्या 1/2 सन्निकटन एल्गोरिथ्म को स्वीकार करती है।^[17]^[18]ग्राफ़ के अधिकतम कट की गणना करना इस समस्या का एक विशेष मामला है।
कार्डिनैलिटी बाधा के अधीन एक मोनोटोन सबमॉड्यूलर फलन को अधिकतम करने की समस्या स्वीकार करती है $1-1/e$ सन्निकटन एल्गोरिथ्म.^[19]^{[page needed]}^[20] अधिकतम कवरेज समस्या इस समस्या का एक विशेष मामला है।
मैट्रोइड बाधा (जो उपरोक्त मामले को समाहित करता है) के अधीन एक मोनोटोन सबमॉड्यूलर फलन को अधिकतम करने की समस्या भी स्वीकार करती है $1-1/e$ सन्निकटन एल्गोरिथ्म.^[21]^[22]^[23]

इनमें से कई एल्गोरिदम को एल्गोरिदम के अर्ध-विभेदक आधारित ढांचे के भीतर एकीकृत किया जा सकता है।^[16]

अनुप्रयोग

अर्थशास्त्र, गेम थ्योरी, मशीन लर्निंग और कंप्यूटर दृष्टि जैसे कई वास्तविक दुनिया के अनुप्रयोगों में सबमॉड्यूलर फलन स्वाभाविक रूप से होते हैं।^[4]^[27]घटती रिटर्न संपत्ति के कारण, सबमॉड्यूलर फलन स्वाभाविक रूप से वस्तुओं की लागत को मॉडल करते हैं, क्योंकि अक्सर एक बड़ी छूट होती है, जो आइटम खरीदता है उसमें वृद्धि होती है। सबमॉड्यूलर फलन जटिलता, समानता और सहयोग की धारणाओं को मॉडल करते हैं जब वे न्यूनतमकरण समस्याओं में दिखाई देते हैं। दूसरी ओर,अधिकतमीकरण समस्याओं में, वे विविधता, सूचना और कवरेज की धारणाओं को मॉडल करते हैं।

यह भी देखें

उद्धरण

↑ H. Lin and J. Bilmes, A Class of Submodular Functions for Document Summarization, ACL-2011.
↑ S. Tschiatschek, R. Iyer, H. Wei and J. Bilmes, Learning Mixtures of Submodular Functions for Image Collection Summarization, NIPS-2014.
↑ A. Krause and C. Guestrin, Near-optimal nonmyopic value of information in graphical models, UAI-2005.
↑ ^4.0 ^4.1 A. Krause and C. Guestrin, Beyond Convexity: Submodularity in Machine Learning, Tutorial at ICML-2008
↑ (Schrijver 2003, §44, p. 766)
↑ Buchbinder, Niv; Feldman, Moran (2018). "Submodular Functions Maximization Problems". In Gonzalez, Teofilo F. (ed.). Handbook of Approximation Algorithms and Metaheuristics, Second Edition: Methodologies and Traditional Applications. Chapman and Hall/CRC. doi:10.1201/9781351236423. ISBN 9781351236423.
↑ "सूचना प्रसंस्करण और सीखना" (PDF). cmu.
↑ Fujishige (2005) p.22
↑ Lovász, L. (1983). "Submodular functions and convexity". Mathematical Programming the State of the Art: 235–257. doi:10.1007/978-3-642-68874-4_10. ISBN 978-3-642-68876-8.
↑ Vondrák, Jan. "Polyhedral techniques in combinatorial optimization: Lecture 17" (PDF).
↑ Grötschel, M.; Lovasz, L.; Schrijver, A. (1981). "The ellipsoid method and its consequences in combinatorial optimization". Combinatorica. 1 (2): 169–197. doi:10.1007/BF02579273. hdl:10068/182482. S2CID 43787103.
↑ Cunningham, W. H. (1985). "On submodular function minimization". Combinatorica. 5 (3): 185–192. doi:10.1007/BF02579361. S2CID 33192360.
↑ Iwata, S.; Fleischer, L.; Fujishige, S. (2001). "A combinatorial strongly polynomial algorithm for minimizing submodular functions". J. ACM. 48 (4): 761–777. doi:10.1145/502090.502096. S2CID 888513.
↑ Schrijver, A. (2000). "A combinatorial algorithm minimizing submodular functions in strongly polynomial time". J. Combin. Theory Ser. B. 80 (2): 346–355. doi:10.1006/jctb.2000.1989.
↑ Z. Svitkina and L. Fleischer, Submodular approximation: Sampling-based algorithms and lower bounds, SIAM Journal on Computing (2011).
↑ ^16.0 ^16.1 R. Iyer, S. Jegelka and J. Bilmes, Fast Semidifferential based submodular function optimization, Proc. ICML (2013).
↑ U. Feige, V. Mirrokni and J. Vondrák, Maximizing non-monotone submodular functions, Proc. of 48th FOCS (2007), pp. 461–471.
↑ N. Buchbinder, M. Feldman, J. Naor and R. Schwartz, A tight linear time (1/2)-approximation for unconstrained submodular maximization, Proc. of 53rd FOCS (2012), pp. 649-658.
↑ Nemhauser, George; Wolsey, L. A.; Fisher, M. L. (1978). "An analysis of approximations for maximizing submodular set functions I". Mathematical Programming. 14 (14): 265–294. doi:10.1007/BF01588971. S2CID 206800425.
↑ Williamson, David P. "Bridging Continuous and Discrete Optimization: Lecture 23" (PDF).
↑ G. Calinescu, C. Chekuri, M. Pál and J. Vondrák, Maximizing a submodular set function subject to a matroid constraint, SIAM J. Comp. 40:6 (2011), 1740-1766.
↑ M. Feldman, J. Naor and R. Schwartz, A unified continuous greedy algorithm for submodular maximization, Proc. of 52nd FOCS (2011).
↑ Y. Filmus, J. Ward, A tight combinatorial algorithm for submodular maximization subject to a matroid constraint, Proc. of 53rd FOCS (2012), pp. 659-668.
↑ M. Narasimhan and J. Bilmes, A submodular-supermodular procedure with applications to discriminative structure learning, In Proc. UAI (2005).
↑ R. Iyer and J. Bilmes, Algorithms for Approximate Minimization of the Difference between Submodular Functions, In Proc. UAI (2012).
↑ R. Iyer and J. Bilmes, Submodular Optimization Subject to Submodular Cover and Submodular Knapsack Constraints, In Advances of NIPS (2013).
↑ J. Bilmes, Submodularity in Machine Learning Applications, Tutorial at AAAI-2015.

संदर्भ

Schrijver, Alexander (2003), Combinatorial Optimization, Springer, ISBN 3-540-44389-4
Lee, Jon (2004), A First Course in Combinatorial Optimization, Cambridge University Press, ISBN 0-521-01012-8
Fujishige, Satoru (2005), Submodular Functions and Optimization, Elsevier, ISBN 0-444-52086-4
Narayanan, H. (1997), Submodular Functions and Electrical Networks, ISBN 0-444-82523-1
Oxley, James G. (1992), Matroid theory, Oxford Science Publications, Oxford: Oxford University Press, ISBN 0-19-853563-5, Zbl 0784.05002

बाहरी संबंध

http://www.cs.berkeley.edu/~stefje/references.html has a longer bibliography
http://submodularity.org/ includes further material on the subject

[LB-1] H. Lin and J. Bilmes, A Class of Submodular Functions for Document Summarization, ACL-2011.

[TIWB-2] S. Tschiatschek, R. Iyer, H. Wei and J. Bilmes, Learning Mixtures of Submodular Functions for Image Collection Summarization, NIPS-2014.

[KG1-3] A. Krause and C. Guestrin, Near-optimal nonmyopic value of information in graphical models, UAI-2005.

[KG-4] 4.0 ^4.1 A. Krause and C. Guestrin, Beyond Convexity: Submodularity in Machine Learning, Tutorial at ICML-2008

[5] (Schrijver 2003, §44, p. 766)

[BF-6] Buchbinder, Niv; Feldman, Moran (2018). "Submodular Functions Maximization Problems". In Gonzalez, Teofilo F. (ed.). Handbook of Approximation Algorithms and Metaheuristics, Second Edition: Methodologies and Traditional Applications. Chapman and Hall/CRC. doi:10.1201/9781351236423. ISBN 9781351236423.

[7] "सूचना प्रसंस्करण और सीखना" (PDF). cmu.

[F22-8] Fujishige (2005) p.22

[L-9] Lovász, L. (1983). "Submodular functions and convexity". Mathematical Programming the State of the Art: 235–257. doi:10.1007/978-3-642-68874-4_10. ISBN 978-3-642-68876-8.

[JV2-10] Vondrák, Jan. "Polyhedral techniques in combinatorial optimization: Lecture 17" (PDF).

[GLS-11] Grötschel, M.; Lovasz, L.; Schrijver, A. (1981). "The ellipsoid method and its consequences in combinatorial optimization". Combinatorica. 1 (2): 169–197. doi:10.1007/BF02579273. hdl:10068/182482. S2CID 43787103.

[Cunningham-12] Cunningham, W. H. (1985). "On submodular function minimization". Combinatorica. 5 (3): 185–192. doi:10.1007/BF02579361. S2CID 33192360.

[IFF-13] Iwata, S.; Fleischer, L.; Fujishige, S. (2001). "A combinatorial strongly polynomial algorithm for minimizing submodular functions". J. ACM. 48 (4): 761–777. doi:10.1145/502090.502096. S2CID 888513.

[Schrijver-14] Schrijver, A. (2000). "A combinatorial algorithm minimizing submodular functions in strongly polynomial time". J. Combin. Theory Ser. B. 80 (2): 346–355. doi:10.1006/jctb.2000.1989.

[SF-15] Z. Svitkina and L. Fleischer, Submodular approximation: Sampling-based algorithms and lower bounds, SIAM Journal on Computing (2011).

[IJB-16] 16.0 ^16.1 R. Iyer, S. Jegelka and J. Bilmes, Fast Semidifferential based submodular function optimization, Proc. ICML (2013).

[FMV-17] U. Feige, V. Mirrokni and J. Vondrák, Maximizing non-monotone submodular functions, Proc. of 48th FOCS (2007), pp. 461–471.

[BFNS-18] N. Buchbinder, M. Feldman, J. Naor and R. Schwartz, A tight linear time (1/2)-approximation for unconstrained submodular maximization, Proc. of 53rd FOCS (2012), pp. 649-658.

[NVF-19] Nemhauser, George; Wolsey, L. A.; Fisher, M. L. (1978). "An analysis of approximations for maximizing submodular set functions I". Mathematical Programming. 14 (14): 265–294. doi:10.1007/BF01588971. S2CID 206800425.

[20] Williamson, David P. "Bridging Continuous and Discrete Optimization: Lecture 23" (PDF).

[CCPV-21] G. Calinescu, C. Chekuri, M. Pál and J. Vondrák, Maximizing a submodular set function subject to a matroid constraint, SIAM J. Comp. 40:6 (2011), 1740-1766.

[FNS-22] M. Feldman, J. Naor and R. Schwartz, A unified continuous greedy algorithm for submodular maximization, Proc. of 52nd FOCS (2011).

[FW-23] Y. Filmus, J. Ward, A tight combinatorial algorithm for submodular maximization subject to a matroid constraint, Proc. of 53rd FOCS (2012), pp. 659-668.

[NB-24] M. Narasimhan and J. Bilmes, A submodular-supermodular procedure with applications to discriminative structure learning, In Proc. UAI (2005).

[IBUAI-25] R. Iyer and J. Bilmes, Algorithms for Approximate Minimization of the Difference between Submodular Functions, In Proc. UAI (2012).

[IB-26] R. Iyer and J. Bilmes, Submodular Optimization Subject to Submodular Cover and Submodular Knapsack Constraints, In Advances of NIPS (2013).

[JB-27] J. Bilmes, Submodularity in Machine Learning Applications, Tutorial at AAAI-2015.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

Anonymous

Search

उपप्रतिरूपक समुच्चय फलन

Namespaces

More

Page actions

Contents

परिभाषा