ETH Zurich के शोधकर्ताओं ने सबसे तेज flow algorithm विकसित किया

 (ethz.ch)
1 पॉइंट द्वारा GN⁺ 2024-06-30 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • ETH Zurich में Rasmus Kyng की शोध टीम ने नेटवर्क में maximum flow खोजने और transport cost को न्यूनतम करने वाली समस्या को लगभग गणितीय सीमा जितनी तेज़ गति से compute करने वाला algorithm विकसित किया
  • नया algorithm नेटवर्क data पढ़ने में लगने वाले समय के लगभग बराबर scale में जवाब देने वाला almost-linear time approach है, और इसे railways, roads, waterways और internet जैसे networks की गणना में लागू किया जा सकता है
  • पहले, connections की संख्या को m मानें तो 2000 से पहले स्तर m^1.5 था, 2004 में m^1.33 तक पहुँचा, लेकिन Kyng का approach data पढ़ने के बाद की extra computation time को नगण्य स्तर तक घटा देता है
  • शोध टीम ने static और directed networks से आगे बढ़कर, connections जुड़ने वाले incremental graphs और हटने वाले decremental graphs में भी shortest path और minimum-cost maximum flow को almost-linear time में compute किया
  • Gotthard Base Tunnel के बंद होने और आंशिक रूप से फिर खुलने, A13 motorway पर landslide जैसी स्थितियों में, जहाँ real-world networks बदलते हैं, यह optimal route को तेज़ी से फिर compute करने का आधार बनता है

Network flow problem को लगभग सीमा-गति पर compute करना

  • Rasmus Kyng की शोध टीम का network flow algorithm नेटवर्क में संभव maximum flow खोजते हुए transport cost को न्यूनतम करने की समस्या से निपटता है
  • Copenhagen से Milan तक जितना संभव हो उतना सामान सबसे तेज़ और सबसे सस्ते तरीके से ले जाने का route खोजने की स्थिति इसका representative example है
  • Railways, roads, waterways और internet जैसे connections और capacity वाले networks में optimal low-cost flow compute किया जा सकता है
  • computation speed इतनी घट गई है कि यह लगभग computer द्वारा network data पढ़ने में लगने वाले समय के बराबर हो गई है

यह “सबसे तेज़” algorithm क्यों है

  • पहले optimal flow compute करने में लगने वाला समय network data process करने के समय से कहीं अधिक होता था
  • network जितना बड़ा और complex होता था, आवश्यक computation time problem size से भी तेज़ी से बढ़ता था
  • Kyng का approach computation time और network size को समान अनुपात में बढ़ने देता है
    • यदि network connections की संख्या m हो, तो data को एक बार पढ़ने में ही m time लगता है
    • 2000 से पहले m^1.5 से तेज़ compute करने वाला कोई algorithm नहीं था
    • 2004 में problem solve करने के लिए आवश्यक computation m^1.33 तक घट गया
    • Kyng algorithm data पढ़ने के बाद solution तक पहुँचने के लिए extra computation time को नगण्य स्तर तक घटा देता है

Almost-linear time algorithms का मूल्यांकन और विस्तार

  • Kyng की शोध टीम ने दो साल पहले इस concept का mathematical proof शामिल करने वाला paper प्रकाशित किया
  • ऐसे लगभग optimally fast algorithms को almost-linear time algorithms कहा जाता है
  • Daniel A. Spielman ने इस algorithm की तुलना घोड़ागाड़ी को overtake करती Porsche से की
  • उस paper को 2022 IEEE Annual Symposium on Foundations of Computer Science, FOCS में Best Paper Award मिला
  • Communications of the ACM ने भी इस शोध को highlight किया, और Quanta editors ने Kyng algorithm को 2022 में computer science की 10 बड़ी discoveries में से एक चुना

