A fair carpool scheduling algorithm
Abstract
We present a simple carpool scheduling algorithm in which no penalty is assessed to a carpool member who does not ride on any given day. The algorithm is shown to be fair, in a certain reasonable sense. The amount of bookkeeping grows only linearly with the number of carpool members.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The carpooling problem was first proposed and studied in Fagin and Williams (1983) and later studied in Ajtai et al. (1998).
“From the point of view of algorithm, the carpooling problem was first proposed and studied in Fagin and Williams (1983) and later studied in Ajtai et al. (1998).”
From PoliUniPool: a carpooling system for universities (2011) · cites this paper as Fagin and Williams (1983)
Ajtai et al. (1998) and Fagin and Williams (1983) mostly deal with online schemes, where the schedule of future arrivals of participants is not known.
“Ajtai et al. (1998) and Fagin and Williams (1983), for the most part, deal with online schemes, i.e. when the schedule of future arrivals of participants is not known.”
From PoliUniPool: a carpooling system for universities (2011) · cites this paper as Fagin and Williams (1983)
Cites
Still being checked.
Cited by
Sorted by citations
Optimization for dynamic ride-sharing: A review
Agatz, N. A. H., Erera, A. L., Savelsbergh, M. W. P., & Wang, X. (2012) · European Journal of Operational Research · doi:10.1016/j.ejor.2012.05.028 · Cited by 1,002 · see citing works
Cooperative Caching for Chip Multiprocessors
Chang, J., & Sohi, G. S. (2006) · ACM SIGARCH Computer Architecture News · doi:10.1145/1150019.1136509 · Cited by 356 · see citing works
Planning of truck platoons: A literature review and directions for future research
Bhoopalam, A. K., Agatz, N. A. H., & Zuidwijk, R. A. (2017) · Transportation Research Part B Methodological · doi:10.1016/j.trb.2017.10.016 · Cited by 303 · see citing works
Cooperative cache partitioning for chip multiprocessors
Chang, J., & Sohi, G. S. (2007) · International Conference on Supercomputing · doi:10.1145/1274971.1275005 · Cited by 266 · see citing works
A Genetic-Algorithm-Based Approach to Solve Carpool Service Problems in Cloud Computing
Huang, S.-C., Jiau, M., & Lin, C. (2014) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2014.2334597 · Cited by 94 · see citing works
Fair task assignment in spatial crowdsourcing
Chen, Z., Cheng, P., Chen, L., Lin, X., & Shahabi, C. (2020) · Proceedings of the VLDB Endowment · doi:10.14778/3407790.3407839 · Cited by 69 · see citing works
Walia, N. K., Kaur, N., Alowaidi, M. A., Bhatia, K. S., Mishra, S., Sharma, N. K., Sharma, S. K., & Kaur, H. (2021) · IEEE Access · doi:10.1109/access.2021.3105727 · Cited by 69 · see citing works
PoliUniPool: a carpooling system for universities
Bruglieri, M., Ciccarelli, D., Colorni, A., & Luè, A. (2011) · Procedia - Social and Behavioral Sciences · doi:10.1016/j.sbspro.2011.08.062 · Cited by 66 · see citing works
“Ajtai et al. (1998) and Fagin and Williams (1983), for the most part, deal with online schemes, i.e. when the schedule of future arrivals of participants is not known.”
BackgroundMethodOptimizing Taxi Carpool Policies via Reinforcement Learning and Spatio-Temporal Mining
Jindal, I., Qin, Z. T., Chen, X., Nokleby, M. S., & Ye, J. (2018) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata.2018.8622481 · Cited by 62 · see citing works
Optimization of the Carpool Service Problem via a Fuzzy-Controlled Genetic Algorithm
Huang, S.-C., Jiau, M., & Lin, C. (2014) · IEEE Transactions on Fuzzy Systems · doi:10.1109/tfuzz.2014.2374194 · Cited by 51 · see citing works
Ajtai, M., Aspnes, J., Naor, M., Rabani, Y., Schulman, L. J., & Waarts, O. (1998) · Journal of Algorithms · doi:10.1006/jagm.1998.0953 · Cited by 47 · see citing works
On fairness in the carpool problem
Naor, M. (2004) · Journal of Algorithms · doi:10.1016/j.jalgor.2004.05.001 · Cited by 44 · see citing works
A Model With a Heuristic Algorithm for Solving the Long-Term Many-to-Many Car Pooling Problem
Yan, S., Chen, C.-Y., & Lin, Y. (2011) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2011.2158209 · Cited by 42 · see citing works
Francez, N., & Kozen, D. C. (1984) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/800017.800515 · Cited by 39 · see citing works
An optimization model and a solution algorithm for the many-to-many car pooling problem
Yan, S., & Chen, C.-Y. (2011) · Annals of Operations Research · doi:10.1007/s10479-011-0948-6 · Cited by 36 · see citing works
Carpooling Service for Large-Scale Taxicab Networks
Zhang, D., He, T., Zhang, F., Lu, M., Liu, Y., Lee, H., & Son, S. H. (2016) · ACM Transactions on Sensor Networks · doi:10.1145/2897517 · Cited by 35 · see citing works
The taxi sharing practices: Matching, routing and pricing methods
Qiu, J., Huang, K., & Hawkins, J. (2022) · Multimodal Transportation · doi:10.1016/j.multra.2022.100003 · Cited by 35 · see citing works
Managing QoS through prioritization in web services
Sharma, A., Adarkar, H., & Sengupta, S. (2004) · doi:10.1109/wisew.2003.1286796 · Cited by 33 · see citing works
GIS-based identification and assessment of suitable meeting point locations for ride-sharing
Czioska, P., Mattfeld, D. C., & Sester, M. (2017) · Transportation research procedia · doi:10.1016/j.trpro.2017.03.038 · Cited by 25 · see citing works
Exploring fairness in participatory thermal comfort control in smart buildings
Shin, E.-J., Yus, R., Mehrotra, S., & Venkatasubramanian, N. (2017) · ACM International Conference on Systems for Energy-Efficient Buildings, Cities, and Transportation (BuildSys) · doi:10.1145/3137133.3137156 · Cited by 25 · see citing works
Optimizing the Carpool Service Problem with Genetic Algorithm in Service-Based Computing
Jiau, M., Huang, S.-C., & Lin, C.-H. (2013) · IEEE International Conference on Services Computing · doi:10.1109/scc.2013.56 · Cited by 24 · see citing works
Proving Fairness and Implementation Correctness of a Microkernel Scheduler
Daum, M., Dörrenbächer, J., & Wolff, B. (2009) · Journal of Automated Reasoning · doi:10.1007/s10817-009-9119-8 · Cited by 24 · see citing works
Optimizing carpool formation along high-occupancy vehicle lanes
Boysen, N., Briskorn, D., Schwerdfeger, S., & Stephan, K. (2021) · European Journal of Operational Research · doi:10.1016/j.ejor.2020.12.053 · Cited by 23 · see citing works
The optimality of the online greedy algorithm in carpool and chairman assignment problems
Coppersmith, D., Nowicki, T., Paleologo, G. A., Tresser, C. P., & Wu, C. W. (2011) · ACM Transactions on Algorithms · doi:10.1145/1978782.1978792 · Cited by 22 · see citing works
Tabu search for the real-world carpooling problem
Huang, C. Y., Zhang, D., Si, Y., & Leung, S. C. H. (2016) · Journal of Combinatorial Optimization · doi:10.1007/s10878-016-0015-y · Cited by 20 · see citing works
Cooperative Caching for Chip Multiprocessors
Chang, J., Herrero, E., Canal, R., & Sohi, G. S. (2011) · Wiley eBooks · doi:10.1002/9781119973584.ch13 · Cited by 18 · see citing works
Solution methods for the taxi pooling problem
Yan, S., Chen, C.-Y., & Wu, C.-C. (2011) · Transportation · doi:10.1007/s11116-011-9354-9 · Cited by 17 · see citing works
An intelligent carpooling app for a green social solution to traffic and parking congestions
Dakroub, O., Boukhater, C. M., Lahoud, F., Awad, M., & Artail, H. A. (2013) · IEEE International Conference on Intelligent Transportation Systems (ITSC) · doi:10.1109/itsc.2013.6728586 · Cited by 16 · see citing works
Recovery time of dynamic allocation processes
Czumaj, A. (1998) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/277651.277686 · Cited by 16 · see citing works
A decentralized solution to the car pooling problem
Kalczyński, P., & Miklas-Kalczynska, M. (2018) · International Journal of Sustainable Transportation · doi:10.1080/15568318.2018.1440674 · Cited by 14 · see citing works
An intelligent and fair GA carpooling scheduler as a social solution for greener transportation
Boukhater, C. M., Dakroub, O., Lahoud, F., Awad, M., & Artail, H. A. (2014) · IEEE Mediterranean Electrotechnical Conference (MELECON) · doi:10.1109/melcon.2014.6820528 · Cited by 14 · see citing works
Ma, J., Panic, D., Yus, R., & Bouloukakis, G. (2024) · IEEE International Conference on Pervasive Computing and Communications · doi:10.1109/percom59722.2024.10494430 · Cited by 13 · see citing works
A cloud computing framework for real-time carpooling services
Lin, C., Jiau, M., & Huang, S.-C. (2012) · International Conference on New Trends in Information Science, Service Science and Data Mining · Cited by 13 · see citing works
Optimizing ride matches for dynamic ride-sharing systems
Wang, X. (2013) · SMARTech Repository (Georgia Institute of Technology) · Cited by 13 · see citing works
Planning of Truck Platoons: A Literature Review and Directions for Future ResearchPreprint
Bhoopalam, A. K., Agatz, N. A. H., & Zuidwijk, R. A. (2017) · SSRN Electronic Journal · doi:10.2139/ssrn.2988195 · Cited by 11 · see citing works
Minimizing the average arriving distance in carpooling
Zhao, T., Yang, Y., & Wang, E. (2020) · International Journal of Distributed Sensor Networks · doi:10.1177/1550147719899369 · Cited by 9 · see citing works
Research on Strategy Control of Taxi Carpooling Detour Route under Uncertain Environment
Zhang, W., He, R., Xiao, Q., & Ma, C. (2016) · Discrete Dynamics in Nature and Society · doi:10.1155/2016/4702360 · Cited by 7 · see citing works
Bounding the errors for convex dynamics on one or more polytopes
Tresser, C. P. (2007) · Chaos An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.2747053 · Cited by 6 · see citing works
On Effective Scheduling in Computing Clusters
Grushin, D. A., & Kuzyurin, N. N. (2019) · Programming and Computer Software · doi:10.1134/s0361768819070077 · Cited by 6 · see citing works
A Mobile, Dynamic, and Privacy‐Preserving Matching System for Car and Taxi Pools
Chiou, S.-Y., & Chen, Y.-C. (2014) · Mathematical Problems in Engineering · doi:10.1155/2014/579031 · Cited by 5 · see citing works
An Analysis of the Taxi-Sharing Organizing and Pricing
Huang, K., Liu, F., Hu, Y., & Liu, Z. (2017) · Lecture notes in electrical engineering · doi:10.1007/978-981-10-3551-7_20 · Cited by 5 · see citing works
Convex dynamics: Unavoidable difficulties in bounding some greedy algorithms
Nowicki, T., & Tresser, C. P. (2003) · Chaos An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.1624652 · Cited by 5 · see citing works
Recovery Time of Dynamic Allocation Processes
Czumaj, A. (2000) · Theory of Computing Systems · doi:10.1007/s002240010012 · Cited by 5 · see citing works
Passenger Search by Spatial Index for Ridesharing
Cho, C.-W., Wu, Y., Yen, C., & Chang, C. (2011) · Conference on Technologies and Applications of Artificial Intelligence (TAAI) · doi:10.1109/taai.2011.23 · Cited by 4 · see citing works
Online Discrepancy with Recourse for Vectors and Graphs
Gupta, A., Gurunathan, V., Krishnaswamy, R., Kumar, A., & Singla, S. (2022) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611977073.57 · Cited by 4 · see citing works
Classification of ride-sharing partners based on multiple constraints
Kammerdiener, T., & Zhang, H. (2011) · Journal of computing sciences in colleges · doi:10.5555/1953573.1953589 · Cited by 4 · see citing works
Ma, J., Panic, D., Yus, R., & Bouloukakis, G. (2025) · Pervasive and Mobile Computing · doi:10.1016/j.pmcj.2025.102076 · Cited by 3 · see citing works
iFair: Achieving Fairness in the Allocation of Scarce Resources for Senior Health Care
Kenne, M. M., Date, P., Eguchi, R. T., Hu, Z., Rousseau, J., & Venkatasubramanian, N. (2024) · IEEE International Conference on Smart Computing · doi:10.1109/smartcomp61445.2024.00025 · Cited by 3 · see citing works
Multiprocessor Fair Scheduling Based on an Improved Slime Mold Algorithm
Dai, M., & Jiang, Z. (2023) · Algorithms · doi:10.3390/a16100473 · Cited by 3 · see citing works
On the formal foundation of a verification approach for system-level concurrent programs
Daum, M. (2010) · Publications of the UdS (Saarland University) · doi:10.22028/d291-26012 · Cited by 3 · see citing works
A Carpooling Open Application with Social Oriented Reward Mechanism
Bonarrigo, S., Carchiolo, V., Longheu, A., Loria, M. P., Malgeri, M., & Mangioni, G. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-11692-1_38 · Cited by 2 · see citing works
Carpooling Using Genetic Algorithm
Bagde, G., Sonar, S., Prsad, A., & Helkar, V. (2015) · Cited by 2 · see citing works
The Family Holiday Gathering Problem or Fair and Periodic Scheduling of Independent Sets
Amir, A., Kapah, O., Kopelowitz, T., Naor, M., & Porat, E. (2016) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/2935764.2935788 · Cited by 2 · see citing works
Plus Go: Intelligent Complementary Ride-Sharing System
Wickramasinghe, V., Edirisinghe, A., Gunawardena, S., Gunathilake, A., Kasthurirathna, D., & Wijekoon, J. (2019) · International Conference on Advancements in Computing (ICAC) · doi:10.1109/icac49085.2019.9103395 · Cited by 2 · see citing works
Individual and collective rationality in carpooling
Kalczyński, P., & Lewandowski, M. (2025) · European Journal of Operational Research · doi:10.1016/j.ejor.2025.10.036 · Cited by 1 · see citing works
Capturing Fair Computations on Concurrent Constraint Language
Campli, P., & Bistarelli, S. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-02846-5_63 · Cited by 1 · see citing works
MobiHerd: Towards Enabling Cost-Effective and Scalable Mobile Group Buying
Raravi, G., Mondal, A., Rajasubramaniam, T., & Singh, A. K. (2016) · IEEE International Conference on Mobile Data Management (MDM) · doi:10.1109/mdm.2016.18 · Cited by 1 · see citing works
Schedule situations and their cooperative game theoretic representations
Munich, L. (2024) · European Journal of Operational Research · doi:10.1016/j.ejor.2024.02.012 · Cited by 1 · see citing works
Tsao, H.-S. J., & Eirinaki, M. (2015) · Procedia Manufacturing · doi:10.1016/j.promfg.2015.07.729 · Cited by 1 · see citing works
The Offline Carpool Problem Revisited
Mneimneh, S., & Farhat, S. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48054-0_40 · Cited by 1 · see citing works
Whose Turn Is It to Drive Today?
Lins, B. (2015) · Math Horizons · doi:10.4169/mathhorizons.23.2.16 · Cited by 1 · see citing works
On an effective scheduling problem in computation clusters
Grushin, D. A., & Kuzyurin, N. N. (2018) · Proceedings of the Institute for System Programming of RAS · doi:10.15514/ispras-2018-30(6)-7 · Cited by 1 · see citing works
Computational Issues in Long-term Fairness Among Groups of Agents
Balan, G. (2010) · doi:10.13021/mars/4977 · Cited by 1 · see citing works
The Family Holiday Gathering Problem or Fair and Periodic Scheduling of Independent SetsPreprint
Amir, A., Kapah, O., Kopelowitz, T., Naor, M., & Porat, E. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1408.2279 · Cited by 1 · see citing works
CORSA: An Open Solution for Social Oriented Real-time Ride Sharing
Bonarrigo, S., Carchiolo, V., Longheu, A., Loria, M. P., Malgeri, M., & Mangioni, G. (2015) · MATEC Web of Conferences · doi:10.1051/matecconf/20152806002
Simulative analysis of multimedia traffic over LTE with real time scenarios in network simulator-3
Nandu, T. S., Krishnan, N., Theja, K. H., Pattnaik, B., Anilal, P., & Sai, S. S. S. (2014) · IEEE International Conference on Advanced Networks and Telecommunications Systems · doi:10.1109/ants.2014.7057250
Design of Next Generation Smart Surface Transportation System
Chang, F. H., & Garg, H. K. (2017) · International Conference on Vehicle Technology and Intelligent Transport Systems (VEHITS) · doi:10.5220/0006376603590365
Fairness as a QoS Measure for Web ServicesPreprint
Bistarelli, S., & Campli, P. (2012)
Fiat, A., Karlin, A. R., Koutsoupias, E., Mathieu, C., & Zach, R. (2017) · Trends in mathematics · doi:10.1007/978-3-319-51753-7_5
SIGACT News Online Algorithms Column 40
Amouzandeh, A., Schmitt, S., & van Stee, R. (2023) · ACM SIGACT News · doi:10.1145/3586165.3586177
Shukla, P. S. (2023) · INTERANTIONAL JOURNAL OF SCIENTIFIC RESEARCH IN ENGINEERING AND MANAGEMENT · doi:10.55041/ijsrem17946
- Authors
- Fagin, R., & Williams, J. H.
- Affiliations
- IBM (United States) (US)
- Venue
- IBM Journal of Research and Development
- Publisher
- IBM
- Published
- 1983-03
- Volume
- 27
- Issue
- 2
- Pages
- 133-139
- ISSN
- 0018-8646 (ISSN-L)
- OpenAlex
- W2063709997
- Cited by
- 73
- References
- 0
- Citations by year
- 2025: 2 · 2024: 3 · 2023: 3 · 2022: 2 · 2021: 2 · 2020: 2 · 2019: 2 · 2018: 4 · 2017: 7 · 2016: 5 · 2015: 5 · 2014: 7 · 2013: 3 · 2012: 3
- FWCI
- 1.86
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IBM Journal of Research and Development (publishedVersion)
- Topics
- Physical Sciences › Engineering › Automotive Engineering › Transportation and Mobility Innovations
- Social Sciences › Transportation › Transportation Planning and Optimization
- Social Sciences › Economics, Econometrics and Finance › Economics and Econometrics › Game Theory and Voting Systems
- Keywords
- fair scheduling, ride-sharing, scheduling algorithms, fairness
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
