💻 computer science

Differentially Private Submodular Maximization with a Knapsack Constraint

यह शोध पत्र नैपसैक बाधा (knapsack constraint) के तहत सबमॉड्यूलर मैक्सिमाइजेशन (submodular maximization) के लिए डिफरेंशियल प्राइवेट एल्गोरिदम प्रस्तुत करता है जो मोनोटोनिक और नॉन-मोनोटोनिक दोनों उद्देश्यों के लिए इष्टतम या निकट-इष्टतम सन्निकटन अनुपात (approximation ratios) प्राप्त करते हैं, जबकि पिछले कार्यों की तुलना में एडिटिव एरर (additive error) और क्वेरी जटिलता में महत्वपूर्ण सुधार करते हैं।

मूल लेखक: Ron Zadicario, Tova Milo

प्रकाशित 2026-06-16

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Ron Zadicario, Tova Milo

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

यहाँ "Differentially Private Submodular Maximization with a Knapsack Constraint" पेपर का एक सरल भाषा और रचनात्मक उपमाओं (analogies) के साथ अनुवाद दिया गया है।

बड़ी तस्वीर: "गुप्त रेसिपी" की समस्या

कल्पना कीजिए कि आप एक शेफ हैं जो सीमित सामग्री का उपयोग करके एक परफेक्ट डिश ("इष्टतम समाधान" या optimal solution) बनाने की कोशिश कर रहे हैं।

सामग्री (Ingredients): आपके पास एक विशाल भंडार (ground set) है जिसमें हजारों वस्तुएं हैं।
घटते प्रतिफल का नियम (The Rule of Diminishing Returns): यह "सबमॉड्यूलर" (submodular) वाला हिस्सा है। इसका मतलब है कि पहली प्याज डालने से स्वाद में बहुत उछाल आता है। दूसरी प्याज डालने से थोड़ा और स्वाद बढ़ता है, लेकिन दसवीं प्याज डालने से लगभग कोई फर्क नहीं पड़ता। सामग्री का मूल्य इस बात पर निर्भर करता है कि बर्तन में पहले से क्या मौजूद है।
बजट (The Budget): आपके पास एक सख्त बजट है (knapsack constraint)। कुछ सामग्रियां सस्ती हैं (जैसे नमक), जबकि कुछ महंगी हैं (जैसे केसर)। आप सब कुछ नहीं खरीद सकते; आपको वह संयोजन चुनना होगा जो आपके बटुए के अनुकूल हो और सबसे स्वादिष्ट हो।

लक्ष्य: वह विशिष्ट मिश्रण खोजना जो बजट से बाहर जाए बिना सबसे स्वादिष्ट व्यंजन बनाता है।

ट्विस्ट: गुप्त सामग्री सूची की सुरक्षा करना

अब, कल्पना कीजिए कि आपकी सामग्री की सूची केवल किराने की सूची नहीं है; यह आपके ग्राहकों का एक गुप्त मेडिकल रिकॉर्ड है।

यदि आप प्रकट करते हैं कि आपने कौन सी सामग्रियां चुनी हैं, तो एक हैकर यह पता लगा सकता है कि किसी विशिष्ट ग्राहक को कोई दुर्लभ एलर्जी या विशिष्ट बीमारी है।
डिफरेंशियल प्राइवेसी (Differential Privacy - DP): यह एक गणितीय "जादुई ढाल" (magic cloak) है। यह सुनिश्चित करता है कि जब आप अपना अंतिम व्यंजन दुनिया को दिखाते हैं, तो कोई भी यह नहीं बता सकता कि उस व्यंजन को बनाने में एक विशिष्ट ग्राहक के डेटा का उपयोग किया गया था या नहीं। रेसिपी लगभग वैसी ही दिखती है चाहे डेटाबेस में ग्राहक A मौजूद हो या न हो।

समस्या: आमतौर पर, जब हम रहस्यों को छिपाने के लिए इस "जादुगर की ढाल" को जोड़ते हैं, तो व्यंजन का स्वाद बिगड़ जाता है। गोपनीयता की रक्षा के लिए डाला गया 'शोर' (noise) स्वाद को खराब कर देता है। पिछले तरीके या तो बहुत धीमे थे (खाना पकाने में वर्षों लग जाते) या परिणामी व्यंजन खाने लायक भी नहीं था (बहुत कम गुणवत्ता वाला)।