Static networks से बदलते networks तक

  • शुरुआती algorithm ने fixed direction वाले fixed, static networks पर focus किया था
    • directed connections शहरों के road network में one-way streets जैसी structure हैं
  • बाद में शोध टीम ने समय के साथ धीरे-धीरे बदलने वाले networks में भी optimal flow compute करने वाले algorithms विकसित किए
  • Simon Meierhans ने Vancouver में Annual ACM Symposium on Theory of Computing, STOC में नया almost-linear time algorithm प्रस्तुत किया
    • यह algorithm नए connections जुड़ने वाले networks में minimum-cost maximum-flow problem solve करता है
  • अक्टूबर में IEEE Symposium on Foundations of Computer Science, FOCS के लिए accepted दूसरे paper में, connections delete होने को भी handle करने वाला algorithm विकसित किया गया
  • दोनों algorithms connections जुड़ने या हटने वाले networks में shortest path identify करते हैं

Real-world network changes के उदाहरण

  • Switzerland का Gotthard Base Tunnel 2023 की गर्मियों के बाद पूरी तरह बंद हुआ था और फिर आंशिक रूप से फिर खोला गया
  • Gotthard Road Tunnel का प्रमुख alternative route A13 motorway का एक हिस्सा हाल में landslide से नष्ट हो गया
  • ऐसे changes होने पर computers, online map services और route planners को Milan और Copenhagen के बीच सबसे कम cost और shortest connection फिर compute करना पड़ता है
  • Kyng के नए algorithms connections जोड़ने या हटाने वाले networks में भी almost-linear time में optimal route compute करते हैं
  • detours या नए routes बनने से connections जुड़ें, तब भी extra computation time नगण्य स्तर पर रहता है

पिछली दो strategies और नया combination approach

  • Network flow computation को optimal flow और minimum-cost route खोजने के लिए network को कई बार analyze करना पड़ता है
  • हर iteration में यह देखा जाता है कि कौन-से connections open हैं, closed हैं, या capacity limit तक पहुँचकर congested हो गए हैं
  • Kyng से पहले computer scientists मुख्यतः दो strategies में से एक का इस्तेमाल करते थे
    • railway network model: हर iteration में traffic flow बदले हुए network के एक पूरे section को compute करना
    • power grid model: हर iteration में पूरे network को compute करना, लेकिन calculation तेज़ करने के लिए हर section के बदले हुए flow में statistical average values का इस्तेमाल करना
  • Kyng की शोध टीम ने दोनों strategies की खूबियों को मिलाकर नया combined approach बनाया
  • Maximilian Probst Gutenberg का मानना है कि कई छोटे, efficient और low-cost computation steps को जोड़ना, कुछ बड़े steps की तुलना में कहीं तेज़ होता है

Flow algorithms का ऐतिहासिक संदर्भ

  • Network flow problem 1950s में algorithms के जरिए systematically solve की गई शुरुआती problems में से एक थी
  • Flow algorithms ने theoretical computer science को independent research field के रूप में स्थापित करने में अहम भूमिका निभाई
  • Lester R. Ford Jr. और Delbert R. Fulkerson का प्रसिद्ध algorithm भी इसी दौर में आया
  • Ford-Fulkerson algorithm हर path की capacity से अधिक हुए बिना, network के जरिए जितना संभव हो उतना सामान transport करने वाली maximum flow problem को efficiently solve करता है
  • बाद के शोध ने दिखाया कि maximum flow problem, minimum cost problem और कई network flow problems सामान्य minimum-cost flow problem के special cases हैं

