Name
Abstract | ||
|---|---|---|
We address the carpooling problem as a graph-theoretic problem. If the set of drivers is known in advance, then for any car capacity, the problem is equivalent to the assignment problem in bipartite graphs. Otherwise, when we do not know in advance who will drive their vehicle and who will be a passenger, the problem is NP-hard. We devise and implement quick heuristics for both cases, based on graph algorithms, as well as parallel algorithms based on geometric/algebraic approach. We compare between the algorithms on random graphs, as well as on real, very large, data. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.procs.2014.05.433 | Procedia Computer Science |
Keywords | Field | DocType |
Carpooling,Linear Programming,Maximum Weighted Matching,Star Partition Problem,Gradient Projection Algorithm,Scalability,Incremental Algorithms | Graph algorithms,Mathematical optimization,Random graph,Algebraic number,Computer science,Parallel algorithm,Bipartite graph,Heuristics,Assignment problem,Linear programming,Artificial intelligence,Machine learning | Conference |
Volume | ISSN | Citations |
32 | 1877-0509 | 3 |
PageRank | References | Authors |
0.44 | 2 | 7 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Irith Ben-Arroyo Hartman | 1 | 34 | 7.87 |
| Daniel Keren | 2 | 931 | 116.90 |
| Abed Abu Dbai | 3 | 12 | 1.30 |
| Elad Cohen | 4 | 3 | 0.44 |
| Luk Knapen | 5 | 86 | 22.42 |
| Ansar-Ul-Haque Yasar | 6 | 118 | 42.31 |
| Davy Janssens | 7 | 238 | 38.08 |