Approximation Algorithms for Car-Sharing Problems

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review


We consider several variants of a car-sharing problem. Given are a number of requests each consisting of a pick-up location and a drop-off location, a number of cars, and nonnegative, symmetric travel times that satisfy the triangle inequality. Each request needs to be served by a car, which means that a car must first visit the pick-up location of the request, and then visit the drop-off location of the request. Each car can serve two requests. One problem is to serve all requests with the minimum total travel time (called), and the other problem is to serve all requests with the minimum total latency (called). We also study the special case where the pick-up and drop-off location of a request coincide. We propose two basic algorithms, called the match and assign algorithm and the transportation algorithm. We show that the best of the resulting two solutions is a 2-approximation for (and a 7/5-approximation for its special case), and a 5/3-approximation for (and a 3/2-approximation for its special case); these ratios are better than the ratios of the individual algorithms. Finally, we indicate how our algorithms can be applied to more general settings where each car can serve more than two requests, or where cars have distinct speeds.

Originele taal-2Engels
TitelComputing and Combinatorics - 26th International Conference, COCOON 2020, Proceedings
RedacteurenDonghyun Kim, R.N. Uma, Zhipeng Cai, Dong Hoon Lee
Aantal pagina's12
ISBN van geprinte versie9783030581497
StatusGepubliceerd - 2020
Evenement26th International Conference on Computing and Combinatorics, COCOON 2020 - Atlanta, Verenigde Staten van Amerika
Duur: 29 aug 202031 aug 2020

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12273 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349


Congres26th International Conference on Computing and Combinatorics, COCOON 2020
LandVerenigde Staten van Amerika

Vingerafdruk Duik in de onderzoeksthema's van 'Approximation Algorithms for Car-Sharing Problems'. Samen vormen ze een unieke vingerafdruk.

Citeer dit