एलपी-प्रकार की समस्या

कलन विधि (एल्गोरिदम) के अध्ययन में एलपी-प्रकार की समस्या (जिसे सामान्यीकृत रैखिक प्रोग्रामिंग भी कहा जाता है) एक अनुकूलन समस्या है जो निम्न-आयामी रैखिक प्रोग्राम के साथ कुछ गुण साझा करती है और जो समान एल्गोरिदम द्वारा हल की जा सकती है। एलपी-प्रकार की समस्याओं में कई महत्वपूर्ण अनुकूलन समस्याएं सम्मिलित हैं जो स्वयं रैखिक प्रोग्राम नहीं हैं, जैसे कि प्लानर बिंदुओं के दिए गए संग्रह की सबसे छोटे वृत्त को खोजने की समस्या, उन्हें यादृच्छिक एल्गोरिदम के संयोजन द्वारा हल किया जा सकता है जो समस्या को परिभाषित करने वाले तत्वों की संख्या में रैखिक है और समस्या के आयाम में उप-घातीय है।

परिभाषा

एलपी-प्रकार की समस्याओं को शारिर & और वेल्ज़ल (1992) द्वारा परिभाषित किया गया था, जिसमें एक को निवेश के रूप में तत्वों का परिमित संग्रह S दिया जाता है और फलन f जो पूरी तरह से अनुक्रम किए गए संग्रह से मूल्यों के लिए S के उप-समूचय को मानचित्र करता है। दो प्रमुख गुणों को संतुष्ट करने के लिए फलन आवश्यक है:

• मोनोटोनिकिटी: प्रत्येक दो संग्रह A ⊆ B ⊆ S, f(A) ≤ f(B) ≤ f(S) के लिए
• स्थानीयता: प्रत्येक दो संग्रह A ⊆ B ⊆ S और S में प्रत्येक तत्व x के लिए अगर f(A) = f(B) = f(A ∪ {x}) है तो f(A) = f(B ∪ {x}).

एलपी-प्रकार की समस्या का आधार एक संग्रह B ⊆ S उस गुण के साथ है कि B के प्रत्येक उचित उपसमुच्चय में B की तुलना में f का छोटा मान होता है और एलपी-प्रकार की समस्या के आयाम (या संयोजक आयाम) को आधार की अधिकतम प्रमुखता के रूप में परिभाषित किया गया है।

यह माना जाता है कि एक अनुकूलन एल्गोरिदम फलन f का मूल्यांकन केवल उन संग्रहों पर कर सकता है जो स्वयं आधार हैं या जो किसी एक तत्व को आधार में जोड़कर बनते हैं। वैकल्पिक रूप से, एल्गोरिथम को दो आदिम संचालनों तक सीमित किया जा सकता है: एक उल्लंघन परीक्षण जो आधार B और तत्व x के लिए निर्धारित करता है कि क्या f(B) = f(B ∪ {x}) और आधार संगणना जो (उसी निवेश के साथ) B ∪ {x}का आधार पाता है, एल्गोरिथम के प्रदर्शन का कार्य केवल इन प्रतिबंधित मूल्यांकनों या आदिमों का उपयोग करके f(S) का मूल्यांकन करना है।

उदाहरण और अनुप्रयोग

LP बॉल्स

एक रेखीय प्रोग्राम को d गैर-नकारात्मक वास्तविक चर की एक प्रणाली द्वारा परिभाषित किया जा सकता है, जो n रैखिक असमानता बाधाओं के अधीन है, साथ में एक गैर-नकारात्मक रैखिक उद्देश्य फलन को कम किया जा सकता है। इसे एलपी-प्रकार की समस्याओं के ढांचे में रखा जा सकता है S को बाधाओं का संग्रह होने और f(A) (बाधाओं के एक उप-समूचय A के लिए) को परिभाषित करके छोटे रैखिक प्रोग्राम का न्यूनतम उद्देश्य फलन Aके रूप में परिभाषित किया जा सकता है। उपयुक्त सामान्य स्थिति धारणाओं के साथ (एक ही इष्टतम उद्देश्य फलन मान वाले एकाधिक समाधान बिंदुओं को रोकने के लिए) यह एलपी-प्रकार की समस्या की मोनोटोनिकिटी और स्थानीयता आवश्यकताओं को पूरा करता है और चर के संख्या d के बराबर संयोजी आयाम है। इसी तरह एक पूर्णांक प्रोग्राम (रैखिक बाधाओं के संग्रह और एक रैखिक उद्देश्य फलन रैखिक प्रोग्राम के रूप में, लेकिन अतिरिक्त प्रतिबंध के साथ कि चर को केवल पूर्णांक मान लेना चाहिए) मोनोटोनिकिटी और स्थानीयता गुणों दोनों को संतुष्ट करता है एल-पी प्रकार की समस्या, रैखिक प्रोग्रामों के लिए समान सामान्य स्थिति मान्यताओं के साथ बेल (1977) और स्कार्फ (1977) के प्रमेयों से पता चलता है कि d चर के साथ एक पूर्णांक प्रोग्राम के लिए संयोजन आयाम अधिकतम 2^dहैं।

