Παρακαλώ χρησιμοποιήστε αυτό το αναγνωριστικό για να παραπέμψετε ή να δημιουργήσετε σύνδεσμο προς αυτό το τεκμήριο:
https://ruomo.lib.uom.gr/handle/7000/215
Τίτλος: | Computational complexity of the exterior point simplex algorithm |
Συγγραφείς: | Voulgaropoulou, Sophia Samaras, Nikolaos Sifaleras, Angelo |
Τύπος: | Article |
Θέματα: | FRASCATI::Natural sciences::Mathematics::Applied Mathematics FRASCATI::Natural sciences::Computer and information sciences |
Λέξεις-Κλειδιά: | Exterior point simplex algorithm Regression analysis Computational complexity Linear relation |
Ημερομηνία Έκδοσης: | 2019 |
Εκδότης: | Springer |
Πηγή: | Operational Research |
Τόμος: | 19 |
Τεύχος: | 2 |
Πρώτη Σελίδα: | 297 |
Τελευταία Σελίδα: | 316 |
Επιτομή: | In this paper, we investigate the computational behavior of the exterior point simplex algorithm. Up until now, there has been a major difference observed between the theoretical worst case complexity and practical performance of simplex-type algorithms. Computational tests have been carried out on randomly generated sparse linear problems and on a small set of benchmark problems. Specifically, 6780 linear problems were randomly generated, in order to formulate a respectable amount of experiments. Our study consists of the measurement of the number of iterations that the exterior point simplex algorithm needs for the solution of the above mentioned problems and benchmark dataset. Our purpose is to formulate representative regression models for these measurements, which would play a significant role for the evaluation of an algorithm’s efficiency. For this examination, specific characteristics, such as the number of constraints and variables, the sparsity and bit length, and the condition of matrix A, of each linear problem, were taken into account. What drew our attention was that the formulated model for the randomly generated problems reveal a linear relation among these characteristics. |
URI: | https://doi.org/10.1007/s12351-017-0291-z https://ruomo.lib.uom.gr/handle/7000/215 |
ISSN: | 1109-2858 1866-1505 |
Αλλοι Προσδιοριστές: | 10.1007/s12351-017-0291-z |
Εμφανίζεται στις Συλλογές: | Τμήμα Εφαρμοσμένης Πληροφορικής |
Αρχεία σε αυτό το Τεκμήριο:
Αρχείο | Περιγραφή | Μέγεθος | Μορφότυπος | |
---|---|---|---|---|
Computational_complexity_of_the_Exterior_Point_Simplex_Algorithm.pdf | 309,56 kB | Adobe PDF | Προβολή/Ανοιγμα |
Τα τεκμήρια στο Αποθετήριο προστατεύονται από πνευματικά δικαιώματα, εκτός αν αναφέρεται κάτι διαφορετικό.