ในทางคณิตศาสตร์ฟังก์ชันเซตย่อยโมดูลาร์ (หรือที่รู้จักกันในชื่อฟังก์ชันย่อยโมดูลาร์ ) คือฟังก์ชันเซตที่อธิบายความสัมพันธ์ระหว่างชุดของอินพุตและเอาต์พุต โดยที่การเพิ่มอินพุตหนึ่งตัวจะให้ผลประโยชน์เพิ่มเติมที่ลดลง ( ผลตอบแทนที่ลดลง ) คุณสมบัติ ผลตอบแทนที่ลดลง ตามธรรมชาติ ทำให้ฟังก์ชันเหล่านี้เหมาะสมสำหรับการใช้งานหลายอย่าง รวมถึงอัลกอริธึมการประมาณค่าทฤษฎีเกม (ในฐานะฟังก์ชันที่จำลองความชอบของผู้ใช้) และเครือข่ายไฟฟ้าเมื่อไม่นานมานี้ ฟังก์ชันย่อยโมดูลาร์ยังพบประโยชน์ในปัญหาในโลกแห่งความเป็นจริงหลายอย่างในด้านการเรียนรู้ของเครื่องและปัญญาประดิษฐ์รวมถึงการสรุปอัตโนมัติการสรุปเอกสารหลายฉบับการเลือกคุณลักษณะการเรียนรู้เชิงรุกการวางตำแหน่งเซ็นเซอร์ การสรุปคอลเลกชันรูปภาพ และโดเมนอื่นๆ อีกมากมาย^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]}

ถ้าเป็นเซต จำกัด ฟังก์ชันซับโมดูลาร์คือฟังก์ชันเซตโดยที่หมายถึงเซตกำลังของซึ่งเป็นไปตามเงื่อนไขที่เทียบเท่ากันข้อใดข้อหนึ่งต่อไปนี้^{[ 5 ]}${\displaystyle \Omega }$${\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} }$${\displaystyle 2^{\Omega }}$${\displaystyle \Omega }$

1. สำหรับทุกๆสิ่งที่ เรามีอยู่ และทุกๆ สิ่งที่เรามีนั้น${\displaystyle X,Y\subseteq \Omega }$${\displaystyle X\subseteq Y}$${\displaystyle x\in \Omega \setminus Y}$${\displaystyle f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)}$
2. สำหรับทุกสิ่งที่เรามีนั้น${\displaystyle S,T\subseteq \Omega }$${\displaystyle f(S)+f(T)\geq f(S\cup T)+f(S\cap T)}$
3. สำหรับทุกๆและเช่นนั้นที่เรามีว่าหรือเทียบเท่ากับ${\displaystyle X\subseteq \Omega }$${\displaystyle x_{1},x_{2}\in \Omega \backslash X}$${\displaystyle x_{1}\neq x_{2}}$${\displaystyle f(X\cup \{x_{1}\})+f(X\cup \{x_{2}\})\geq f(X\cup \{x_{1},x_{2}\})+f(X)}$${\displaystyle f(X\cup \{x_{1}\})-f(X)\geq f(X\cup \{x_{1},x_{2}\})-f(X\cup \{x_{2}\})}$

ฟังก์ชันซับโมดูลาร์ที่ไม่เป็นลบก็เป็น ฟังก์ชัน ซับแอดดิทีฟ ด้วย แต่ฟังก์ชันซับแอดดิทีฟไม่จำเป็นต้องเป็นซับโมดูลาร์เสมอไป ถ้าไม่ถือว่าเซต เป็นเซตจำกัด เงื่อนไขข้างต้นจะไม่เทียบเท่ากัน โดยเฉพาะอย่างยิ่ง ฟังก์ชัน ที่กำหนดโดยถ้าเป็นเซตจำกัด และถ้าเป็นเซตอนันต์ จะตรงตามเงื่อนไขแรกข้างต้น แต่เงื่อนไขที่สองจะไม่เป็นจริงเมื่อและเป็นเซตอนันต์ที่มีส่วนร่วมจำกัด ${\displaystyle \Omega }$${\displaystyle f}$${\displaystyle f(S)=1}$${\displaystyle S}$${\displaystyle f(S)=0}$${\displaystyle S}$${\displaystyle S}$${\displaystyle T}$

