Local search algorithms for the maximum carpool matching problem

DOI10.4230/LIPICS.ESA.2017.55MaRDI QIDQ5111744zbMATH OpenFDO

Authors Gilad Kutiel, Dror Rawitz

Publication date 27 May 2020

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2017.55

zbMATH Keywords

local searchapproximation algorithmssubmodular maximizationstar packing

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Matching models (91B68)

Recommendations

• Local search algorithms for the maximum carpool matching problem
• Approximation algorithms for the maximum carpool matching problem
• Carpooling in social networks
• Approximate ridesharing of personal vehicles problem
• The optimality of the online greedy algorithm in carpool and chairman assignment problems

Cites work

• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• An Improved Approximation Bound for Spanning Star Forest and Color Saving
• Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
• Approximation algorithms for the maximum carpool matching problem
• Approximations for maximum transportation with permutable supply vector and other capacitated star packing problems
• Deterministic algorithms for submodular maximization problems
• Greedy local improvement and weighted set packing approximation
• Improved approximation algorithms for the spanning star forest problem
• Improved approximation algorithms for weighted 2-path partitions
• On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
• Optimization for dynamic ride-sharing: a review
• Scalability issues in optimal assignment for carpooling

Cited in

(3)

• Approximation algorithms for the maximum carpool matching problem
• Approximate ridesharing of personal vehicles problem
• Local search algorithms for the maximum carpool matching problem

This page was built for publication: Local search 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 Q5111744)