यह पेपर क्या हासिल करता है

लेखक, रॉन ज़ाडिकारियो और टोवा मिलो ने नए एल्गोरिदम (रेसिपी) तैयार किए हैं जो इस समस्या को पहले की तुलना में बहुत बेहतर तरीके से हल करते हैं। उन्होंने दो प्रकार के कुकिंग परिदृश्यों को संबोधित किया है:

1. "हमेशा बेहतर" वाला परिदृश्य (Monotone)

इस परिदृश्य में, सामग्री जोड़ने से व्यंजन कभी खराब नहीं होता। हो सकता है कि इससे स्वाद बहुत ज्यादा न बढ़े, लेकिन यह इसे बिगाड़ेगा नहीं।

पुराना तरीका: पिछले तरीके हर संभव संयोजन को चखकर परफेक्ट रेसिपी का अनुमान लगाने जैसे थे। यह बहुत धीमा था और गोपनीयता सुरक्षा के कारण अंतिम व्यंजन का स्वाद बहुत खराब हो जाता था।
नया तरीका (एल्गोरिदम 2): उन्होंने एक ऐसा तरीका बनाया है जो इष्टतम (optimal) है। यह सैद्धांतिक रूप से सर्वश्रेष्ठ स्वाद (गणित में एक प्रसिद्ध बेंचमार्क जिसे $1 - 1/e$ $1 - 1/ e$ कहा जाता है) का 63% प्राप्त करता है।
- उपमा: कल्पना कीजिए कि आपके पास एक जादुई चखने वाला चम्मच (tasting spoon) है। हर एक संयोजन को चखने के बजाय (जिसमें बहुत समय लगता है), यह चम्मच बुद्धिमानी से सबसे आशाजनक संयोजनों का नमूना लेता है। यह ग्राहकों के रहस्यों को इतनी अच्छी तरह से सुरक्षित करता है कि रेसिपी में जोड़ा गया "शोर" बहुत कम होता है। परिणाम एक ऐसा व्यंजन है जो लगभग उतना ही स्वादिष्ट है जितना कि गैर-निजी संस्करण, लेकिन यह सुरक्षित है।
तेज़ तरीका (एल्गोरिदम 7): उन्होंने एक "तेज़" संस्करण भी बनाया है। यह पूरी तरह से परफेक्ट नहीं है (यह सर्वश्रेष्ठ स्वाद का 50% प्राप्त करता है), लेकिन यह अविश्वसनीय रूप से तेज़ है और फिर भी रहस्यों को सुरक्षित रखता है।

2. "कभी-कभी बुरा" वाला परिदृश्य (Non-Monotone)

इस परिदृश्य में, सामग्री जोड़ने से व्यंजन खराब हो सकता है। शायद बहुत अधिक लहसुन डालने से सूप का स्वाद बिगड़ सकता है। इसे हल करना कठिन है।

ब्रेकथ्रू: इस पेपर से पहले, इस पेचीदा परिदृश्य में गोपनीयता की रक्षा करते हुए एक अच्छा व्यंजन प्राप्त करने का कोई गणितीय रूप से प्रमाणित तरीका नहीं था।
नया तरीका (एल्गोरिदम 3): उन्होंने पहली बार एक ऐसा तरीका पेश किया है जो एक अच्छा परिणाम (सर्वश्रेष्ठ स्वाद का 25%) सुनिश्चित करता है जबकि गोपनीयता की रक्षा भी करता है।
- उपमा: इसे एक "टॉस-अप" (तौले-बाँटे गए) रणनीति के रूप में सोचें। एल्गोरिदम एक संभावित सामग्री चुनता है, एक सिक्का उछालता है, और कभी-कभी यह तय करता है कि भले ही वह अच्छी दिख रही हो, उसका उपयोग नहीं करना है। यह यादृच्छिकता (randomness) रहस्यों को छिपाने में मदद करती है। फिर, अंत में, यह सभी "लगभग" बने व्यंजनों को देखता है और सबसे अच्छे को चुनता है। यह एक चतुर जुआ है जो सफल होता है।

यह क्यों महत्वपूर्ण है (पेपर के अनुसार)