पुराने algorithms की सीमाएँ और 2004 का बदलाव

  • Kyng के शोध से पहले के कई algorithms किसी एक specific problem को efficiently solve कर सकते थे, लेकिन पर्याप्त तेज़ नहीं थे और व्यापक minimum-cost flow problem तक expand करना कठिन था
  • 1970s के pioneering flow algorithms बनाने वाले John Edward Hopcroft, Richard Manning Karp और Robert Endre Tarjan को अलग-अलग Turing Award मिला
    • Karp को 1985 में award मिला
    • Hopcroft और Tarjan को 1986 में award मिला
  • 2004 में Daniel Spielman, Shang-Hua Teng और बाद में Samuel Daitch ने minimum-cost flow problem के लिए भी तेज़ और efficient solution देने वाला algorithm लिखा
  • इस group ने दृष्टिकोण को railway से power grid के power flow की ओर shift किया
  • power grid में current flow को आंशिक रूप से उन connections पर redirect किया जा सकता है जिनमें पहले से दूसरा current बह रहा हो
  • Kyng ने Spielman के पूरे-network के लिए powerful algorithmic approach को जस का तस follow नहीं किया, बल्कि partial path computation idea को Hopcroft और Karp के पुराने approach पर apply किया
  • हर iteration में partial paths compute करने से overall flow computation तेज़ करने में बड़ी भूमिका निभी

नए mathematical tools और data structures

  • ETH Zurich टीम की प्रगति सिर्फ नए algorithms पर नहीं, बल्कि computation को और तेज़ बनाने वाले mathematical tools के design पर भी आधारित है
  • शोध टीम ने network data organize करने के लिए नया data structure विकसित किया
  • यह data structure network connections में बदलावों को बहुत तेज़ी से identify करने देता है
  • तेज़ change identification algorithmic solution की speed बढ़ाने वाले factor के रूप में काम करता है
  • almost-linear time algorithms और नया data structure उन बहुत बड़ी problems को solve करने का आधार तैयार करते हैं जिन्हें पहले efficiently compute नहीं किया जा सकता था