कम्प्यूटेशनल ज्यामिति में कई प्राकृतिक अनुकूलन समस्याएं एलपी-प्रकार हैं:

सबसे छोटी वृत्त समस्या

* सबसे छोटी वृत्त समस्या एक वृत्त की न्यूनतम त्रिज्या ज्ञात करने की समस्या है जिसमें तल में n बिंदुओं का एक संग्रह दिया गया है, यह मोनोटोनिकिटी को संतुष्ट करता है (अधिक अंक जोड़ने से केवल वृत्त बड़ा हो सकता है) और स्थानीयता (यदि संग्रह सबसे छोटा वृत्त A के लिए सबसे छोटे वृत्त में B और x सम्मिलित हैं, तो उसी वृत्त में B ∪ {x}) भी सम्मिलित है) क्योंकि सबसे छोटा वृत्त हमेशा कुछ तीन बिंदुओं द्वारा निर्धारित किया जाता है, सबसे छोटी वृत्त समस्या में संयोजी आयाम तीन होता है, भले ही इसे द्वि-आयामी यूक्लिडियन ज्यामिति का उपयोग करके परिभाषित किया गया हो। अधिकांश d आयामों में बिंदुओं की सबसे छोटी संलग्न गेंद संयोजी आयाम d + 1 की एलपी-प्रकार की समस्या बनाती है। छोटी वृत्त समस्या को गेंदों के एक संग्रह को घेरने वाली सबसे छोटी वृत्त के लिए सामान्यीकृत किया जा सकता है, सबसे छोटी गेंद के लिए जो गेंदों के प्रत्येक संग्रह को छूती या घेरती है भारित 1-केंद्र समस्या के लिए या गैर-यूक्लिडियन स्थानों में इसी तरह की छोटी संलग्न गेंद की समस्याओं के लिए जैसे कि ब्रेगमैन डायवर्जेंस द्वारा परिभाषित दूरी के साथ स्पेस। सबसे छोटे घेरने वाले दीर्घवृत्ताभ को खोजने की संबंधित समस्या भी एक एलपी-प्रकार की समस्या है, लेकिन एक बड़े संयोजी आयाम d(d + 3)/2के साथ।

• मान लीजिए K₀, K₁, ... d-आयामी यूक्लिडियन स्पेस में n उत्तल संग्रह का अनुक्रम बनें और मान लीजिए कि हम इस अनुक्रम का सबसे लंबा उपसर्ग (कंप्यूटर विज्ञान) खोजना चाहते हैं जिसमें एक सामान्य चौराहा बिंदु हो, इसे एलपी-प्रकार की समस्या के रूप में व्यक्त किया जा सकता है जिसमें f(A) = −i जहां K_i A का पहला सदस्य है जो A के एक अन्तर्विभाजक उपसर्ग से संबंधित नहीं है और जहां f(A) = −n यदि ऐसा कोई सदस्य नहीं है। इस प्रणाली का संयोजन आयाम d + 1है।
• मान लीजिए कि हमें त्रि-आयामी स्पेस में अक्ष-संरेखित आयताकार बक्से का एक संग्रह दिया गया है और स्पेस के सकारात्मक ऑक्टेंट में निर्देशित एक रेखा खोजना चाहते हैं जो सभी बक्से के माध्यम से कटती है। इसे मिश्रित आयाम 4 के साथ एलपी-प्रकार की समस्या के रूप में व्यक्त किया जा सकता है।
• दो उत्तल पॉलीटोप्स के बीच निकटतम दूरी खोजने की समस्या उनके संग्रह के शिखर द्वारा निर्दिष्ट, एलपी-प्रकार की समस्या के रूप में प्रदर्शित की जा सकती है। इस सूत्रीकरण में संग्रह S दोनों पॉलीटोप्स में सभी कोने का संग्रह है और फलन मूल्य f(A) दो पॉलीटोप्स में दो सबसंग्रह A के उत्तल वर्टिकल के बीच सबसे छोटी दूरी की उपेक्षा है। समस्या का संयोजी आयाम d + 1 है यदि दो पॉलीटॉप असंयुक्त हैं या दो बहुशीर्ष या d + 2 यदि उनके पास एक गैर-रिक्त चौराहा है।*मान लीजिए कि S = {f₀, f₁, ...} क्वासिकोनवेक्स फलन का समुच्चय है फिर बिंदुवार अधिकतम max_i f_i स्वयं क्वासिकॉनवेक्स है और max_i f_i का न्यूनतम मूल्य खोजने की समस्या एक एलपी-प्रकार की समस्या है। इसमें अधिकतम संयोजनात्मक आयाम है 2d + 1है जहां d कार्यों के डोमेन का आयाम है, लेकिन पर्याप्त रूप से सुचारू कार्यों के लिए अधिकतम d + 1 संयोजी आयाम छोटा है, कई अन्य एलपी-प्रकार की समस्याओं को भी इस तरह क्वासिकोनवेक्स कार्यों का उपयोग करके व्यक्त किया जा सकता है उदाहरण के लिए, सबसे छोटी संलग्न वृत्त समस्या max_i f_i को न्यूनतम करने की समस्या है, जहां प्रत्येक कार्य f_i दिए गए बिंदुओं में से किसी एक से यूक्लिडियन दूरी को मापता है।

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

