  Consider a customer who needs to fulfill a shopping list, and also a personal
shopper who is willing to buy and resell to customers the goods in their
shopping lists. It is in the personal shopper's best interest to find
(shopping) routes that (i) minimize the time serving a customer, in order to be
able to serve more customers, and (ii) minimize the price paid for the goods,
in order to maximize his/her potential profit when reselling them. Those are
typically competing criteria leading to what we refer to as the Personal
Shopper's Dilemma query, i.e., to determine where to buy each of the required
goods while attempting to optimize both criteria at the same time. Given the
query's NP-hardness we propose a heuristic approach to determine a subset of
the sub-optimal routes under any linear combination of the aforementioned
criteria, i.e., the query's approximate linear skyline set. In order to measure
the effectiveness of our approach we also introduce two new metrics, optimality
and coverage gaps w.r.t. an optimal, but computationally expensive, baseline
solution. Our experiments, using realistic city-scale datasets, show that our
proposed approach is two orders of magnitude faster than the baseline and
yields low values for the optimality and coverage gaps.