ฟังก์ชันเซตเรียกว่าฟังก์ชันเอกภาคถ้าสำหรับทุกค่าเรามีว่าตัวอย่างของฟังก์ชันซับโมดูลาร์เอกภาค ได้แก่: ${\displaystyle f}$${\displaystyle T\subseteq S}$${\displaystyle f(T)\leq f(S)}$

ฟังก์ชันเชิงเส้น (โมดูลาร์)

ฟังก์ชันใดๆ ที่อยู่ในรูปแบบดังกล่าวเรียกว่าฟังก์ชันเชิงเส้น นอกจากนี้ ถ้าf เป็นฟังก์ชันเอกภาคด้วย${\displaystyle f(S)=\sum _{i\in S}w_{i}}$${\displaystyle \forall i,w_{i}\geq 0}$

ฟังก์ชันเพิ่มงบประมาณ

ฟังก์ชันใดๆ ในรูปแบบสำหรับแต่ละและเรียกว่างบประมาณแบบบวก^{[ 6 ]}${\displaystyle f(S)=\min \left\{B,~\sum _{i\in S}w_{i}\right\}}$${\displaystyle w_{i}\geq 0}$${\displaystyle B\geq 0}$

ฟังก์ชันการครอบคลุม

ให้เป็นกลุ่มของเซตย่อยของเซตพื้นฐาน บางเซต ฟังก์ชันสำหรับเรียกว่าฟังก์ชันความครอบคลุม ซึ่งสามารถขยายความได้โดยการเพิ่มน้ำหนักที่ไม่เป็นลบให้กับองค์ประกอบต่างๆ${\displaystyle \Omega =\{E_{1},E_{2},\ldots ,E_{n}\}}$${\displaystyle \Omega '}$${\displaystyle f(S)=\left|\bigcup _{E_{i}\in S}E_{i}\right|}$${\displaystyle S\subseteq \Omega }$

เอนโทรปี

ให้เป็นเซตของตัวแปรสุ่มแล้วสำหรับใดๆเราจะได้ว่าเป็นฟังก์ชันย่อยโมดูลาร์ โดยที่คือเอนโทรปีของเซตของตัวแปรสุ่มซึ่งเป็นข้อเท็จจริงที่รู้จักกันในชื่ออสมการของแชนนอน [ ^{7 ] อสมการ}เพิ่มเติมสำหรับฟังก์ชันเอนโทรปีเป็นที่ทราบกันว่าเป็นจริง ดูเวกเตอร์เอนโทรปี${\displaystyle \Omega =\{X_{1},X_{2},\ldots ,X_{n}\}}$${\displaystyle S\subseteq \Omega }$${\displaystyle H(S)}$${\displaystyle H(S)}$${\displaystyle S}$

ฟังก์ชันอันดับMatroid

ให้เป็นเซตพื้นฐานที่แมทรอยด์ถูกกำหนดไว้ จากนั้นฟังก์ชันอันดับของแมทรอยด์จะเป็นฟังก์ชันย่อยโมดูลาร์^{[ 8 ]}${\displaystyle \Omega =\{e_{1},e_{2},\dots ,e_{n}\}}$

ฟังก์ชันย่อยโมดูลาร์ที่ไม่เป็นฟังก์ชันเอกภาคเรียกว่าฟังก์ชันไม่เอกภาคโดยเฉพาะอย่างยิ่ง ฟังก์ชันจะเรียกว่าฟังก์ชันไม่เอกภาคหากมีคุณสมบัติที่ว่าการเพิ่มสมาชิกเข้าไปในเซตจะทำให้ค่าของฟังก์ชันลดลง กล่าวอย่างเป็นทางการมากขึ้น ฟังก์ชันจะเป็นฟังก์ชันไม่เอกภาคหากมีเซตในโดเมนของฟังก์ชันคือst และ${\displaystyle f}$${\displaystyle S,T}$${\displaystyle S\subset T}$${\displaystyle f(S)>f(T)}$

ฟังก์ชันซับโมดูลาร์ที่ไม่เป็นโมโนโทนเรียกว่าสมมาตรถ้าสำหรับทุก ๆเรามีว่าตัวอย่างของฟังก์ชันซับโมดูลาร์ที่ไม่เป็นโมโนโทนแบบสมมาตร ได้แก่: ${\displaystyle f}$${\displaystyle S\subseteq \Omega }$${\displaystyle f(S)=f(\Omega -S)}$

กราฟตัด

ให้เป็นจุดยอดของกราฟสำหรับเซตของจุดยอดใดๆให้แทนจำนวนขอบที่ทำให้และซึ่งสามารถขยายความได้โดยการเพิ่มน้ำหนักที่ไม่เป็นลบให้กับขอบ${\displaystyle \Omega =\{v_{1},v_{2},\dots ,v_{n}\}}$${\displaystyle S\subseteq \Omega }$${\displaystyle f(S)}$${\displaystyle e=(u,v)}$${\displaystyle u\in S}$${\displaystyle v\in \Omega -S}$

ข้อมูลร่วมกัน

ให้เป็นเซตของตัวแปรสุ่มแล้วสำหรับใดๆเราจะได้ว่าเป็นฟังก์ชันย่อยโมดูลาร์ โดยที่คือข้อมูลร่วม${\displaystyle \Omega =\{X_{1},X_{2},\ldots ,X_{n}\}}$${\displaystyle S\subseteq \Omega }$${\displaystyle f(S)=I(S;\Omega -S)}$${\displaystyle I(S;\Omega -S)}$

ฟังก์ชันย่อยโมดูลาร์ที่ไม่เป็นโมโนโทนและไม่สมมาตร เรียกว่า ฟังก์ชันอสมมาตร

การตัดต่อแบบกำหนดทิศทาง

ให้เป็นจุดยอดของกราฟทิศทางสำหรับเซตของจุดยอดใดๆให้แทนจำนวนขอบที่และซึ่งสามารถขยายความได้โดยการเพิ่มน้ำหนักที่ไม่เป็นลบให้กับขอบทิศทาง${\displaystyle \Omega =\{v_{1},v_{2},\dots ,v_{n}\}}$${\displaystyle S\subseteq \Omega }$${\displaystyle f(S)}$${\displaystyle e=(u,v)}$${\displaystyle u\in S}$${\displaystyle v\in \Omega -S}$

บ่อยครั้งที่เรามีฟังก์ชันเซตย่อยแบบโมดูลาร์ที่อธิบายค่าของเซตต่างๆ เราจำเป็นต้องคำนวณค่าของ เซต เศษส่วนตัวอย่างเช่น เรารู้ว่าค่าของการได้รับบ้าน A และบ้าน B คือ V และเราต้องการทราบค่าของการได้รับ 40% ของบ้าน A และ 60% ของบ้าน B เพื่อจุดประสงค์นี้ เราจำเป็นต้องมีการขยายฟังก์ชันเซตย่อยแบบโมดูลาร์ อย่างต่อเนื่อง

ในทางทฤษฎี ฟังก์ชันเซตที่มีสามารถแสดงได้เป็นฟังก์ชันบนโดยการเชื่อมโยงแต่ละกับเวกเตอร์ไบนารีโดยที่เมื่อและมิเช่นนั้นส่วนขยายต่อเนื่องของคือฟังก์ชันต่อเนื่องที่ตรงกับค่าของบนกล่าว คือ${\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} }$${\displaystyle |\Omega |=n}$${\displaystyle \{0,1\}^{n}}$${\displaystyle S\subseteq \Omega }$${\displaystyle x^{S}\in \{0,1\}^{n}}$${\displaystyle x_{i}^{S}=1}$${\displaystyle i\in S}$${\displaystyle x_{i}^{S}=0}$${\displaystyle f}$${\displaystyle F:[0,1]^{n}\rightarrow \mathbb {R} }$${\displaystyle f}$${\displaystyle x\in \{0,1\}^{n}}$${\displaystyle F(x^{S})=f(S)}$