एल्गोरिदम

सीडेल

सीडेल (1991) ने निम्न-आयामी रैखिक प्रोग्रामिंग के लिए एक एल्गोरिदम दिया जिसे एलपी-प्रकार की समस्या ढांचे में अनुकूलित किया जा सकता है। सेडेल का एल्गोरिदम निवेश के रूप में संग्रह S और एक अलग संग्रह X (प्रारंभिक रूप से खाली) को इष्टतम आधार से संबंधित तत्वों के रूप में लेता हैं। इसके बाद यह शेष तत्वों को एक-एक करके एक यादृच्छिक क्रम में मानता है प्रत्येक के लिए उल्लंघन परीक्षण करता है और परिणाम के आधार पर ज्ञात आधार तत्वों के एक बड़े संग्रह के साथ एक ही एल्गोरिथ्म के लिए एक पुनरावर्ती कॉल करता है। इसे निम्नलिखित स्यूडोकोड के साथ व्यक्त किया जा सकता है:

फलन   सीडेल(S, f, X) है
    आर := खाली समुच्चय
    बी := एक्स
    S के यादृच्छिक क्रमपरिवर्तन में x के लिए:
        अगर f(B) ≠ f(B ∪ {x}):
            बी := सीडेल(आर, एफ, एक्स ∪ {x})
        आर := आर ∪ {x}
    वापसी बी

संयोजी आयाम d के साथ एक समस्या में एल्गोरिथम के iवें पुनरावृत्ति में उल्लंघन परीक्षण केवल तभी विफल होता है जब x d − |X| शेष आधार तत्व, जो प्रायिकता के साथ अधिक से अधिक होता है (d − |X|)/iहोता है, इस गणना के आधार पर यह दिखाया जा सकता है कि एल्गोरिथम द्वारा किए गए उल्लंघन परीक्षणों की कुल अपेक्षित संख्या O(d! n) n में रैखिक है लेकिन dघातीय से भी खराब है।

क्लार्कसन

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

फलन     पुनरावर्ती (एस, एफ) है
    X := खाली संग्रह  
    दोहराना
        R := आकार d√n के साथ S का एक यादृच्छिक उपसमुच्चय
        बी := आर के लिए आधार ∪ एक्स, रिकर्सिवली परिकलित
        व := {x | एफ(बी) ≠ एफ(बी ∪ {x})}
        एक्स := एक्स ∪ वी
    जब तक वी खाली न हो जाए
    वापसी बी

प्रत्येक पुनरावृत्ति में V का अपेक्षित आकार O(√n)है और जब भी V खाली नहीं होता है, तो इसमें S के अंतिम आधार का कम से कम एक नया तत्व सम्मिलित होता है इसलिए, एल्गोरिथ्म अधिकांश विचलन पर प्रदर्शन करता है, प्रत्येक n उल्लंघन परीक्षण करता है और O(d√n)आकार की एक उप-समस्या के लिए एकल पुनरावर्ती कॉल करता है।

क्लार्कसन का पुनरावृत्त एल्गोरिथ्म Sके प्रत्येक तत्व को भार प्रदान करता है, प्रारंभ में वे सभी बराबर होते हैं इसके बाद यह यादृच्छिक रूप से S से 9d² तत्वों का एक संग्रह R चुनता है और पिछले एल्गोरिथम की तरह संग्रह B और V की गणना करता है। यदि V का कुल वजन S के कुल वजन का अधिकतम 2/(9d − 1) गुना है (जैसा कि निरंतर प्रायिकता के साथ होता है) तब एल्गोरिथ्म V के प्रत्येक तत्व के भार को दोगुना कर देता है और पहले की तरह यह इस प्रक्रिया को तब तक दोहराता है V खाली हो जाता है। प्रत्येक पुनरावृत्ति में, इष्टतम आधार का वजन S के कुल वजन की तुलना में अधिक दर से बढ़ने के लिए दिखाया जा सकता है जिससे यह अनुसरण करता है कि एल्गोरिथम को O(log n) पुनरावृत्तियों के भीतर समाप्त होना चाहिए।

किसी दिए गए समस्या को हल करने के लिए पुनरावर्ती एल्गोरिदम का उपयोग करके पुनरावर्ती कॉल के लिए पुनरावृत्ति एल्गोरिदम पर स्विच करना और फिर पुनरावृत्त एल्गोरिदम द्वारा की गई कॉल के लिए सेडेल के एल्गोरिदम पर स्विच करना संभव है, यह संभव है कि O का उपयोग करके दी गई एलपी-प्रकार की समस्या को हल किया जाए O(dn + d! d^O(1) log n) उल्लंघन परीक्षण।

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