पेपर यह दावा नहीं करता है कि ये एल्गोरिदम सीधे तौर पर बीमारियों का इलाज करेंगे या आपके व्यवसाय को चलाएंगे। इसके बजाय, यह गणित और दक्षता पर ध्यान केंद्रित करता है:

बेहतर स्वाद (Utility): उनके एल्गोरिदम ऐसे परिणाम देते हैं जो पिछले गोपनीयता तरीकों की तुलना में "परफेक्ट डिश" के बहुत करीब होते हैं। "त्रुटि" (कि व्यंजन कितना खराब हो जाता है) काफी कम है।
तेज़ कुकिंग (Query Complexity): उन्होंने एल्गोरिदम को कितनी बार सामग्रियों को "चखने" (डेटा को क्वेरी करने) की आवश्यकता होती है, इसे कम कर दिया है।
- उपमा: पुराने तरीके को एक अच्छा व्यंजन खोजने के लिए 1,000,000 संयोजनों को चखने की आवश्यकता हो सकती थी। उनका नया तरीका केवल 1,000 बार में काम कर सकता है। यह इसे उन विशाल डेटासेट्स पर उपयोग करना संभव बनाता है जिन्हें पहले प्रोसेस करना बहुत धीमा था।
अपने आप में पहला (First of its Kind): पेचीदा "नॉन-मोनोटोन" मामले के लिए (जहाँ सामग्रियां व्यंजन को खराब कर सकती हैं), वे पहले हैं जिन्होंने सख्त गोपनीयता नियमों के तहत काम करने वाला गणितीय रूप से गारंटीकृत समाधान प्रदान किया है।

संक्षेप में

इस पेपर को एक मास्टर शेफ के रूप में समझें जिसने ग्राहकों की पहचान उजागर किए बिना, गुप्त सामग्री सूची का उपयोग करके एक शानदार भोजन बनाना सीख लिया है।

पहले: आपको या तो एक तेज़ लेकिन असुरक्षित भोजन या एक धीमा लेकिन खराब स्वाद वाला सुरक्षित भोजन चुनना पड़ता था।
अब: वे एक ऐसा मेनू पेश करते हैं जहाँ आप एक ऐसा भोजन प्राप्त कर सकते हैं जो दोनों है—सुरक्षित (गणितीय रूप से प्रमाणित गोपनीयता) और स्वादिष्ट (उच्च गुणवत्ता वाला), और इसे पहले की तुलना में बहुत तेज़ी से बनाया जा सकता है। उन्होंने यह भी पता लगाया है कि सबसे कठिन और अप्रत्याशित रेसिपी (जहाँ सामग्रियां आपस में टकरा सकती हैं) के लिए यह कैसे किया जाए।

तकनीकी सारांश: नैपसैक बाधा के साथ विभेदक रूप से निजी उपमोड्यूलर सरलीकरण (Differentially Private Submodular Maximization with a Knapsack Constraint)

1. समस्या की परिभाषा

यह शोधपत्र डिफरेंशियल प्राइवेसी (DP) के ढांचे के तहत नैपसैक बाधा के साथ उपमोड्यूलर सरलीकरण (SMK) समस्या को संबोधित करता है।

SMK संदर्भ: $n$ तत्वों के एक ग्राउंड सेट $N$ को देखते हुए, एक उपमोड्यूलर ऑब्जेक्टिव फंक्शन $f: 2^N \to \mathbb{R}$ , एक लागत फंक्शन $c: N \to \mathbb{R}_{>0}$ , और एक बजट $B$ दिया गया है, लक्ष्य एक ऐसा उपसमुच्चय $S \subseteq N$ खोजना है ताकि $\sum_{v \in S} c(v) \leq B$ हो और $f(S)$ अधिकतम हो। यह समस्या NP-hard है और फीचर सिलेक्शन, डेटा समराइजेशन, और इन्फ्लुएंस मैक्सिमाइजेशन जैसे मशीन लर्निंग अनुप्रयोगों में सर्वव्यापी है।
प्राइवेसी सेटिंग: ऑब्जेक्टिव फंक्शन $f_D$ एक संवेदनशील डेटासेट $D$ पर निर्भर करता है। एल्गोरिदम को एक समाधान $S$ आउटपुट करना चाहिए जो $(\epsilon, \delta)$ -डिफरेंशियल प्राइवेसी को संतुष्ट करता हो, यह सुनिश्चित करते हुए कि $D$ में किसी एक व्यक्ति के डेटा को बदलने पर आउटपुट वितरण नगण्य रूप से बदलता है।
क्षेत्र (Scope): यह कार्य मोनोटोन (monotone) और नॉन-मोनोटोन (non-monotone) दोनों प्रकार के ऑब्जेक्टिव फंक्शन्स पर विचार करता है।