มีการใช้งานส่วนขยายต่อเนื่องหลายประเภทของฟังก์ชันย่อยแบบโมดูลาร์อยู่ทั่วไป ซึ่งจะอธิบายไว้ด้านล่าง

ส่วนขยายนี้ตั้งชื่อตามนักคณิตศาสตร์László Lovász [ ^{9 ] พิจารณา}เวกเตอร์ใดๆที่แต่ละ จากนั้นส่วนขยาย Lovász จะถูกกำหนดดังนี้ ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}$${\displaystyle 0\leq x_{i}\leq 1}$

${\displaystyle f^{L}(\mathbf {x} )=\mathbb {E} (f(\{i|x_{i}\geq \lambda \}))}$

โดยที่ค่าคาดหวังถูกเลือกจากค่าที่ได้จากการแจกแจงแบบเอกรูปในช่วง ส่วนขยายของ Lovász เป็นฟังก์ชันนูนก็ต่อเมื่อเป็นฟังก์ชันย่อยแบบโมดูลาร์ ${\displaystyle \lambda }$${\displaystyle [0,1]}$${\displaystyle f}$

พิจารณาเวกเตอร์ใดๆที่แต่ละ. จากนั้นส่วนขยายเชิงเส้นหลายตัวจะถูกกำหนดเป็น ^{[ 10 ] [ 11 ]}${\displaystyle \mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}}$${\displaystyle 0\leq x_{i}\leq 1}$${\displaystyle F(\mathbf {x} )=\sum _{S\subseteq \Omega }f(S)\prod _{i\in S}x_{i}\prod _{i\notin S}(1-x_{i})}$

