Approximation Algorithms for Route Planning with Nonlinear Objectives
| Autor: | Yang, Ger, Nikolova, Evdokia |
|---|---|
| Rok vydání: | 2015 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We consider optimal route planning when the objective function is a general nonlinear and non-monotonic function. Such an objective models user behavior more accurately, for example, when a user is risk-averse, or the utility function needs to capture a penalty for early arrival. It is known that as nonlinearity arises, the problem becomes NP-hard and little is known about computing optimal solutions when in addition there is no monotonicity guarantee. We show that an approximately optimal non-simple path can be efficiently computed under some natural constraints. In particular, we provide a fully polynomial approximation scheme under hop constraints. Our approximation algorithm can extend to run in pseudo-polynomial time under a more general linear constraint that sometimes is useful. As a by-product, we show that our algorithm can be applied to the problem of finding a path that is most likely to be on time for a given deadline. Comment: 9 pages, 2 figures, main part of this paper is to be appear in AAAI'16 |
| Databáze: | arXiv |
| Externí odkaz: |
|