2. कार्यप्रणाली और तकनीकी चुनौतियाँ

लेखक पहचानते हैं कि मानक DP उपमोड्यूलर मैक्सिमाइजेशन तकनीकें (जो अक्सर कार्डिनैलिटी बाधाओं के लिए डिज़ाइन की जाती हैं) नैपसैक बाधाओं के लिए इष्टतम नहीं हैं क्योंकि इसके दो प्राथमिक कारण हैं:

घनत्व स्कोर (Density Scores) की परिवर्तनशील संवेदनशीलता (Varying Sensitivity): नैपसैक सेटिंग्स में, एल्गोरिदम आमतौर पर "घनत्व" (सीमांत लाभ विभाजित लागत) के आधार पर तत्वों का चयन करते हैं। कार्डिनैलिटी बाधाओं के विपरीत जहाँ संवेदनशीलता समान होती है, एक घनत्व स्कोर $f(u|S)/c(u)$ की संवेदनशीलता तत्व की लागत $c(u)$ के व्युत्क्रमानुपाती होती है। मानक चयन तंत्रों (जैसे एक्सपोनेंशियल मैकेनिज्म) का एक सरल अनुप्रयोग $\Delta f \cdot (B/c_{\min})$ के समान एक योगात्मक त्रुटि (additive error) उत्पन्न करेगा, जिससे अधिकतम व्यवहार्य समाधान आकार $k$ के सापेक्ष एक उप-इष्टतम निर्भरता होगी।
- समाधान: लेखक जनरलाइज्ड रिपोर्ट नोइजी मैक्स (GRNM) मैकेनिज्म (Raskhodnikova & Smith, 2016) का उपयोग करते हैं। यह मैकेनिज्म व्यक्तिगत उम्मीदवार संवेदनशीलता के अनुकूल होता है, यह सुनिश्चित करता है कि योगात्मक त्रुटि सबसे खराब स्थिति वाले बाउंड के बजाय चयनित उम्मीदवार की विशिष्ट संवेदनशीलता के साथ स्केल करे।
कंपोजिशन बॉटलनेक (Composition Bottleneck): मोनोटोन SMK (जैसे Two-Guess-Greedy) के लिए अत्याधुनिक गैर-निजी एल्गोरिदम को इष्टतम तत्वों का अनुमान लगाने के लिए $O(n^2)$ पुनरावृत्तियों (iterations) की आवश्यकता होती है। मानक एडवांस्ड कंपोजिशन थ्योरम के परिणामस्वरूप त्रुटि का पद $n$ के साथ बहुपद (polynomially) रूप से बढ़ेगा, जो प्राइवेसी के लाभों को समाप्त कर देगा।
- समाधान: लेखक जनरलाइज्ड प्राइवेट सिलेक्शन फ्रेमवर्क (Cohen et al., 2023) का लाभ उठाते हैं। प्रत्येक एन्यूमरेशन स्टेप को कितनी बार बुलाया जाता है, इसे रैंडमाइज करके, वे प्राइवेसी लॉस को कुल सब-रूटीन की संख्या से अलग कर देते हैं, जिससे $n$ पर पॉलीलॉगारिदमिक (polylogarithmic) निर्भरता के साथ एक योगात्मक त्रुटि प्राप्त होती है।

3. मुख्य योगदान और एल्गोरिदम

A. मोनोटोन ऑब्जेक्टिव फंक्शन्स

शोधपत्र मोनोटोन मामले के लिए दो एल्गोरिदम प्रस्तावित करता है:

