Intrinsic complexity estimates in polynomial optimization

Abstract : It is known that point searching in basic semialgebraic sets and the search for globally minimal points in polynomial optimization tasks can be carried out using $(s\,d)^{O(n)}$ arithmetic operations, where $n$ and $s$ are the numbers of variables and constraints and $d$ is the maximal degree of the polynomials involved.\spar \noindent We associate to each of these problems an intrinsic system degree which becomes in worst case of order $(n\,d)^{O(n)}$ and which measures the intrinsic complexity of the task under consideration.\spar \noindent We design non-uniformly deterministic or uniformly probabilistic algorithms of intrinsic, quasi-polynomial complexity which solve these problems.
Type de document :
Article dans une revue
Journal of Complexity, Elsevier, 2014, 30 (4), pp.430-443. 〈10.1016/j.jco.2014.02.005〉
Liste complète des métadonnées

Littérature citée [47 références]  Voir  Masquer  Télécharger
Contributeur : Mohab Safey El Din <>
Soumis le : lundi 10 février 2014 - 17:39:28
Dernière modification le : samedi 16 décembre 2017 - 07:18:04
Document(s) archivé(s) le : dimanche 11 mai 2014 - 07:35:10


Fichiers produits par l'(les) auteur(s)




Bernd Bank, Marc Giusti, Joos Heintz, Mohab Safey El Din. Intrinsic complexity estimates in polynomial optimization. Journal of Complexity, Elsevier, 2014, 30 (4), pp.430-443. 〈10.1016/j.jco.2014.02.005〉. 〈hal-00815123v2〉



Consultations de la notice


Téléchargements de fichiers