โดยสัญชาตญาณแล้วx _iแทนความน่าจะเป็นที่รายการiจะถูกเลือกสำหรับเซต สำหรับทุกเซตSผลคูณภายในทั้งสองแสดงถึงความน่าจะเป็นที่เซตที่เลือกคือS อย่างแน่นอน ดังนั้น ผลรวมจึงแสดงถึงค่าที่คาดหวังของfสำหรับเซตที่เกิดจากการเลือกแต่ละรายการiแบบสุ่มด้วยความน่าจะเป็น xi โดยไม่ขึ้นอยู่กับรายการอื่นๆ

พิจารณาเวกเตอร์ใดๆที่แต่ละ. จากนั้นการปิดแบบนูนจะถูกกำหนดเป็น. ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}$${\displaystyle 0\leq x_{i}\leq 1}$${\displaystyle 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)}$

ส่วนปิดนูนของฟังก์ชันเซตใดๆ จะเป็นฟังก์ชันนูนเหนือ ${\displaystyle [0,1]^{n}}$

พิจารณาเวกเตอร์ใดๆที่แต่ละ. จากนั้นส่วนปิดเว้าจะถูกกำหนดเป็น. ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}$${\displaystyle 0\leq x_{i}\leq 1}$${\displaystyle 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)}$

สำหรับส่วนขยายที่กล่าวถึงข้างต้น สามารถแสดงได้ว่าเมื่อใดจะเป็นซับโมดูลาร์^{[ 12 ]}${\displaystyle f^{+}(\mathbf {x} )\geq F(\mathbf {x} )\geq f^{-}(\mathbf {x} )=f^{L}(\mathbf {x} )}$${\displaystyle f}$

1. กลุ่มของฟังก์ชันซับโมดูลาร์นั้นปิด ภายใต้ การรวมเชิงเส้นที่ไม่เป็นลบพิจารณาฟังก์ชันซับโมดูลาร์ใดๆและจำนวนที่ไม่เป็นลบแล้วฟังก์ชันที่กำหนดโดย จะเป็นฟังก์ชันซับโมดูลาร์${\displaystyle f_{1},f_{2},\ldots ,f_{k}}$${\displaystyle \alpha _{1},\alpha _{2},\ldots ,\alpha _{k}}$${\displaystyle g}$${\displaystyle g(S)=\sum _{i=1}^{k}\alpha _{i}f_{i}(S)}$
2. สำหรับฟังก์ชันย่อยโมดูลาร์ใดๆฟังก์ชันที่กำหนดโดย ก็เป็นฟังก์ชันย่อยโมดูลาร์เช่น กัน${\displaystyle f}$${\displaystyle g(S)=f(\Omega \setminus S)}$
3. ฟังก์ชันโดยที่เป็นจำนวนจริงจะเป็นฟังก์ชันย่อยโมดูลาร์เมื่อใดก็ตามที่เป็นฟังก์ชันย่อยโมดูลาร์แบบเอกภาค โดยทั่วไปแล้วจะเป็นฟังก์ชันย่อยโมดูลาร์สำหรับฟังก์ชันเว้าที่ไม่ลดลงใดๆ${\displaystyle g(S)=\min(f(S),c)}$${\displaystyle c}$${\displaystyle f}$${\displaystyle g(S)=h(f(S))}$${\displaystyle h}$
4. พิจารณากระบวนการสุ่มที่ เลือกเซต โดยแต่ละองค์ประกอบใน เซต จะถูกรวมเข้าไปในเซตอย่างอิสระด้วยความน่าจะเป็น แล้วอสมการต่อไปนี้จะเป็นจริงโดยที่คือเซตว่างโดยทั่วไปแล้ว ให้พิจารณากระบวนการสุ่มต่อไปนี้ โดยสร้างเซต ดังนี้ สำหรับแต่ละสร้าง เซต โดยการรวมแต่ละองค์ประกอบในเซต เข้าไปในเซต อย่างอิสระด้วยความน่าจะเป็นนอกจากนี้ ให้ แล้วอสมการต่อไปนี้จะเป็นจริง${\displaystyle T}$${\displaystyle \Omega }$${\displaystyle T}$${\displaystyle p}$${\displaystyle \mathbb {E} [f(T)]\geq pf(\Omega )+(1-p)f(\varnothing )}$${\displaystyle \varnothing }$${\displaystyle S}$${\displaystyle 1\leq i\leq l,A_{i}\subseteq \Omega }$${\displaystyle S_{i}}$${\displaystyle A_{i}}$${\displaystyle S_{i}}$${\displaystyle p_{i}}$${\displaystyle S=\cup _{i=1}^{l}S_{i}}$${\displaystyle \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})}$

