Local Search Algorithms for Maximum Carpool Matching

Authors Gilad Kutiel, Dror Rawitz



PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.55.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Gilad Kutiel
Dror Rawitz

Cite AsGet BibTex

Gilad Kutiel and Dror Rawitz. Local Search Algorithms for Maximum Carpool Matching. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 55:1-55:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ESA.2017.55

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 -> N, and a weight function w: A -> R^+, a carpool matching is a subset of arcs, M subseteq A, such that every v in V satisfies: (i) d^{in}_M(v) cdot d^{out}_M(v) = 0, (ii) d^{in}_M(v) <= c(v), and (iii) d^{out}_M(v) <= 1. A vertex v for which d^{out}_M(v) = 1 is a passenger, and a vertex for which d^{out}_M(v) = 0 is a driver who has d^{in}_M(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, 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 Maximum Carpool Matching where each vertex represents an unsplittable group of passengers. Formally, each vertex u in V has a size s(u) in N, and the constraint d^{in}_M(v) <= c(v) is replaced with sum_{u:(u,v) in M} s(u) <= c(v). We show that Maximum Carpool Matching can be formulated as an unconstrained submodular maximization problem, thus it admits a 1/2-approximation algorithm. We show that the same formulation does not work for Maximum Group Carpool Matching, nevertheless, we present a local search (1/2 - epsilon)-approximation algorithm for Maximum Group Carpool Matching. For the unweighted variant of both problems when the maximum possible capacity, c_{max}, is bounded by a constant, we provide a local search (1/2 + 1/{2c_{max}} - epsilon)-approximation algorithm. We also show that the problem is APX-hard, even if the maximum degree and c_{max} are at most 3.
Keywords
  • approximation algorithms
  • local search
  • star packing
  • submodular maximization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Blablacar. URL: https://www.blablacar.com.
  2. Moovit carpool. URL: https://moovitapp.com/.
  3. Waze. URL: https://www.waze.com/.
  4. Zimride by enterprise. URL: https://zimride.com/.
  5. Niels A. H. Agatz, Alan L. Erera, Martin W. P. Savelsbergh, and Xing Wang. Optimization for dynamic ride-sharing: A review. European Journal of Operational Research, 223(2):295-303, 2012. Google Scholar
  6. Esther M. Arkin, Refael Hassin, Shlomi Rubinstein, and Maxim Sviridenko. Approximations for maximum transportation with permutable supply vector and other capacitated star packing problems. Algorithmica, 39(2):175-187, 2004. Google Scholar
  7. Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis, and Maria Kyropoulou. An improved approximation bound for spanning star forest and color saving. In 34th International Symposium on Mathematical Foundations of Computer Science, pages 90-101, 2009. Google Scholar
  8. Amotz Bar-Noy, David Peleg, George Rabanca, and Ivo Vigan. Improved approximation algorithms for weighted 2-path partitions. In 23rd Annual European Symposium on Algorithms, volume 9294 of LNCS, pages 953-964, 2015. Google Scholar
  9. Niv Buchbinder and Moran Feldman. Deterministic algorithms for submodular maximization problems. In 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 392-403, 2016. Google Scholar
  10. Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM J. Comput., 44(5):1384-1402, 2015. Google Scholar
  11. Deeparnab Chakrabarty and Gagan Goel. On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP. SIAM J. Comput., 39(6):2189-2211, 2010. Google Scholar
  12. Barun Chandra and Magnús M. Halldórsson. Greedy local improvement and weighted set packing approximation. J. Algorithms, 39(2):223-240, 2001. Google Scholar
  13. Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra, and Gyanit Singh. Improved approximation algorithms for the spanning star forest problem. Algorithmica, 65(3):498-516, 2013. Google Scholar
  14. Irith Ben-Arroyo Hartman. Optimal assignment for carpooling. submitted. Google Scholar
  15. Irith Ben-Arroyo Hartman, Daniel Keren, Abed Abu Dbai, Elad Cohen, Luk Knapen, Ansar-Ul-Haque Yasar, and Davy Janssens. Theory and practice in large carpooling problems. In 5th International Conference on Ambient Systems, Networks and Technologies, pages 339-347, 2014. Google Scholar
  16. Luk Knapen, Daniel Keren, Ansar-Ul-Haque Yasar, Sungjin Cho, Tom Bellemans, Davy Janssens, and Geert Wets. Estimating scalability issues while finding an optimal assignment for carpooling. In 4th International Conference on Ambient Systems, Networks and Technologies, pages 372-379, 2013. Google Scholar
  17. Luk Knapen, Ansar-Ul-Haque Yasar, Sungjin Cho, Daniel Keren, Abed Abu Dbai, Tom Bellemans, Davy Janssens, Geert Wets, Assaf Schuster, Izchak Sharfman, and Kanishka Bhaduri. Exploiting graph-theoretic tools for matching in carpooling applications. J. Ambient Intelligence and Humanized Computing, 5(3):393-407, 2014. Google Scholar
  18. Gilad Kutiel. Approximation algorithms for the maximum carpool matching problem. In 12th International Computer Science Symposium in Russia, volume 10304 of LNCS, pages 206-216, 2017. Google Scholar
  19. C. Thach Nguyen, Jian Shen, Minmei Hou, Li Sheng, Webb Miller, and Louxin Zhang. Approximating the spanning star forest problem and its application to genomic sequence alignment. SIAM J. Comput., 38(3):946-962, 2008. Google Scholar
  20. Christos Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. In 12th Annual ACM Symposium on Theory of Computing, pages 229-234, 1988. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail