A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms
- Author
- MONTEIRO, Renato D. C1 ; TSUCHIYA, Takashi2
[1] School of Industrial and Systems Engineering, Georgia Institute of Technology, 765 Ferst St, Atlanta, GA 30332, United States
[2] The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-Ku, Tokyo, 106-8569, Japan - Source
Mathematical programming. 2008, Vol 115, Num 1, pp 105-149, 45 p ; ref : 22 ref
- CODEN
- MHPGA4
- ISSN
- 0025-5610
- Scientific domain
- Control theory, operational research; Mathematics
- Publisher
- Springer, Heidelberg
- Publication country
- Germany
- Document type
- Article
- Language
- English
- Author keyword
- Affine scaling Central path Condition number Crossover events Curvature Interior-point algorithms Layered least squares steps Linear programming Path-following Polynomial complexity Predictor-corrector Primal-dual algorithms Scale-invariance Strongly polynomial
- Keyword (fr)
- Algorithme approximation Complexité polynômial Courbure Invariance échelle Invariant Justification Matrice M Méthode moindre carré Méthode point intérieur Méthode primale duale Méthode prédicteur correcteur Méthode suivi chemin Optimisation combinatoire Optimisation sous contrainte Programmation linéaire Programmation mathématique Préconditionnement Structure géométrique Transformation affine Transformation échelle
- Keyword (en)
- Approximation algorithm Polynomial complexity Curvature Scale invariance Invariant Justification M matrix Least squares method Interior point method Primal dual method Predictor corrector method Path following method Combinatorial optimization Constrained optimization Linear programming Mathematical programming Preconditioning Geometrical structure Affine transformation Scale transformation
- Keyword (es)
- Algoritmo aproximación Complejidad polinomial Curvatura Invarianza escala Invariante Justificación Matriz M Método cuadrado menor Método punto interior Método primal dual Método predictor corrector Método seguido camino Optimización combinatoria Optimización con restricción Programación lineal Programación matemática Precondicionamiento Estructura geométrica Transformación afín Transformación escala
- Classification
- Pascal
- 001 Exact sciences and technology / 001D Applied sciences / 001D01 Operational research. Management science / 001D01A Operational research and scientific management / 001D01A03 Mathematical programming
- Pascal
- 001 Exact sciences and technology / 001D Applied sciences / 001D01 Operational research. Management science / 001D01A Operational research and scientific management / 001D01A04 Flows in networks. Combinatorial problems
- Discipline
- Operational research. Management
- Origin
- Inist-CNRS
- Database
- PASCAL
- INIST identifier
- 20353978
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Access to the document
Install on your browser
DOI
10.1007/s10107-007-0141-5 
https://dx.doi.org/10.1007/s10107-007-0141-5
"O:13:\"PanistOpenUrl\":36:{s:10:\"\u0000*\u0000openUrl\";N;s:6:\"\u0000*\u0000idc\";N;s:6:\"\u0000*\u0000fmt\";s:7:\"journal\";s:6:\"\u0000*\u0000doi\";s:25:\"10.1007\/s10107-007-0141-5\";s:6:\"\u0000*\u0000pii\";s:0:\"\";s:7:\"\u0000*\u0000pmid\";s:0:\"\";s:9:\"\u0000*\u0000atitle\";s:155:\"A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms\";s:9:\"\u0000*\u0000jtitle\";s:24:\"Mathematical programming\";s:9:\"\u0000*\u0000stitle\";s:13:\"Math. program\";s:7:\"\u0000*\u0000date\";s:4:\"2008\";s:9:\"\u0000*\u0000volume\";s:3:\"115\";s:8:\"\u0000*\u0000issue\";s:1:\"1\";s:8:\"\u0000*\u0000spage\";s:3:\"105\";s:8:\"\u0000*\u0000epage\";s:3:\"149\";s:8:\"\u0000*\u0000pages\";s:0:\"\";s:7:\"\u0000*\u0000issn\";s:9:\"0025-5610\";s:8:\"\u0000*\u0000eissn\";s:0:\"\";s:9:\"\u0000*\u0000aulast\";s:8:\"MONTEIRO\";s:10:\"\u0000*\u0000aufirst\";s:11:\"Renato D. C\";s:9:\"\u0000*\u0000auinit\";s:0:\"\";s:10:\"\u0000*\u0000auinitm\";s:0:\"\";s:5:\"\u0000*\u0000au\";a:1:{i:0;s:17:\"TSUCHIYA, Takashi\";}s:9:\"\u0000*\u0000aucorp\";s:0:\"\";s:7:\"\u0000*\u0000isbn\";s:0:\"\";s:8:\"\u0000*\u0000coden\";s:6:\"MHPGA4\";s:8:\"\u0000*\u0000genre\";s:7:\"article\";s:7:\"\u0000*\u0000part\";s:0:\"\";s:9:\"\u0000*\u0000btitle\";s:0:\"\";s:8:\"\u0000*\u0000title\";s:155:\"A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms\";s:8:\"\u0000*\u0000place\";s:10:\"Heidelberg\";s:6:\"\u0000*\u0000pub\";s:8:\"Springer\";s:10:\"\u0000*\u0000edition\";s:0:\"\";s:9:\"\u0000*\u0000tpages\";s:2:\"45\";s:9:\"\u0000*\u0000series\";s:0:\"\";s:8:\"\u0000*\u0000proxy\";s:30:\"http:\/\/proxyout.inist.fr:8080\/\";s:12:\"\u0000*\u0000integrite\";b:1;}"
Panist access
"O:12:\"IstexOpenUrl\":35:{s:10:\"\u0000*\u0000openUrl\";N;s:6:\"\u0000*\u0000fmt\";s:7:\"journal\";s:6:\"\u0000*\u0000doi\";s:25:\"10.1007\/s10107-007-0141-5\";s:6:\"\u0000*\u0000pii\";s:0:\"\";s:7:\"\u0000*\u0000pmid\";s:0:\"\";s:9:\"\u0000*\u0000atitle\";s:155:\"A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms\";s:9:\"\u0000*\u0000jtitle\";s:24:\"Mathematical programming\";s:9:\"\u0000*\u0000stitle\";s:13:\"Math. program\";s:7:\"\u0000*\u0000date\";s:4:\"2008\";s:9:\"\u0000*\u0000volume\";s:3:\"115\";s:8:\"\u0000*\u0000issue\";s:1:\"1\";s:8:\"\u0000*\u0000spage\";s:3:\"105\";s:8:\"\u0000*\u0000epage\";s:3:\"149\";s:8:\"\u0000*\u0000pages\";s:0:\"\";s:7:\"\u0000*\u0000issn\";s:9:\"0025-5610\";s:8:\"\u0000*\u0000eissn\";s:0:\"\";s:9:\"\u0000*\u0000aulast\";s:8:\"MONTEIRO\";s:10:\"\u0000*\u0000aufirst\";s:11:\"Renato D. C\";s:9:\"\u0000*\u0000auinit\";s:0:\"\";s:10:\"\u0000*\u0000auinitm\";s:0:\"\";s:5:\"\u0000*\u0000au\";a:1:{i:0;s:17:\"TSUCHIYA, Takashi\";}s:9:\"\u0000*\u0000aucorp\";s:0:\"\";s:7:\"\u0000*\u0000isbn\";s:0:\"\";s:8:\"\u0000*\u0000coden\";s:6:\"MHPGA4\";s:8:\"\u0000*\u0000genre\";s:7:\"article\";s:7:\"\u0000*\u0000part\";s:0:\"\";s:9:\"\u0000*\u0000btitle\";s:0:\"\";s:8:\"\u0000*\u0000title\";s:155:\"A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms\";s:8:\"\u0000*\u0000place\";s:10:\"Heidelberg\";s:6:\"\u0000*\u0000pub\";s:8:\"Springer\";s:10:\"\u0000*\u0000edition\";s:0:\"\";s:9:\"\u0000*\u0000tpages\";s:2:\"45\";s:9:\"\u0000*\u0000series\";s:0:\"\";s:8:\"\u0000*\u0000proxy\";s:30:\"http:\/\/proxyout.inist.fr:8080\/\";s:12:\"\u0000*\u0000integrite\";b:1;}"
Istex access
"O:16:\"UnpaywallOpenUrl\":35:{s:8:\"\u0000*\u0000email\";s:27:\"assistance-portail@inist.fr\";s:6:\"\u0000*\u0000fmt\";N;s:6:\"\u0000*\u0000doi\";s:25:\"10.1007\/s10107-007-0141-5\";s:6:\"\u0000*\u0000pii\";N;s:7:\"\u0000*\u0000pmid\";N;s:9:\"\u0000*\u0000atitle\";N;s:9:\"\u0000*\u0000jtitle\";N;s:9:\"\u0000*\u0000stitle\";N;s:7:\"\u0000*\u0000date\";N;s:9:\"\u0000*\u0000volume\";N;s:8:\"\u0000*\u0000issue\";N;s:8:\"\u0000*\u0000spage\";N;s:8:\"\u0000*\u0000epage\";N;s:8:\"\u0000*\u0000pages\";N;s:7:\"\u0000*\u0000issn\";N;s:8:\"\u0000*\u0000eissn\";N;s:9:\"\u0000*\u0000aulast\";N;s:10:\"\u0000*\u0000aufirst\";N;s:9:\"\u0000*\u0000auinit\";N;s:10:\"\u0000*\u0000auinitm\";N;s:5:\"\u0000*\u0000au\";N;s:9:\"\u0000*\u0000aucorp\";N;s:7:\"\u0000*\u0000isbn\";N;s:8:\"\u0000*\u0000coden\";N;s:8:\"\u0000*\u0000genre\";N;s:7:\"\u0000*\u0000part\";N;s:9:\"\u0000*\u0000btitle\";N;s:8:\"\u0000*\u0000title\";N;s:8:\"\u0000*\u0000place\";N;s:6:\"\u0000*\u0000pub\";N;s:10:\"\u0000*\u0000edition\";N;s:9:\"\u0000*\u0000tpages\";N;s:9:\"\u0000*\u0000series\";N;s:8:\"\u0000*\u0000proxy\";s:30:\"http:\/\/proxyout.inist.fr:8080\/\";s:12:\"\u0000*\u0000integrite\";N;}"
Unpaywall access
"O:16:\"EuropePMCOpenUrl\":35:{s:10:\"\u0000*\u0000openUrl\";N;s:6:\"\u0000*\u0000fmt\";s:7:\"journal\";s:6:\"\u0000*\u0000doi\";s:25:\"10.1007\/s10107-007-0141-5\";s:6:\"\u0000*\u0000pii\";s:0:\"\";s:7:\"\u0000*\u0000pmid\";s:0:\"\";s:9:\"\u0000*\u0000atitle\";s:155:\"A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms\";s:9:\"\u0000*\u0000jtitle\";s:24:\"Mathematical programming\";s:9:\"\u0000*\u0000stitle\";s:13:\"Math. program\";s:7:\"\u0000*\u0000date\";s:4:\"2008\";s:9:\"\u0000*\u0000volume\";s:3:\"115\";s:8:\"\u0000*\u0000issue\";s:1:\"1\";s:8:\"\u0000*\u0000spage\";s:3:\"105\";s:8:\"\u0000*\u0000epage\";s:3:\"149\";s:8:\"\u0000*\u0000pages\";s:0:\"\";s:7:\"\u0000*\u0000issn\";s:9:\"0025-5610\";s:8:\"\u0000*\u0000eissn\";s:0:\"\";s:9:\"\u0000*\u0000aulast\";s:8:\"MONTEIRO\";s:10:\"\u0000*\u0000aufirst\";s:11:\"Renato D. C\";s:9:\"\u0000*\u0000auinit\";s:0:\"\";s:10:\"\u0000*\u0000auinitm\";s:0:\"\";s:5:\"\u0000*\u0000au\";a:1:{i:0;s:17:\"TSUCHIYA, Takashi\";}s:9:\"\u0000*\u0000aucorp\";s:0:\"\";s:7:\"\u0000*\u0000isbn\";s:0:\"\";s:8:\"\u0000*\u0000coden\";s:6:\"MHPGA4\";s:8:\"\u0000*\u0000genre\";s:7:\"article\";s:7:\"\u0000*\u0000part\";s:0:\"\";s:9:\"\u0000*\u0000btitle\";s:0:\"\";s:8:\"\u0000*\u0000title\";s:155:\"A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms\";s:8:\"\u0000*\u0000place\";s:10:\"Heidelberg\";s:6:\"\u0000*\u0000pub\";s:8:\"Springer\";s:10:\"\u0000*\u0000edition\";s:0:\"\";s:9:\"\u0000*\u0000tpages\";s:2:\"45\";s:9:\"\u0000*\u0000series\";s:0:\"\";s:8:\"\u0000*\u0000proxy\";s:30:\"http:\/\/proxyout.inist.fr:8080\/\";s:12:\"\u0000*\u0000integrite\";b:1;}"
Europe PubMed Central access
"O:11:\"BaseOpenUrl\":35:{s:10:\"\u0000*\u0000openUrl\";N;s:6:\"\u0000*\u0000fmt\";s:7:\"journal\";s:6:\"\u0000*\u0000doi\";s:25:\"10.1007\/s10107-007-0141-5\";s:6:\"\u0000*\u0000pii\";s:0:\"\";s:7:\"\u0000*\u0000pmid\";s:0:\"\";s:9:\"\u0000*\u0000atitle\";s:155:\"A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms\";s:9:\"\u0000*\u0000jtitle\";s:24:\"Mathematical programming\";s:9:\"\u0000*\u0000stitle\";s:13:\"Math. program\";s:7:\"\u0000*\u0000date\";s:4:\"2008\";s:9:\"\u0000*\u0000volume\";s:3:\"115\";s:8:\"\u0000*\u0000issue\";s:1:\"1\";s:8:\"\u0000*\u0000spage\";s:3:\"105\";s:8:\"\u0000*\u0000epage\";s:3:\"149\";s:8:\"\u0000*\u0000pages\";s:0:\"\";s:7:\"\u0000*\u0000issn\";s:9:\"0025-5610\";s:8:\"\u0000*\u0000eissn\";s:0:\"\";s:9:\"\u0000*\u0000aulast\";s:8:\"MONTEIRO\";s:10:\"\u0000*\u0000aufirst\";s:11:\"Renato D. C\";s:9:\"\u0000*\u0000auinit\";s:0:\"\";s:10:\"\u0000*\u0000auinitm\";s:0:\"\";s:5:\"\u0000*\u0000au\";a:1:{i:0;s:17:\"TSUCHIYA, Takashi\";}s:9:\"\u0000*\u0000aucorp\";s:0:\"\";s:7:\"\u0000*\u0000isbn\";s:0:\"\";s:8:\"\u0000*\u0000coden\";s:6:\"MHPGA4\";s:8:\"\u0000*\u0000genre\";s:7:\"article\";s:7:\"\u0000*\u0000part\";s:0:\"\";s:9:\"\u0000*\u0000btitle\";s:0:\"\";s:8:\"\u0000*\u0000title\";s:155:\"A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms\";s:8:\"\u0000*\u0000place\";s:10:\"Heidelberg\";s:6:\"\u0000*\u0000pub\";s:8:\"Springer\";s:10:\"\u0000*\u0000edition\";s:0:\"\";s:9:\"\u0000*\u0000tpages\";s:2:\"45\";s:9:\"\u0000*\u0000series\";s:0:\"\";s:8:\"\u0000*\u0000proxy\";s:30:\"http:\/\/proxyout.inist.fr:8080\/\";s:12:\"\u0000*\u0000integrite\";b:1;}"
Base Search access
"O:12:\"ArXivOpenUrl\":35:{s:10:\"\u0000*\u0000openUrl\";N;s:6:\"\u0000*\u0000fmt\";s:7:\"journal\";s:6:\"\u0000*\u0000doi\";s:25:\"10.1007\/s10107-007-0141-5\";s:6:\"\u0000*\u0000pii\";s:0:\"\";s:7:\"\u0000*\u0000pmid\";s:0:\"\";s:9:\"\u0000*\u0000atitle\";s:155:\"A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms\";s:9:\"\u0000*\u0000jtitle\";s:24:\"Mathematical programming\";s:9:\"\u0000*\u0000stitle\";s:13:\"Math. program\";s:7:\"\u0000*\u0000date\";s:4:\"2008\";s:9:\"\u0000*\u0000volume\";s:3:\"115\";s:8:\"\u0000*\u0000issue\";s:1:\"1\";s:8:\"\u0000*\u0000spage\";s:3:\"105\";s:8:\"\u0000*\u0000epage\";s:3:\"149\";s:8:\"\u0000*\u0000pages\";s:0:\"\";s:7:\"\u0000*\u0000issn\";s:9:\"0025-5610\";s:8:\"\u0000*\u0000eissn\";s:0:\"\";s:9:\"\u0000*\u0000aulast\";s:8:\"MONTEIRO\";s:10:\"\u0000*\u0000aufirst\";s:11:\"Renato D. C\";s:9:\"\u0000*\u0000auinit\";s:0:\"\";s:10:\"\u0000*\u0000auinitm\";s:0:\"\";s:5:\"\u0000*\u0000au\";a:1:{i:0;s:17:\"TSUCHIYA, Takashi\";}s:9:\"\u0000*\u0000aucorp\";s:0:\"\";s:7:\"\u0000*\u0000isbn\";s:0:\"\";s:8:\"\u0000*\u0000coden\";s:6:\"MHPGA4\";s:8:\"\u0000*\u0000genre\";s:7:\"article\";s:7:\"\u0000*\u0000part\";s:0:\"\";s:9:\"\u0000*\u0000btitle\";s:0:\"\";s:8:\"\u0000*\u0000title\";s:155:\"A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms\";s:8:\"\u0000*\u0000place\";s:10:\"Heidelberg\";s:6:\"\u0000*\u0000pub\";s:8:\"Springer\";s:10:\"\u0000*\u0000edition\";s:0:\"\";s:9:\"\u0000*\u0000tpages\";s:2:\"45\";s:9:\"\u0000*\u0000series\";s:0:\"\";s:8:\"\u0000*\u0000proxy\";s:30:\"http:\/\/proxyout.inist.fr:8080\/\";s:12:\"\u0000*\u0000integrite\";b:1;}"
arXiv access