ฟังก์ชันซับโมดูลาร์มีคุณสมบัติที่คล้ายคลึงกับ ฟังก์ชัน นูนและฟังก์ชันเว้า มาก ด้วยเหตุนี้ปัญหาการหาค่าเหมาะสมที่สุดที่เกี่ยวข้องกับการหาค่าเหมาะสมที่สุดของฟังก์ชันนูนหรือฟังก์ชันเว้า จึงสามารถอธิบายได้ว่าเป็นปัญหาการหาค่าสูงสุดหรือค่าต่ำสุดของฟังก์ชันซับโมดูลาร์ภายใต้ข้อจำกัดบางประการ

ความยากของการหาค่าต่ำสุดของฟังก์ชันเซตย่อยโมดูลาร์นั้นขึ้นอยู่กับข้อจำกัดที่กำหนดไว้ในปัญหา

1. ปัญหาการลดค่าฟังก์ชันย่อยแบบไม่จำกัดสามารถคำนวณได้ใน^เวลาพหุนาม [ ^{13 ] [ 14 ]}และแม้กระทั่งในเวลาพหุนามที่เข้มงวด^{[ 15 ] [ 16 ]}การคำนวณการตัดขั้นต่ำในกราฟเป็นกรณีพิเศษของปัญหาการลดค่านี้
2. ปัญหาการลดฟังก์ชันย่อยโมดูลาร์ที่มีขอบเขตล่างของจำนวนสมาชิกเป็นปัญหาNP-hardโดยมีขอบเขตล่างของตัวประกอบพหุนามบนตัวประกอบการประมาณค่า^{[ 17 ] [ 18 ]}

ต่างจากกรณีของการหาค่าต่ำสุด การหาค่าสูงสุดของฟังก์ชันย่อยแบบทั่วไปนั้นเป็นปัญหาNP-hardแม้ในกรณีที่ไม่มีข้อจำกัด ดังนั้น งานวิจัยส่วนใหญ่ในสาขานี้จึงเกี่ยวข้องกับอัลกอริธึมการประมาณค่าในเวลาพหุนาม ซึ่งรวมถึงอัลกอริธึมแบบโลภ(greedy algorithms)หรือ อัลกอริธึมการค้นหาแบบโลคอล ( local search algorithms )

