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

गणित में, एक सबमॉड्यूलर फ़ंक्शन समुच्चय करें (जिसे सबमॉड्यूलर फ़ंक्शन के रूप में भी जाना जाता है) एक समुच्चय फ़ंक्शन होता है, जिसका मूल्य,अनौपचारिक रूप से, यह गुण रखता है कि इनपुट समुच्चय में जोड़े जाने पर एकल तत्व जो फ़ंक्शन बनाता है, उसके वृद्धिशील मूल्य में अंतर इनपुट समुच्चय का आकार बढ़ने के साथ घटता जाता है। सबमॉड्यूलर फ़ंक्शंस में एक प्राकृतिक ह्रासमान रिटर्न गुण होता है जो उन्हें कई अनुप्रयोगों के लिए उपयुक्त बनाता है, जिसमें सन्निकटन एल्गोरिदम, खेल सिद्धांत (उपयोगकर्ता प्राथमिकताओं को मॉडलिंग करने वाले फ़ंक्शन के रूप में) और विद्युत नेटवर्क सम्मिलित होता हैं। हाल ही में, यंत्र अधिगम और कृत्रिम होशियारी में कई वास्तविक दुनिया की समस्याओं में सबमॉड्यूलर फ़ंक्शंस को अत्यधिक उपयोगिता मिली है, जिसमें स्वचालित सारांशीकरण, बहु-दस्तावेज़ सारांशीकरण, फ़ीचर चयन, सक्रिय शिक्षण (मशीन लर्निंग), सेंसर प्लेसमेंट, छवि संग्रह सारांशीकरण और कई अन्य डोमेन सम्मिलित होता हैं।^[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}\}$ कुछ matroid के उपसमुच्चय का संग्रह बनें $\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})$ .^{[citation needed]}

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

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

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

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

सबमॉड्यूलर फ़ंक्शन को न्यूनतम करने की अप्रतिबंधित समस्या बहुपद समय में गणना योग्य है,^[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

परिभाषा