माटूसेक, शारिर और वेलज़ल

माटूसेक, शारिर और & वेलज़ल (1996) एक एल्गोरिदम का वर्णन करता है जो रैखिक प्रोग्रामों की एक अतिरिक्त गुण का उपयोग करता है जो हमेशा अन्य एलपी-प्रकार की समस्याओं से नहीं होता है, कि सभी आधारों में एक दूसरे की समान प्रमुखता होती है। यदि किसी एलपी-प्रकार की समस्या में यह गुण नहीं है, तो इसे d नए डमी तत्वों को जोड़कर और फलन f को संशोधित करके इसके पुराने मान f(A) और संख्या का min(d,|A|) कोषगत रूप का आदेश दिया।

एक समय में S के तत्वों को जोड़ने या तत्वों के नमूने खोजने के बजाय माटूसेक, शारिर & और वेलज़ल (1996) एक एल्गोरिथ्म का वर्णन करते हैं जो एक समय में तत्वों को हटा देता है। प्रत्येक चरण में यह एक आधार C रखता है जो प्रारंभ में डमी तत्वों का संग्रह हो सकता है। इसे निम्नलिखित स्यूडोकोड के साथ वर्णित किया जा सकता है:

फलन     msw(S, f, C) है
    अगर एस = सी तो
        वापसी सी
    S \ C का एक यादृच्छिक तत्व x चुनें
    बी = एमएसडब्ल्यू (एस \ एक्स, एफ, सी)
    अगर f(B) ≠ f(B ∪ {x}) तो
        बी := आधार(बी ∪ {x})
        बी := एमएसडब्ल्यू(एस, एफ, बी)
    वापसी बी

एल्गोरिथम के अधिकांश पुनरावर्ती कॉलों में उल्लंघन परीक्षण सफल होता है और यदि कथन छोड़ दिया जाता है। हालाँकि, एक छोटी सी संभावना के साथ उल्लंघन परीक्षण विफल हो जाता है और एल्गोरिथ्म एक अतिरिक्त आधार संगणना और फिर एक अतिरिक्त पुनरावर्ती कॉल करता है जैसा कि लेखक दिखाते हैं, एल्गोरिदम के लिए अपेक्षित समय 'n' में रैखिक है और d log nके वर्ग मार्ग में घातीय है इस पद्धति को क्लार्कसन की पुनरावर्ती और पुनरावृत्ति प्रक्रियाओं के साथ जोड़कर समय निर्भरता के इन दो रूपों को एक दूसरे से अलग किया जा सकता है, जिसके परिणामस्वरूप एक एल्गोरिथ्म होता है जो बाहरी पुनरावर्ती एल्गोरिथ्म O(dn) में उल्लंघन परीक्षण करता है और एक संख्या जो कि घातीय का वर्गमूल d log d एल्गोरिथम के निचले स्तरों में।

रूपांतर

बाहरी परतों के साथ अनुकूलन

माटूसेक (1995) एलपी-प्रकार की अनुकूलन समस्याओं की भिन्नता पर विचार करता है जिसमें संग्रह के साथ S दिया जाता है और उद्देश्य फलन fएक संख्या k कार्य शेष संग्रह पर जितना संभव हो उतना छोटा उद्देश्य कार्य करने के लिए S से k तत्वों को निकालना है। उदाहरण के लिए, जब सबसे छोटी वृत्त समस्या पर लागू किया जाता है तो यह सबसे छोटा वृत्त देता है जिसमें समतल बिंदुओं के दिए गए संग्रह k के अलावा सभी सम्मिलित होते हैं। वह दिखाता है कि सभी गैर-पतित एलपी-प्रकार की समस्याओं के लिए (अर्थात, ऐसी समस्याएं जिनमें सभी आधारों के अलग-अलग मूल्य हैं) इस समस्या को O(nk^d) समय में हल किया जा सकता है O(k^d) एलपी-प्रकार के एक संग्रह को हल करके S के उप-समूचय द्वारा परिभाषित समस्याएं।

निहित समस्याएं

कुछ ज्यामितीय अनुकूलन समस्याओं को एलपी-प्रकार की समस्याओं के रूप में व्यक्त किया जा सकता है जिसमें एलपी-प्रकार के निर्माण में तत्वों की संख्या अनुकूलन समस्या के लिए निवेश डेटा मानों की संख्या से काफी अधिक है। एक उदाहरण के रूप में सतह में nबिंदुओं के संग्रह पर विचार करें, जिनमें से प्रत्येक स्थिर वेग से गतिमान है। किसी भी समय इस प्रणाली का व्यास इसके दो बिंदुओं के बीच की अधिकतम दूरी है। उस समय को खोजने की समस्या जिस पर व्यास को कम किया जा सकता है, बिंदुवार O(n²) अर्ध-उत्तल कार्यों को न्यूनतम करने के रूप में तैयार किया जा सकता है, प्रत्येक जोड़ी बिंदुओं के लिए एक समय के एक फलन के रूप में जोड़ी के बीच यूक्लिडियन दूरी को मापता है इस प्रकार इसे O(n²) तत्वों के एक संग्रह पर संयोजी आयाम दो की LP-प्रकार की समस्या के रूप में हल किया जा सकता है, लेकिन यह संग्रह निवेश बिंदुओं की संख्या से काफी बड़ा है।

