# Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms

* Auteur correspondant
2 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : Max-plus based methods have been recently developed to approximate the value function of possibly high dimensional optimal control problems. A critical step of these methods consists in approximating a function by a supremum of a small number of functions (max-plus "basis functions") taken from a prescribed dictionary. We study several variants of this approximation problem, which we show to be continuous versions of the facility location and $k$-center combinatorial optimization problems, in which the connection costs arise from a Bregman distance. We give theoretical error estimates, quantifying the number of basis functions needed to reach a prescribed accuracy. We derive from our approach a refinement of the curse of dimensionality free method introduced previously by McEneaney, with a higher accuracy for a comparable computational cost.
Type de document :
Pré-publication, Document de travail
8pages 5 figures. 2011
Domaine :

https://hal.inria.fr/hal-00935266
Contributeur : Zheng Qu <>
Soumis le : jeudi 23 janvier 2014 - 12:04:29
Dernière modification le : jeudi 11 janvier 2018 - 06:22:33

### Identifiants

• HAL Id : hal-00935266, version 1
• ARXIV : 1109.5241

### Citation

Stephane Gaubert, William Mceneaney, Zheng Qu. Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms. 8pages 5 figures. 2011. 〈hal-00935266〉

### Métriques

Consultations de la notice