<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Singhraj on Medium]]></title>
        <description><![CDATA[Stories by Singhraj on Medium]]></description>
        <link>https://medium.com/@singhraj01?source=rss-1a8478134413------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*3L69WGOt3mGb0wMj</url>
            <title>Stories by Singhraj on Medium</title>
            <link>https://medium.com/@singhraj01?source=rss-1a8478134413------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 00:04:17 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@singhraj01/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[How Ride-Sharing Apps Optimally Match Drivers and Passengers using Graph Theory]]></title>
            <link>https://medium.com/@singhraj01/how-ride-sharing-apps-optimally-match-drivers-and-passengers-using-graph-theory-37cd43976bf8?source=rss-1a8478134413------2</link>
            <guid isPermaLink="false">https://medium.com/p/37cd43976bf8</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[optimization]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[graph-theory]]></category>
            <dc:creator><![CDATA[Singhraj]]></dc:creator>
            <pubDate>Tue, 14 Apr 2026 16:42:52 GMT</pubDate>
            <atom:updated>2026-04-14T16:42:52.832Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Behind every Uber or Ola booking lies a powerful optimization engine — Bipartite Graphs and the Hungarian Algorithm.</em></p><h3><strong>Introduction</strong></h3><p>You open apps like Uber or Ola, tap “<strong>Book Ride</strong>”, and within seconds a driver is assigned.</p><p>But here’s the real question:</p><p>👉 <em>How does the system choose the best driver among many?</em></p><p>Not just the closest one — but the assignment that minimizes <strong>total waiting time across all passengers simultaneously</strong>.</p><blockquote><em>“Wait… so it’s not just nearest driver?”<br>Exactly — it’s a</em><strong><em> global optimization problem.</em></strong></blockquote><h3><strong>What is a Bipartite Graph?</strong></h3><p><strong>A bipartite graph</strong> splits its vertices into two distinct sets — Set X and Set Y — where every edge connects a vertex from one set to a vertex in the other. No edge ever connects two vertices within the same set.</p><p>Formally, a graph G = (V, E) is bipartite if V can be partitioned into two non-empty subsets X and Y such that every edge has one endpoint in X and the other in Y.</p><p>A bipartite graph divides nodes into two sets:</p><ul><li>Drivers (D) 🚗</li><li>Passengers (P) 🧍</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/647/1*CQMSBD6d6OZ5AE6IuiQfWA.png" /><figcaption><strong><em>Bipartite Graph: Drivers ↔ Passengers with distances</em></strong></figcaption></figure><p>Edges exist only between the two sets, not within them.</p><p>Each edge has a <strong>weight</strong>:<br>👉 Distance or travel time</p><h3><strong>Graph Representation of Ride-Sharing</strong></h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/698/1*q10X-ROf4gWtw8Dg_PDp8Q.png" /></figure><p>Goal: Find <strong>minimum cost perfect matching</strong></p><h3><strong>Why Not Random Matching?</strong></h3><p>A simple assignment may work… but it’s inefficient.</p><p>Example:</p><ul><li>One driver travels 8 km</li><li>Another travels 1 km</li></ul><p>Total = 9 km ❌</p><p>We want:<strong><br>Minimum total distance across all matches</strong></p><h3><strong>The Hungarian Algorithm</strong></h3><p>Developed by Harold Kuhn in 1955 (based on work by Hungarian mathematicians), the algorithm finds the minimum cost perfect matching in O(n³) time — efficient enough for city-scale systems handling thousands of simultaneous requests.</p><p>The Hungarian Algorithm finds the<strong> optimal assignment</strong>.</p><h3><strong>Steps:</strong></h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/753/1*YHJWdb4sJ-DDaO4M58muSw.png" /></figure><h3><strong>Example 1 — simple case (3×3)</strong></h3><p><em>‘‘Three drivers, three passengers. Some routes are unavailable (∞). Watch how row reduction alone produces an immediately readable optimal assignment.’’</em></p><p><strong>Drivers:</strong> D₁, D₂, D₃ <br><strong>Passengers:</strong> P₁, P₂, P₃</p><p><strong>Step 1 — cost matrix</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/642/1*ScRX0B8NqB6DBj-QmmohIA.png" /></figure><p><strong>Step 2 — after row reduction (subtract row minimums: 2, 2, 1)</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/557/1*IQ_ucypzfXU8ZXZgzrcY5g.png" /></figure><p>Every row has exactly one zero and each zero is in a different column — perfect matching is immediately readable. No adjustment step needed.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/734/1*EnZiecqCPhc-iu5PLTc13g.png" /></figure><h4>Optimal Matching:</h4><ul><li>D₁ → P₁</li><li>D₂ → P₃</li><li>D₃ → P₂</li></ul><p>👉 <strong>Total = 5 km (Optimal)</strong></p><h3>Example 2 — Advanced Case (With Adjustment)</h3><p>‘‘Four drivers, four passengers, all routes available. This example requires the matrix adjustment step — the real power of the algorithm.’’</p><p><strong>Drivers: </strong>D₁, D₂, D₃, D₄<strong><br>Passengers: </strong>P₁, P₂, P₃, P₄</p><p><strong>Step 1 — Cost Matrix</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/662/1*iZGucJ-pSApx1u3g5v0E8Q.png" /></figure><p><strong>Step 2 — Row Reduction (subtract 2, 3, 1, 4)</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/635/1*0Sw99DlwAt5LEgmkPfIiSw.png" /></figure><h4>Step 3 — Column Reduction (subtract 3 from P₁; others already 0)</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/662/1*2L-Bc5eW3NzcbgH59FBSDQ.png" /><figcaption>Only 3 lines are needed to cover all zeros — less than n=4, so optimal solution is not yet found. We apply the adjustment step.</figcaption></figure><h4>Step 4 — Adjustment Required (smallest uncovered value = 1)</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/658/1*z8unvOF13X-auW4ykPn7nw.png" /></figure><h3>Final Assignment</h3><ul><li>D₁ → P₂</li><li>D₂ → P₁</li><li>D₃ → P₃</li><li>D₄ → P₄</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/698/1*MtoV2cJ98ndExXL_HgjmLQ.png" /><figcaption><em>Final driver → passenger mapping</em></figcaption></figure><h3>💡 Where Else Is This Used?</h3><ul><li>🚗 Ride-sharing (Uber, Ola)</li><li>🍔 Food delivery (Swiggy, Zomato)</li><li>📦 Logistics (Amazon)</li><li>🏥 Healthcare matching systems</li><li>💻 Task scheduling</li></ul><h3>📘 Questions</h3><h3>1. A bipartite graph consists of…?</h3><p>a. Only vertices<br>b. Two disjoint sets of vertices with edges between them<br>c. Cycles only<br>d. Directed edges only</p><h3>2. Edge weights represent…?</h3><p>a. Ratings<br>b. IDs<br>c. Distance/time<br>d. Nodes</p><h3>3. Goal of Hungarian Algorithm?</h3><p>a. Shortest path<br>b. Maximum edges<br>c. Minimum cost matching<br>d. Remove cycles</p><h3>4. Perfect matching means…?</h3><p>a. All connected<br>b. Some unmatched<br>c. Every vertex matched once<br>d. Single edge</p><h3>5. Adjustment step is needed when…?</h3><p>a. All zeros<br>b. Lines = n<br>c. Solution found<br>d. Lines &lt; n</p><h3>6. Time complexity is…?</h3><p>a. O(n)<br>b. O(n²)<br>c. O(n³)<br>d. O(log n)</p><h3>✅ Answers:</h3><ol><li>b</li><li>c</li><li>c</li><li>c</li><li>d</li><li>c</li></ol><h3>📚 References</h3><ul><li><a href="https://mathworld.wolfram.com/HungarianMaximumMatchingAlgorithm.html">https://mathworld.wolfram.com/HungarianMaximumMatchingAlgorithm.html</a></li><li><a href="https://brilliant.org/wiki/hungarian-matching/">https://brilliant.org/wiki/hungarian-matching/</a></li><li><a href="https://www.sciencedirect.com/topics/computer-science/hungarian-algorithm">https://www.sciencedirect.com/topics/computer-science/hungarian-algorithm</a></li><li><a href="https://codelucky.com/bipartite-matching-hungarian-algorithm/">https://codelucky.com/bipartite-matching-hungarian-algorithm/</a></li><li><a href="https://web.sfc.keio.ac.jp/~rdv/keio/sfc/teaching/optimization-theory/optimization-theory-2016/Opt-Lec09-notes-bipartite.html">https://web.sfc.keio.ac.jp/~rdv/keio/sfc/teaching/optimization-theory/optimization-theory-2016/Opt-Lec09-notes-bipartite.html</a></li><li><a href="https://journals.sagepub.com/doi/10.1260/1748-3018.8.2.219">https://journals.sagepub.com/doi/10.1260/1748-3018.8.2.219</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=37cd43976bf8" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>