Approximation algorithms for the maximum carpool matching problem

DOI10.1007/978-3-319-58747-9_19zbMATH Open1442.68266arXiv1604.05609OpenAlexW2340469429MaRDI QIDQ2399375FDOQ2399375

Authors: Gilad Kutiel 

Publication date: 22 August 2017

Abstract: 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:VoN$, and a weight function $w:AoR$, a feasible emph{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 $Acap(PimesD)$, under the constraints that for every vertex $dinD$, $din(d)leqc(d)$, and for every vertex $pinP$, $dout(p)leq1$. 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~cite{zimride}, 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.

Full work available at URL: https://arxiv.org/abs/1604.05609

Recommendations

• Local search algorithms for the maximum carpool matching problem
• Local search algorithms for the maximum carpool matching problem
• Approximate ridesharing of personal vehicles problem
• Carpooling in social networks
• On some matching problems arising in vehicle scheduling models

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Combinatorial optimization (90C27) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Matching models (91B68)

Cites Work

• A strongly polynomial minimum cost circulation algorithm
• Optimization for dynamic ride-sharing: a review
• Scalability issues in optimal assignment for carpooling
• Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
• Approximations for maximum transportation with permutable supply vector and other capacitated star packing problems
• Improved Approximation Algorithms for the Spanning Star Forest Problem

Cited In (6)

• The optimality of the online greedy algorithm in carpool and chairman assignment problems
• An optimization model and a solution algorithm for the many-to-many car pooling problem
• Local search algorithms for the maximum carpool matching problem
• Scalability issues in optimal assignment for carpooling
• Local search algorithms for the maximum carpool matching problem
• Complexity and approximability of extended spanning star forest problems in general and complete graphs

This page was built for publication: Approximation algorithms for the maximum carpool matching problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2399375)