चैन (2004) अंतर्निहित रूप से परिभाषित एलपी-प्रकार की समस्याओं को हल करने के लिए एक एल्गोरिथ्म का वर्णन करता है जैसे कि यह एक जिसमें प्रत्येक एलपी-प्रकार तत्व कुछ स्थिर k के लिए निवेश मानों के k-tuple द्वारा निर्धारित किया जाता है। अपने दृष्टिकोण को लागू करने के लिए एक निर्णय एल्गोरिदम उपस्थित होना चाहिए जो किसी दिए गए एलपी-प्रकार के आधार B के लिए निर्धारित कर सकता है और n निवेश मानों के S संग्रह कर सकता है, चाहे B और S द्वारा निर्धारित एलपी-प्रकार की समस्या का आधार हो।

चान का एल्गोरिदम निम्न चरणों का पालन करता है:

• यदि निवेश मानों की संख्या कुछ थ्रेशोल्ड मान से कम है, तो एलपी-प्रकार के तत्वों का संग्रह ढूंढें जो यह निर्धारित करता है और परिणामी स्पष्ट एलपी-प्रकार की समस्या को हल करता है।
• अन्यथा, निवेश मानों को सामान आकार के उप-समूचय Si के k से अधिक उपयुक्त संख्या में विभाजित करें।
• यदि f स्पष्ट रूप से परिभाषित एलपी-प्रकार की समस्या को हल करने के लिए वस्तुनिष्ठ कार्य है, तो एक फलन g को परिभाषित करें जो संग्रह के मिलन पर f के मान के लिए Si के संग्रह को मानचित्र करता है फिर उपसमुच्चय का संग्रह S_i और उद्देश्य फलन g स्वयं एक एलपी-प्रकार की समस्या को परिभाषित करता है, उसी आयाम की जिस तरह की निहित समस्या को हल किया जाना है।
• क्लार्कसन के एल्गोरिथ्म का उपयोग करके g द्वारा परिभाषित (स्पष्ट) एलपी-प्रकार की समस्या को हल करें जो उल्लंघन परीक्षणों की एक रैखिक संख्या और आधार मूल्यांकनों की एक बहुलगणकीय संख्या करता है, आधार मूल्यांकन g चैन के एल्गोरिथम के लिए पुनरावर्ती कॉल द्वारा निष्पादित किया जा सकता है और उल्लंघन परीक्षण निर्णय एल्गोरिथम को कॉल द्वारा किया जा सकता है।

इस धारणा के साथ कि निर्णय एल्गोरिथ्म में कुछ O(T(n)) समय लगता है जो निवेश आकार nके एक फलन के रूप में कम से कम बहुपद रूप से बढ़ता है, चैन दिखाता है कि एक स्पष्ट एलपी सूत्रीकरण पर स्विच करने की सीमा और विभाजन में उप-समूचय की संख्या को इस तरह से चुना जा सकता है कि निहित एलपी-प्रकार अनुकूलन एल्गोरिथ्म भी समय O(T(n))में चलता है।

उदाहरण के लिए, गतिमान बिंदुओं के न्यूनतम व्यास के लिए निर्णय एल्गोरिथ्म को केवल एक निश्चित समय पर बिंदुओं के एक समूह के व्यास की गणना करने की आवश्यकता होती है, एक समस्या O(n log n) घूर्णन कैलीपर्स तकनीक का उपयोग करते हुए समय में हल किया जा सकता है इसलिए चान के एल्गोरिदम को उस समय को खोजने के लिए जिस पर व्यास कम किया जाता है O(n log n).में भी समय लगता है। चैन इस विधि का उपयोग डी-आयामी यूक्लिडियन स्पेस में केंद्रबिंदु ज्यामिति का एक बिंदु खोजने के लिए n इंगित करता है समय O(n^{d − 1} + n log n), उत्तल बहुभुज पर समान वितरण के लिए अधिकतम तुकी गहराई का एक बिंदु खोजने के लिए ब्रास, हेनरिक-लिटान & और मोरिन (2003) द्वारा इसी तरह की तकनीक का उपयोग किया गया था।

इतिहास और संबंधित समस्याएं