DP-2GG (एल्गोरिदम 2): यह "टू-गेस-ग्रीडी" एल्गोरिदम (Feldman et al., 2023) का एक डिफरेंशियल प्राइवेट अनुकूलन है।
- मैकेनिज्म: यह आकार में 2 या उससे कम के सभी उपसमुच्चयों $Y \subseteq N$ पर पुनरावृत्ति करता है। प्रत्येक $Y$ के लिए, यह अवशेष (residual) इंस्टेंस पर एक प्राइवेज़्ड डेंसिटी-ग्रीडी सबरूटीन (एल्गोरिदम 1) चलाता है। अंतिम समाधान इन सब-रूटीन्स के नॉइजी आउटपुट से चुना जाता है।
- गारंटी: एक $(1 - 1/e)$ -अनुमान (approximation) प्राप्त करता है।
- जटिलता (Complexity): $O(\beta^{-1} n^3 k)$ ऑरेकल क्वेरीज़।
- त्रुटि (Error): योगात्मक त्रुटि $O(\frac{\Delta k^{1.5}}{\epsilon} \sqrt{\log n} \dots)$ के रूप में स्केल करती है, जो $n$ और $1/c_{\min}$ पर बहुपद निर्भरता को हटाकर पिछले कार्यों की तुलना में सुधार करती है।
DP-DG+ (एल्गोरिदम 7): यह डेनसिटी-ग्रीडी+ पर आधारित एक तेज़, सिंगल-पास एल्गोरिदम है।
- मैकेनिज्म: यह एक बार प्राइवेज़्ड डेनसिटी-ग्रीडी पास निष्पादत करता है और आंशिक समाधानों और उनके व्यवहार्य सिंगल-एलिमेंट एक्सटेंशन के बीच सर्वश्रेष्ठ समाधान चुनता है।
- गारंटी: $1/2$ -अनुमान प्राप्त करता है।
- जटिलता: $O(nk)$ ऑरेकल क्वेरीज़।
- त्रुटि: मोनोटोन मामले के तुलनीय सुधरा हुआ योगात्मक त्रुटि।

B. नॉन-मोनोटोन ऑब्जेक्टिव फंक्शन्स

शोधपत्र नॉन-मोनोटोन SMK के लिए प्रमाणित गारंटियों के साथ पहला डिफरेंशियल प्राइवेट एल्गोरिदम पेश करता है।

एल्गोरिदम: DP-SDG (एल्गोरिदम 3), जो नॉन-प्राइवेट SmkRan एल्गोरिदम (Han et al., 2021) का एक प्राइवेज़्ड अनुकूलन है।
मैकेनिज्म: यह GRNM का उपयोग करके डेंसिटी-आधारित चयन करता है। नॉन-मोनोटोनिटी को संभालने के लिए चुने गए तत्वों को $1/2$ की संभावना के साथ समाधान में जोड़ा जाता है (रैंडमाइज्ड डिसकार्डिंग)। महत्वपूर्ण रूप से, यह तब भी पुनरावृत्ति जारी रखता है जब सीमांत लाभ (marginal gains) नकारात्मक हो जाते हैं (शोर के कारण), और सभी आंशिक समाधानों और उनके एक्सटेंशन से सर्वश्रेष्ठ देखे गए समाधान को चुनने के लिए RNM का उपयोग करता है।
प्राइवेसी विश्लेषण: चयन चरणों की अनिश्चितता को संभालने के लिए, लेखक एक कॉन्सेंट्रेशन बाउंड (concentration bound) निकालते हैं जो दिखाता है कि कुल पुनरावृत्तियाँ ज्यामितीय यादृच्छिक चरों (geometric random variables) के योग द्वारा स्टोकेस्टिक रूप से डोमिनेटेड हैं, जो $O(k)$ के आसपास केंद्रित होती हैं।
गारंटी: अपेक्षा (expectation) में $1/4$ -अनुमान प्राप्त करता है।
जटिलता: $O(nk)$ ऑरेकल क्वेरीज़।
त्रुटि: योगात्मक त्रुटि मोनोटोन मामले के समान है।

4. परिणाम और अनुभवजन्य मूल्यांकन (Empirical Evaluation)

सैद्धांतिक परिणाम

लेखक टेबल 1 में अपने परिणामों की तुलना पिछले कार्य (विशेष रूप से Sadeghi & Fazel, 2021) के विरुद्ध करते हैं। प्रमुख सुधारों में शामिल हैं:

