Local Search Algorithms for the Maximum Carpool Matching Problem
- PDF / 2,506,561 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 97 Downloads / 280 Views
Local Search Algorithms for the Maximum Carpool Matching Problem Gilad Kutiel1 · Dror Rawitz2 Received: 2 November 2017 / Accepted: 25 April 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
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 ∶ V → ℕ , and a weight function w ∶ A → ℝ+ , a carpool matching is a subset of arcs, M ⊆ A , out in in (v) ⋅ dM (v) ≤ c(v) , and (3) (v) = 0 , (2) dM such that every v ∈ V satisfies: (1) dM out out dM (v) ≤ 1 . A vertex v for which dM (v) = 1 is a passenger, and a vertex for which out in dM (v) = 0 is a driver who has dM (v) passengers. In the Maximum Carpool Matching problem the goal is to find a carpool matching M of maximum total weight. The problem arises when designing an online carpool service, such as Zimride (Zimride by enterprise. https://zimride.com/), which tries to connect between users based on a similarity function. The problem is known to be NP-hard, even in the unweighted and uncapacitated case. The Maximum Group Carpool Matching problem, is an extension of the Maximum Carpool Matching where each vertex represents an unsplittable group of passengers. Formally, each vertex u ∈ V has a size s(u) ∈ ℕ , and the ∑ in (v) ≤ c(v) is replaced with u∶(u,v)∈M s(u) ≤ c(v) . We show that Maximum constraint dM Carpool Matching can be formulated as an unconstrained submodular maximization problem, thus it admits a 12-approximation algorithm. We show that the same formulation does not work for Maximum Group Carpool Matching, nevertheless, we present a local search ( 12 − 𝜀)-approximation algorithm for Maximum Group Carpool Matching. For the unweighted variant of both problems when the maximum possible capacity, cmax , is bounded by a constant, we provide a local search ( 12 + 2c1 − 𝜀) max
-approximation algorithm. We also provide an APX-hardness result, even if the maximum degree and cmax are at most 3.
Keywords Approximation algorithms · Local search · Star packing · Submodular maximization A preliminary version was presented at the 25th Annual European Symposium on Algorithms, 2017. D. Rawitz: Supported in part by the Israel Science Foundation (Grant No. 497/14). * Gilad Kutiel [email protected] Extended author information available on the last page of the article
13
Vol.:(0123456789)
Algorithmica
1 Introduction As traveling costs become higher and parking becomes sparse it is only natural to share rides or to carpool. Originally, carpooling was an arrangement among a group of people by which they take turns driving the others to and from a designated location. However, taking turns is not essential, instead passengers can share the cost of the ride with the driver. Carpooling has social advantages other than reducing the costs: it reduces fuel consumption and road congestion and frees parking space. While in the past carpooling was usually a fixed arrangement between friends or neighbors, the emergence of social networks h
Data Loading...