रैखिक प्रोग्रामिंग के लिए रैखिक समय एल्गोरिदम की खोज और अवलोकन का एक ही एल्गोरिदम कई स्थितियों में ज्यामितीय अनुकूलन समस्याओं को हल करने के लिए इस्तेमाल किया जा सकता है जो रैखिक प्रोग्राम नहीं थे, कम से कम मेगिडो (1983, 1984) जिन्होंने तीन-चर रैखिक प्रोग्राम और सबसे छोटी वृत्त समस्या दोनों के लिए एक रैखिक अपेक्षित समय एल्गोरिथम दिया हालांकि, मेगिडो ने रैखिक प्रोग्रामिंग के सामान्यीकरण को संयोजी के बजाय ज्यामितीय रूप से तैयार किया संग्रह के सिस्टम पर सार समस्या के बजाय एक उत्तल अनुकूलन समस्या के रूप में, इसी प्रकार डायर (1986) और क्लार्कसन (क्लार्कसन 1995के 1988 के सम्मेलन संस्करण में) ने देखा कि उनके तरीकों को उत्तल प्रोग्रामों के साथ-साथ रैखिक प्रोग्रामों ोंोोंोंोोोंोोंोंो पर भी लागू किया जा सकता है। डायर (1992) ने दिखाया कि न्यूनतम घेरने वाली दीर्घवृत्ताभ समस्या को गैर-रैखिक बाधाओं की एक छोटी संख्या जोड़कर उत्तल अनुकूलन समस्या के रूप में भी तैयार किया जा सकता है। निम्न आयामी रैखिक प्रोग्रामिंग और संबंधित समस्याओं के लिए समय सीमा में सुधार करने के लिए यादृच्छिकता का उपयोग क्लार्कसन और डायर & एंड फ्रेज़ (1989)द्वारा किया गया था।

स्थानीयता और मोनोटोनी के स्वयंसिद्धों को संतुष्ट करने वाले कार्यों के संदर्भ में एलपी-प्रकार की समस्याओं की परिभाषा शारिर & और वेलज़ल (1992)है, लेकिन उसी समय सीमा में अन्य लेखकों ने रैखिक प्रोग्रामों ों के वैकल्पिक संयुक्त सामान्यीकरण तैयार किए उदाहरण के लिए, गार्टनर (1995)द्वारा विकसित एक ढांचे में फलन f को Sके उप-समूचय पर कुल अनुक्रम द्वारा प्रतिस्थापित किया जाता है। अनुक्रम बनाने के लिए एलपी-प्रकार की समस्या में संबंधों को तोड़ना संभव है, लेकिन केवल संयोजी आयाम में वृद्धि की कीमत पर।

इसके अतिरिक्त एलपी-प्रकार की समस्याओं की तरह गार्टनर तत्वों के उप-समूचय पर संगणना करने के लिए कुछ आदिम को परिभाषित करता है हालाँकि, उनकी औपचारिकता में दहनशील आयाम का एक एनालॉग नहीं है।

रैखिक प्रोग्रामों ोंो और रैखिक संपूरकता समस्याओं दोनों का एक और सार सामान्यीकरण स्टिकनी & एंड वॉटसन (1978) द्वारा तैयार किया गया और बाद में कई अन्य लेखकों द्वारा अध्ययन किए गए दोनों रैखिक प्रोग्राम ोंो और रैखिक पूरकता समस्याओं का एक और सार सामान्यीकरण गुण के साथ एक हाइपरक्यूब के किनारों के उन्मुखीकरण से संबंधित है कि हाइपरक्यूब के प्रत्येक फेस (एक फेस के रूप में संपूर्ण हाइपरक्यूब सहित) में एक अद्वितीय सिंक होता है, एक शीर्ष जिसमें कोई बाहरी किनारा नहीं होता है। इस प्रकार का एक अभिविन्यास एलपी-प्रकार की समस्या से एक हाइपरक्यूब के शिखर के साथ S के उपसमुच्चय को इस तरह से बनाया जा सकता है कि दो उपसमुच्चय एक ही तत्व से भिन्न होते हैं यदि संबंधित कोने निकट हैं और यदि f(A) ≠ f(B) है तो A ⊆ B को B की ओर उन्मुख करना और अन्यथा A की ओर उन्मुख करना परिणामी अभिविन्यास में अतिरिक्त गुण है कि यह एक निर्देशित विश्वकोश ग्राफ बनाता है, जिससे यह दिखाया जा सकता है कि एक यादृच्छिक एल्गोरिथ्म पूरे हाइपरक्यूब (एलपी-प्रकार की समस्या का इष्टतम आधार) के अद्वितीय सिंक n के वर्गमूल में चर घातांकी कई चरणों में पा सकता है।

