2016/01/21 by Gilad Kutiel, Kutiel, Gilad
Business, Management and Accounting · Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Search Problems #Sharing Economy and Platforms #Transportation and Mobility Innovations
paper · pdf · doi:10.48550/arxiv.1604.05609
openalex publication_date 2016/01/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Maximum Carpool Matching problem is a star packing problem in directed graphs. Formally, given a directed graph G = (V, A), a capacity function c: V → N , and a weight function w : A → R , a feasible carpool matching is a triple (P, D, M), where P (passengers) and D (drivers) form a partition of V, and M is a subset of A ∩ (P × D), under the constraints that for every vertex d ∈ D, din(d) ≤ c(d), and for every vertex p ∈ P, dout(p) ≤ 1. In the Maximum Carpool Matching problem we seek for a matching (P, D, M) that maximizes the total weight of M. The problem arises when designing an online carpool service, such as Zimride~\citezimride, that tries to connect between passengers and drivers based on (arbitrary) similarity function. The problem is known to be NP-hard, even for uniform weights and without capacity constraints. We present a 3-approximation algorithm for the problem and 2-approximation algorithm for the unweighted variant of the problem.