संबंधित papers और सामग्री

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-06-30
Hacker News की राय

  • यह algorithm n -> inf की सीमा में asymptotically लगभग linear है
    वीडियो के अंत में कहा गया है कि इस algorithm का कोई भी implementation वास्तविक दुनिया में मौजूदा algorithms को हरा पाना मुश्किल होगा
    https://cacm.acm.org/research/almost-linear-time-algorithms-...

    • तो क्या यह एक और galactic algorithm है?
      https://en.wikipedia.org/wiki/Galactic_algorithm
    • शुरुआत में इतनी उम्मीदें बढ़ाने के बाद यह काफ़ी फीका लगा
    • शीर्षक देखते ही मैं बहुत skeptical था
      सबसे तेज़ संभव गति जैसा phrase वाकई बहुत bold claim है
    • ऐसे मामलों में एक और संकेत यह होता है कि लगभग बिल्कुल optimal solution चाहिए होता है
      अक्सर 1% समय लगाकर 99% quality हासिल करना कहीं ज़्यादा practical होता है

  • दिलचस्प बात यह है कि वही व्यक्ति सिर्फ theory वाले algorithms को असल में अच्छी तरह चलाने पर भी research करता है [1]
    हालांकि उस प्रक्रिया में भी शायद करीब 20 साल लगते हैं। [1] 2004 के theoretical breakthrough [2] पर बना है, और मेरी समझ के मुताबिक ऐसे algorithms 2024 में ही practice में काम करना शुरू हुए हैं। अगर ऐसा है, तो practical minimum-cost flow algorithm की उम्मीद 2044 में की जा सकती है
    [1] https://arxiv.org/pdf/2303.00709
    [2] https://arxiv.org/abs/cs/0310051

  • Almost-Linear-Time Algorithm
    O(mn) से O(m) पर जाना computation से N, यानी vertices की संख्या, को हटाने जैसा है; क्या यह इतना अच्छा नहीं कि यकीन करना मुश्किल हो?

    • constant factors इतने बड़े हैं कि practical inputs पर यह asymptotically worse मौजूदा algorithms से भी धीमा होगा
      फिर भी theory के लिहाज़ से यह शानदार result है

  • कच्चे numbers से ही पता चलता है कि हम कितनी दूर आ चुके हैं। 2000 के दशक से पहले कोई भी algorithm m1.5 से तेज़ compute नहीं कर पाता था। यहां m उन network connections की संख्या है जिन्हें computer को compute करना होता है, और network data को एक बार पढ़ने में ही m time लगता है। 2004 में इस समस्या को हल करने के लिए जरूरी computation speed m1.33 तक घट गई। Kyng के algorithm के साथ, network data पढ़ने के बाद solution तक पहुंचने के लिए जरूरी “extra” computation time अब नगण्य है।
    मूल लेख ने Kyng के breakthrough को m metric के नज़रिए से explain नहीं किया, जबकि उसे इतना important माना गया है; सोच रहा हूं क्यों

  • कभी-कभी लगता है कि complexity को metric बनाने में हम पूरी तरह भटक गए हैं
    complexity metrics को पागलपन की हद तक optimize किया जा रहा है, लेकिन ऐसे algorithms बढ़ रहे हैं जो असल में useful नहीं हैं

    • यह phenomenon तो दशकों से मौजूद है
      आसान उपलब्धियां खत्म होने के बाद algorithms research भी एक और highly specialized field बन गया है, और जब तक आप बहुत करीबी field के researcher न हों, ज़्यादातर papers पर समय लगाना खास worth it नहीं है

  • संबंधित पोस्ट: https://news.ycombinator.com/item?id=31149038 (40 comments)
    https://news.ycombinator.com/item?id=31675015 (72 comments)

  • paper या code कहां है?

  • यहां मुझे एक बात confuse कर रही है: o(n), O(n) से ज्यादा strong statement लगता है
    क्योंकि हर o(n) algorithm O(n) होता है, लेकिन उल्टा सच नहीं है। और अगर o(n) बहुत छोटे n पर भी लागू होता है, जबकि O(n) सिर्फ n -> inf पर लागू होता है, तो यह algorithm छोटे n पर भी applicable होना चाहिए, नहीं? तब तो यह ऊपर बताए galactic algorithm का उलटा होना चाहिए। क्या मैं कुछ miss कर रहा हूं?

    • small o notation भी अभी asymptotic statement ही है, इसलिए इसे छोटे n पर लागू होना जरूरी नहीं
      f(n) = o(g(n)) की definition मोटे तौर पर lim (n -> infinity) f(n)/g(n) = 0 है। दूसरे शब्दों में, sufficiently large n के लिए g, f से ज्यादा तेज़ी से grow करता है
      उदाहरण के लिए f(n) = 10n if n < 1000 else 1e1000 जैसी function o(n) है। n बढ़ने पर 1e1000/n, 0 की ओर जाता है। यह एक piecewise function की pseudo Python representation है, जो n = 1000 तक 101000 तक exponentially बढ़ता है और फिर उसके बाद constant रहता है
    • अगर किसी algorithm की complexity 3↑↑64*n^0.999 हो, तो वह algorithm o(n) है, लेकिन उसे आराम से galactic algorithm कह सकते हैं

  • अगर मुझे सही याद है तो 3↑↑64 Graham's number है

  • धत् तेरे की, ये constant factors, मन करता है आसमान की ओर मुट्ठी हिलाऊं

  • abstract में time सिर्फ m^(1+o(1)) बताया गया है
    क्या किसी को पता है कि कहीं और अधिक specific upper bound दिया है?

    • यहां o small o है, इसलिए यह उस term को पकड़ता है जिसका “1 से divide किया हुआ value” m के infinity की ओर जाने पर 0 की ओर जाता है
      https://de.m.wikipedia.org/wiki/Landau-Symbole
    • इसका मतलब है कि constants ऐसे चुने जा सकते हैं कि इसे O(m) के जितना चाहें उतना करीब बनाया जा सके
      दूसरे शब्दों में, किसी भी ɛ>1 के लिए O(m^ɛ) time में चलने वाला algorithm देने वाली algorithmic scheme है
    • वही तो specific upper bound है
      small o वह function है जो n के infinity की ओर जाने पर 0 के करीब जाता है, और इसे asymptotically negligible कहा जाता है