उल्लंघनकर्ता स्पेस का हाल ही में विकसित ढांचा एलपी-प्रकार की समस्याओं को सामान्यीकृत करता है, इस अर्थ में कि प्रत्येक एलपी-प्रकार की समस्या को उल्लंघनकर्ता स्थान द्वारा प्रतिरूपित किया जा सकता है, लेकिन जरूरी नहीं कि इसके विपरीत। उल्लंघनकर्ता स्थान को एलपी-प्रकार की समस्याओं के समान परिभाषित किया जाता है, एक फलन f जो मानचित्र उद्देश्य फलन मानों पर संग्रहित होता है, लेकिन f के मान क्रमबद्ध नहीं होते हैं। अनुक्रम की कमी के बावजूद प्रत्येक संग्रह S में आधारों का एक अच्छी तरह से परिभाषित संग्रह है (संपूर्ण संग्रह के समान मान वाला न्यूनतम संग्रह) जो एलपी-प्रकार की समस्याओं के लिए क्लार्कसन के एल्गोरिदम की विविधताओं द्वारा पाया जा सकता है। वास्तव में, उल्लंघनकर्ता स्पेस को उन प्रणालियों को स्पष्ट रूप से चित्रित करने के लिए दिखाया गया है जिन्हें क्लार्कसन के एल्गोरिदम द्वारा हल किया जा सकता है।

संदर्भ

