Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Approximate Ridesharing of Personal Vehicles Problem   The ridesharing problem is that given a set of trips, each trip consists of
an individual, a vehicle of the individual and some requirements, select a
subset of trips and use the vehicles of selected trips to deliver all
individuals to their destinations satisfying the requirements. Requirements of
trips are specified by parameters including source, destination, vehicle
capacity, preferred paths of a driver, detour distance and number of stops a
driver is willing to make, and time constraints. We analyze the relations
between the time complexity and parameters for two optimization problems:
minimizing the number of selected vehicles and minimizing total travel distance
of the vehicles. We consider the following conditions: (1) all trips have the
same source or same destination, (2) no detour is allowed, (3) each participant
has one preferred path, (4) no limit on the number of stops, and (5) all trips
have the same departure and same arrival time. It is known that both
minimization problems are NP-hard if one of Conditions (1), (2) and (3) is not
satisfied. We prove that both problems are NP-hard and further show that it is
NP-hard to approximate both problems within a constant factor if Conditions (4)
or (5) is not satisfied. We give $\frac{K+2}{2}$-approximation algorithms for
minimizing the number of selected vehicles when condition (4) is not satisfied,
where $K$ is the largest capacity of all vehicles.

35
The categories of this paper are: mtrl-th
10
The categories of this paper are: q-bio
2
The categories of this paper are: math
24
The categories of this paper are: dg-ga
29
The categories of this paper are: funct-an
7
The categories of this paper are: hep-th
17
The categories of this paper are: q-fin
30
The categories of this paper are: q-alg
11
The categories of this paper are: hep-lat
18
The categories of this paper are: econ
9
The categories of this paper are: nlin
0
The categories of this paper are: hep-ph
33
The categories of this paper are: plasm-ph
3
The categories of this paper are: physics
37
The categories of this paper are: supr-con
4
The categories of this paper are: cond-mat