1. ปัญหาของการเพิ่มค่าสูงสุดของฟังก์ชันย่อยโมดูลาร์ที่ไม่เป็นลบนั้นยอมรับอัลกอริทึมการประมาณค่า 1/2 ^{[ 19 ] [ 20 ]}การคำนวณการตัดสูงสุดของกราฟเป็นกรณีพิเศษของปัญหานี้
2. ปัญหาของการเพิ่มค่าสูงสุดของฟังก์ชันย่อยแบบโมโนโทนภายใต้ข้อจำกัดของจำนวนสมาชิกนั้นยอมรับอัลกอริทึมการประมาณ ค่า ^{[ 21 ] [ 22 ]}ปัญหาการครอบคลุมสูงสุดเป็นกรณีพิเศษของปัญหานี้${\displaystyle 1-1/e}$
3. ปัญหาของการเพิ่มค่าสูงสุดของฟังก์ชันย่อยแบบโมโนโทนภายใต้ ข้อจำกัด ของเมทริกซ์ (ซึ่งครอบคลุมกรณีข้างต้น) ยังยอมรับอัลกอริทึมการประมาณค่า อีกด้วย ^{[ 23 ] [ 24 ] [ 25 ]}${\displaystyle 1-1/e}$

อัลกอริทึมเหล่านี้จำนวนมากสามารถรวมเข้าด้วยกันได้ภายในกรอบงานอัลกอริทึมแบบกึ่งเชิงอนุพันธ์^{[ 18 ]}

นอกเหนือจากการหาค่าต่ำสุดและสูงสุดของฟังก์ชันซับโมดูลาร์แล้ว ยังมีปัญหาการหาค่าเหมาะสมที่สุดตามธรรมชาติอื่นๆ อีกหลายอย่างที่เกี่ยวข้องกับฟังก์ชันซับโมดูลาร์

1. การลดความแตกต่างระหว่างฟังก์ชันย่อยโมดูลาร์สองฟังก์ชัน^{[ 26 ]}ไม่เพียงแต่เป็นปัญหา NP-hard เท่านั้น แต่ยังไม่สามารถประมาณค่าได้อีกด้วย^{[ 27 ]}
2. การลด/เพิ่มค่าสูงสุดของฟังก์ชันซับโมดูลาร์ภายใต้ข้อ จำกัด เซตระดับ ซับโมดูลาร์ (เรียกอีกอย่างว่าการเพิ่มประสิทธิภาพซับโมดูลาร์ภายใต้ข้อจำกัดการครอบคลุมซับโมดูลาร์หรือข้อจำกัดกระเป๋าซับโมดูลาร์) ยอมรับการรับประกันการประมาณค่าแบบจำกัด^{[ 28 ]}
3. การแบ่งข้อมูลตามฟังก์ชันย่อยเพื่อเพิ่มสวัสดิภาพเฉลี่ยให้สูงสุดเรียกว่าปัญหาสวัสดิภาพย่อย ซึ่งยังยอมรับการรับประกันการประมาณค่าแบบมีขอบเขต (ดูการเพิ่มสวัสดิภาพให้สูงสุด )

ฟังก์ชันซับโมดูลาร์เกิดขึ้นตามธรรมชาติในแอปพลิเคชันในโลกแห่งความเป็นจริงหลายอย่าง เช่นเศรษฐศาสตร์ทฤษฎีเกม การเรียนรู้ ของเครื่องและคอมพิวเตอร์วิชั่น^{[ 4 ] [ 29 ]}รวมถึงปัญญาประดิษฐ์ ทั่วไป ^{[ 30 ]}เนื่องมาจากคุณสมบัติผลตอบแทนที่ลดลง ฟังก์ชันซับโมดูลาร์จึงจำลองต้นทุนของสินค้าได้อย่างเป็นธรรมชาติ เนื่องจากมักจะมีส่วนลดมากขึ้นเมื่อจำนวนสินค้าที่ซื้อเพิ่มขึ้น ฟังก์ชันซับโมดูลาร์จำลองแนวคิดของความซับซ้อน ความคล้ายคลึง และความร่วมมือเมื่อปรากฏในปัญหาการลดค่า ในทางกลับกัน ในปัญหาการเพิ่มค่า ฟังก์ชันเหล่านี้จะจำลองแนวคิดของความหลากหลาย ข้อมูล และความครอบคลุม

• ฟังก์ชันซูเปอร์โมดูลาร์
• แมทรอยด์ , โพลีแมทรอยด์
• ฟังก์ชันอรรถประโยชน์ของสินค้าที่แบ่งแยกไม่ได้

• เว็บไซต์ http://www.cs.berkeley.edu/~stefje/references.htmlมีบรรณานุกรมที่ยาวกว่า
• เว็บไซต์ http://submodularity.org/มีข้อมูลเพิ่มเติมเกี่ยวกับเรื่องนี้