• Amenta, Nina (1994), "Helly-type theorems and generalized linear programming" (PDF), Discrete and Computational Geometry, 12 (3): 241–261, doi:10.1007/BF02574379, MR 1298910, S2CID 26667725.
• Amenta, Nina; Bern, Marshall; Eppstein, David (1999), "Optimal point placement for mesh smoothing", Journal of Algorithms, 30 (2): 302–322, arXiv:cs.CG/9809081, doi:10.1006/jagm.1998.0984, MR 1671836, S2CID 182728.
• Bell, David E. (1977), "A theorem concerning the integer lattice" (PDF), Studies in Applied Mathematics, 56 (2): 187–188, doi:10.1002/sapm1977562187, MR 0462617.
• Braß, Peter; Heinrich-Litan, Laura; Morin, Pat (2003), "Computing the center of area of a convex polygon" (PDF), International Journal of Computational Geometry & Applications, 13 (5): 439–445, doi:10.1142/S021819590300127X, MR 2012837.
• Brise, Yves; Gärtner, Bernd (2011), "Clarkson's algorithm for violator spaces" (PDF), Computational Geometry: Theory and Applications, 44 (2): 70–81, arXiv:0906.4706, doi:10.1016/j.comgeo.2010.09.003, MR 2737285, S2CID 1233875.
• Chan, Timothy M. (2004), "An optimal randomized algorithm for maximum Tukey depth" (PDF), Proc. 15th ACM-SIAM Symp. Discrete Algorithms, pp. 423–429.
• Chazelle, Bernard; Matoušek, Jiří (1996), "On linear-time deterministic algorithms for optimization problems in fixed dimension" (PDF), Journal of Algorithms, 21 (3): 579–597, doi:10.1006/jagm.1996.0060, MR 1417665, S2CID 2482481.
• Clarkson, Kenneth L. (1995), "Las Vegas algorithms for linear and integer programming when the dimension is small" (PDF), Journal of the ACM, 42 (2): 488–499, doi:10.1145/201019.201036, MR 1409744, S2CID 6953625.
• Dyer, Martin E. (1986), "On a multidimensional search technique and its application to the Euclidean one-centre problem", SIAM Journal on Computing, 15 (3): 725–738, doi:10.1137/0215052, MR 0850419.
• Dyer, Martin E. (1992), "A class of convex programs with applications to computational geometry", Proc. 8th Symposium on Computational Geometry (SCG '92), Berlin, Germany, pp. 9–15, doi:10.1145/142675.142681, ISBN 0-89791-517-8, S2CID 7654513{{citation}}: CS1 maint: location missing publisher (link).
• Dyer, Martin E.; Frieze, Alan M. (1989), "A randomized algorithm for fixed-dimensional linear programming", Mathematical Programming, (Ser. A), 44 (2): 203–212, doi:10.1007/BF01587088, MR 1003560, S2CID 206800147.
• Eppstein, David (2005), "Quasiconvex programming", in Goodman, Jacob E.; Pach, János; Welzl, Emo (eds.), Combinatorial and Computational Geometry, MSRI Publications, vol. 52, Cambridge Univ. Press, pp. 287–331, arXiv:cs.CG/0412046, MR 2178325.
• Eppstein, David (2006), "Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms", ACM Transactions on Algorithms, 2 (4): 492–509, arXiv:cs.DS/0304018, doi:10.1145/1198513.1198515, MR 2284242, S2CID 9980061.
• Fischer, Kaspar; Gärtner, Bernd (2004), "The smallest enclosing ball of balls: combinatorial structure and algorithms" (PDF), International Journal of Computational Geometry & Applications, 14 (4–5): 341–378, doi:10.1142/S0218195904001500, MR 2087827.
• Gärtner, Bernd (1995), "A subexponential algorithm for abstract optimization problems" (PDF), SIAM Journal on Computing, 24 (5): 1018–1035, doi:10.1137/S0097539793250287, MR 1350756.
• Gärtner, Bernd; Matoušek, Jiří; Rüst, L.; Škovroň, P. (2008), "Violator spaces: structure and algorithms", Discrete Applied Mathematics, 156 (11): 2124–2141, arXiv:cs.DM/0606087, doi:10.1016/j.dam.2007.08.048, MR 2437006.
• Gärtner, Bernd; Welzl, Emo (2001), "A simple sampling lemma: analysis and applications in geometric optimization" (PDF), Discrete and Computational Geometry, 25 (4): 569–590, doi:10.1007/s00454-001-0006-2, MR 1838420, S2CID 14263014.
• Gupta, Prosenjit; Janardan, Ravi; Smid, Michiel (1996), "Fast algorithms for collision and proximity problems involving moving geometric objects", Computational Geometry. Theory and Applications, 6 (6): 371–391, doi:10.1016/0925-7721(95)00028-3, hdl:11858/00-001M-0000-0014-B50E-D, MR 1415267.
• Halman, Nir (2007), "Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems", Algorithmica, 49 (1): 37–50, doi:10.1007/s00453-007-0175-3, MR 2344393, S2CID 8183965.
• Kalai, Gil (1992), "A subexponential randomized simplex algorithm", Proc. 24th ACM Symposium on Theory of Computing, pp. 475–482, doi:10.1145/129712.129759, S2CID 17447465.
• Li, Hongdong (2007), "A practical algorithm for L_∞ triangulation with outliers", Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR '07), pp. 1–8, doi:10.1109/CVPR.2007.383068, hdl:1885/39190, S2CID 14882916.
• Löffler, Maarten; van Kreveld, Marc (2010), "Largest bounding box, smallest diameter, and related problems on imprecise points" (PDF), Computational Geometry Theory and Applications, 43 (4): 419–433, doi:10.1016/j.comgeo.2009.03.007, MR 2575803.
• Matoušek, Jiří (1995), "On geometric optimization with few violated constraints", Discrete and Computational Geometry, 14 (4): 365–384, doi:10.1007/BF02570713, MR 1360943.
• Matoušek, Jiří (2009), "Removing degeneracy in LP-type problems revisited", Discrete and Computational Geometry, 42 (4): 517–526, doi:10.1007/s00454-008-9085-7, MR 2556452.
• Matoušek, Jiří; Sharir, Micha; Welzl, Emo (1996), "A subexponential bound for linear programming" (PDF), Algorithmica, 16 (4–5): 498–516, doi:10.1007/BF01940877, S2CID 877032.
• Megiddo, Nimrod (1983), "Linear-time algorithms for linear programming in R³ and related problems", SIAM Journal on Computing, 12 (4): 759–776, doi:10.1137/0212052, MR 0721011, S2CID 14467740.
• Megiddo, Nimrod (1984), "Linear programming in linear time when the dimension is fixed", Journal of the ACM, 31 (1): 114–127, doi:10.1145/2422.322418, MR 0821388, S2CID 12686747.
• Nielsen, Frank; Nock, Richard (2008), "On the smallest enclosing information disk" (PDF), Information Processing Letters, 105 (3): 93–97, doi:10.1016/j.ipl.2007.08.007, MR 2378119.
• Puerto, J.; Rodríguez-Chía, A. M.; Tamir, A. (2010), "On the planar piecewise quadratic 1-center problem", Algorithmica, 57 (2): 252–283, doi:10.1007/s00453-008-9210-2, MR 2587554, S2CID 18587944.
• Scarf, Herbert E. (1977), "An observation on the structure of production sets with indivisibilities", Proceedings of the National Academy of Sciences of the United States of America, 74 (9): 3637–3641, Bibcode:1977PNAS...74.3637S, doi:10.1073/pnas.74.9.3637, MR 0452678, PMC 431672, PMID 16592435.
• Seidel, Raimund (1991), "Small-dimensional linear programming and convex hulls made easy", Discrete and Computational Geometry, 6 (5): 423–434, doi:10.1007/BF02574699, MR 1115100.
• Sharir, Micha; Welzl, Emo (1992), "A combinatorial bound for linear programming and related problems", 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS), Cachan, France, February 13–15, 1992, Proceedings, Lecture Notes in Computer Science, vol. 577, Springer-Verlag, pp. 567–579, doi:10.1007/3-540-55210-3_213.
• Stickney, Alan; Watson, Layne (1978), "Digraph models of Bard-type algorithms for the linear complementarity problem", Mathematics of Operations Research, 3 (4): 322–333, doi:10.1287/moor.3.4.322, MR 0509668.
• Szabó, Tibor; Welzl, Emo (2001), "Unique sink orientations of cubes" (PDF), 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), pp. 547–555, doi:10.1109/SFCS.2001.959931, MR 1948744, S2CID 6597643.
• Welzl, Emo (1991), "Smallest enclosing disks (balls and ellipsoids)", in Maurer, H. (ed.), New Results and New Trends in Computer Science (PDF), Lecture Notes in Computer Science (555 ed.), Springer-Verlag, pp. 359–370, doi:10.1007/BFb0038202.