अनुमान अनुपात (Approximation Ratios): सर्वोत्तम ज्ञात नॉन-प्राइवेट अनुपातों ( $(1-1/e)$ मोनोटोन के लिए, $1/4$ नॉन-मोनोटोन के लिए) से मेल खाना।
योगात्मक त्रुटि (Additive Error): ग्राउंड सेट के आकार $n$ (पॉलिलॉगारिदमिक बनाम बहुपद) और अधिकतम व्यवहार्य समाधान आकार $k$ (पिछले कार्यों की तुलना में $k^{1.5}$ के रूप में स्केल करना) पर काफी बेहतर निर्भरता।
क्वेरी जटिलता (Query Complexity): $n$ और $k$ में बहुपद, जबकि मोनोटोन SMK के लिए पिछले कार्य मल्टीलिनियर एक्सटेंशन के सटीक मूल्यांकन पर $O(2^n)$ क्वेरीज़ पर निर्भर थे।

अनुभवजन्य परिणाम

एल्गोरिदम का मूल्यांकन मैनहट्टन में 100,000 उबर पिकअप लोकेशंस के डेटासेट का उपयोग करके एक राइड-शेयरिंग ऑप्टिमाइजेशन टास्क पर किया गया।

उपयोगिता (Utility): $\epsilon \geq 0.1$ के लिए, DP एल्गोरिदम (DP-2GG, DP-DG+, DP-SDG) अपने नॉन-प्राइवेट समकक्षों (2GG, DG+, SmkRan) के तुलनीय उपयोगिता प्राप्त करते हैं, जो रैंडम बेसलाइन से काफी बेहतर प्रदर्शन करते हैं। $\epsilon=0.2$ पर, DP-2GG नॉन-प्राइवेट 2GG के 2% के भीतर है।
स्केलेबिलिटी (Scalability): DP-DG+ और DP-SDG, ग्राउंड सेट के आकार $n$ के संबंध में ऑरेकल क्वेरीज़ में रैखिक वृद्धि प्रदर्शित करते हैं, जो अधिक क्वेरी-गहन DP-2GG की तुलना में उनकी व्यावहारिक दक्षता की पुष्टि करता है।

5. महत्व और दावे

शोधपत्र डिफरेंशियल प्राइवेसी के तहत कॉम्बिनेटरियल ऑप्टिमाइजेशन के संबंध में साहित्य के महत्वपूर्ण अंतराल को भरने का दावा करता है:

पहला प्रमाणित नॉन-मोनोटोन SMK: यह नॉन-मोनोटोन SMK के लिए डिफरेंशियल प्राइवेसी के तहत पहले प्रमाणित गारंटी स्थापित करता है।
बेहतर मोनोटोन बाउंड्स: यह मोनोटोन SMK एल्गोरिदम की उपयोगिता (योगात्मक त्रुटि) और क्वेरी जटिलता दोनों में सुधार करता है, जो पिछले दृष्टिकोणों की घातीय (exponential) क्वेरी जटिलता से दूर ले जाता है।
नैपसैक बाधाओं को संभालना: यह प्रदर्शित करता है कि नैपसैक बाधाओं (परिवर्तनशील संवेदनशीलता और कंपोजिशन बॉटलनेक) की विशिष्ट चुनौतियों को जनरलाइज्ड सिलेक्शन मैकेनिज्म और कॉन्सेंट्रेशन बाउंड्स का उपयोग करके दूर किया जा सकता है, जिससे ऐसे परिणाम प्राप्त होते हैं जो कार्डिनैलिटी-प्रतिबंधित सेटिंग्स की दक्षता से मेल खाते हैं।

लेखक नोट करते हैं कि जबकि उनकी योगात्मक त्रुटि की निर्भरता $k$ पर कार्डिनैलिटी-प्रतिबंधित सेटिंग्स में बहुपद-समय एल्गोरिदम के लिए सर्वोत्तम ज्ञात स्तर से मेल खाती है, यह प्रश्न खुला है कि क्या बाउंडेड सेंसिटिविटी के तहत $k$ पर बेहतर निर्भरता प्राप्त की जा सकती है। वे इन तकनीकों को मैट्रॉइड बाधाओं के साथ संयुक्त नैपसैक बाधाओं तक विस्तारित करने को भविष्य के कार्य के रूप में भी सुझाते हैं।