Karmarkar's algorithm
http://dbpedia.org/resource/Karmarkar's_algorithm an entity of type: WikicatOptimizationAlgorithmsAndMethods
L'algoritmo di Karmarkar (1984) è un per risolvere un problema di programmazione lineare.L'algoritmo di Karmakar utilizza un metodo a punto interno evitando accuratamente i vertici e ogni punto della frontiera della regione ammissibile nella ricerca del valore ottimo.L'algoritmo genera una successione di punti strettamente ammissibili che convergono verso il punto ottimale, il quale invece può essere un vertice. L'algoritmo ha un tempo polinomiale nella grandezza del problema anche nel caso che il problema sia illimitato: in questo caso si accorge della non esistenza di un punto ottimale e termina, restituendo una garanzia della non limitazione del problema.
rdf:langString
カーマーカーのアルゴリズム（英: Karmarkar's algorithm）とは1984年、ナレンドラ・カーマーカーにより発見された線形計画問題の解法である。このアルゴリズムは、しばしば、カーマーカー法（英: Karmarkar's method）とも呼ばれる。また、このアルゴリズムを発明とする特許が米国や日本で出願され、請求特許は時折カーマーカー特許 (Karmarkar's patent) とも呼称される。 カーマーカーのアルゴリズムは、線形計画問題に対する多項式時間アルゴリズムで初めての実用的なものである。も多項式時間アルゴリズムであるが、実用上の効率は良くない。 カーマーカーのアルゴリズムは内点法の一種である。内点法は、候補解をの境界に沿って更新する単体法とは異なり、実行可能領域の内部を通るよう更新する。この更新は解の精度を定数倍改善し、これを繰り返すことで最適解（optimal solution）に収束する。
rdf:langString
خوارزمية كارماركر هي خوارزمية قدمها ناريندرا كارماركر في عام 1984 لحل مسائل البرمجة الخطية . كانت أول خوارزمية ذات كفاءة معقولة لحل هذه المسائل في زمن متعدد الحدود . طريقة الإهليلجي هي أيضا متعددة الحدود لكنها أثبتت أنها غير فعالة عمليا. بجعل تدل على عدد المتغيرات و على عدد وحدات بت في مدخلات الخوارزمية، خوارزمية كارماركر تحتاج إلى عملية على خانات , في المقابل تحتاج إلى عمليات بخوارزمية الاهليجي. بالتالي زمن تشغيل خوارزمية كارماركر هو: باستخدام الضرب القائم على FFT (انظر رمز O الكبير ).
rdf:langString
Karmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984 for solving linear programming problems. It was the first reasonably efficient algorithm that solves these problems in polynomial time. The ellipsoid method is also polynomial time but proved to be inefficient in practice. Denoting as the number of variables and as the number of bits of input to the algorithm, Karmarkar's algorithm requires operations on digit numbers, as compared to such operations for the ellipsoid algorithm. The runtime of Karmarkar's algorithm is thus
rdf:langString
L’algorithme de Karmarkar est un algorithme introduit par Narendra Karmarkar en 1984 pour résoudre les problèmes d'optimisation linéaire. C'est le premier algorithme réellement efficace qui résout ces problèmes en un temps polynomial. La méthode de l'ellipsoïde fonctionne aussi en temps polynomial mais est inefficace en pratique.
rdf:langString
O algoritmo de Karmarkar é um algoritmo introduzido por Narendra Karmarkar, em 1984, para resolver problemas de programação linear. Foi o primeiro algoritmo razoavelmente eficiente que resolve esses problemas em tempo polinomial. O é também de tempo polinomial, mas provou ser ineficaz na prática. Onde é o número de variáveis e é o número de bits de entrada, o algoritmo de Karmarkar requer operações, números de dígitos, enquanto que no algoritmo elipsóide são necessárias operações. O tempo de execução do algoritmo de Karmarkar é: usando FFT (Fast Fourier Transform).
rdf:langString
Алгоритм Кармаркара — это алгоритм, представленный Нарендра Кармаркаром в 1984 для решения задач линейного программирования. Это был первый достаточно эффективный алгоритм, который решал задачи за полиномиальное время. Метод эллипсоидов является также алгоритмом полиномиального времени, но он оказался неэффективным в практических приложениях. Если — число переменных и — число бит входных данных, алгоритм Кармаркара требует операций над числами с знаками, в то время как метод эллипсоидов требует таких операций. Время работы алгоритма Кармаркара равно
rdf:langString
rdf:langString
خوارزمية كارماركر
rdf:langString
Algorithme de Karmarkar
rdf:langString
Algoritmo di Karmarkar
rdf:langString
Karmarkar's algorithm
rdf:langString
カーマーカーのアルゴリズム
rdf:langString
Algoritmo de Karmarkar
rdf:langString
Алгоритм Кармаркара
xsd:integer
3736667
xsd:integer
1102127923
rdf:langString
خوارزمية كارماركر هي خوارزمية قدمها ناريندرا كارماركر في عام 1984 لحل مسائل البرمجة الخطية . كانت أول خوارزمية ذات كفاءة معقولة لحل هذه المسائل في زمن متعدد الحدود . طريقة الإهليلجي هي أيضا متعددة الحدود لكنها أثبتت أنها غير فعالة عمليا. بجعل تدل على عدد المتغيرات و على عدد وحدات بت في مدخلات الخوارزمية، خوارزمية كارماركر تحتاج إلى عملية على خانات , في المقابل تحتاج إلى عمليات بخوارزمية الاهليجي. بالتالي زمن تشغيل خوارزمية كارماركر هو: باستخدام الضرب القائم على FFT (انظر رمز O الكبير ). تندرج خوارزمية كارماركر ضمن فئة أساليب النقاط الداخلية : لا يتبع التخمين الحالي للحل حدود المجموعة الممكنة كما هو الحال في طريقة simplex ، لكنه يتحرك بداخل المنطقة الممكنة، مما يحسن تقريب الحل الأمثل بكسر واضح مع كل التكرار، والوصول إلى الحل الأمثل مع البيانات المنطقية.
rdf:langString
Karmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984 for solving linear programming problems. It was the first reasonably efficient algorithm that solves these problems in polynomial time. The ellipsoid method is also polynomial time but proved to be inefficient in practice. Denoting as the number of variables and as the number of bits of input to the algorithm, Karmarkar's algorithm requires operations on digit numbers, as compared to such operations for the ellipsoid algorithm. The runtime of Karmarkar's algorithm is thus using FFT-based multiplication (see Big O notation). Karmarkar's algorithm falls within the class of interior point methods: the current guess for the solution does not follow the boundary of the feasible set as in the simplex method, but it moves through the interior of the feasible region, improving the approximation of the optimal solution by a definite fraction with every iteration, and converging to an optimal solution with rational data.
rdf:langString
L’algorithme de Karmarkar est un algorithme introduit par Narendra Karmarkar en 1984 pour résoudre les problèmes d'optimisation linéaire. C'est le premier algorithme réellement efficace qui résout ces problèmes en un temps polynomial. La méthode de l'ellipsoïde fonctionne aussi en temps polynomial mais est inefficace en pratique. En posant le nombre de variables et le nombre de bits d'entrée de l'algorithme, l'algorithme de Karmarkar réalise opérations sur bits à comparer aux opérations pour la méthode des ellipsoïdes. Le temps d'exécution de l'algorithme de Karmarkar est ainsi en utilisant l'algorithme de Schönhage-Strassen (voir Comparaison asymptotique). L'algorithme de Karmarkar est une méthode du point intérieur : la solution candidate courante ne suit pas les bornes de l'espace faisable comme dans l'algorithme du simplexe, mais approche par l'intérieur de l'espace faisable et atteint la solution optimale de manière asymptotique.
rdf:langString
L'algoritmo di Karmarkar (1984) è un per risolvere un problema di programmazione lineare.L'algoritmo di Karmakar utilizza un metodo a punto interno evitando accuratamente i vertici e ogni punto della frontiera della regione ammissibile nella ricerca del valore ottimo.L'algoritmo genera una successione di punti strettamente ammissibili che convergono verso il punto ottimale, il quale invece può essere un vertice. L'algoritmo ha un tempo polinomiale nella grandezza del problema anche nel caso che il problema sia illimitato: in questo caso si accorge della non esistenza di un punto ottimale e termina, restituendo una garanzia della non limitazione del problema.
rdf:langString
カーマーカーのアルゴリズム（英: Karmarkar's algorithm）とは1984年、ナレンドラ・カーマーカーにより発見された線形計画問題の解法である。このアルゴリズムは、しばしば、カーマーカー法（英: Karmarkar's method）とも呼ばれる。また、このアルゴリズムを発明とする特許が米国や日本で出願され、請求特許は時折カーマーカー特許 (Karmarkar's patent) とも呼称される。 カーマーカーのアルゴリズムは、線形計画問題に対する多項式時間アルゴリズムで初めての実用的なものである。も多項式時間アルゴリズムであるが、実用上の効率は良くない。 カーマーカーのアルゴリズムは内点法の一種である。内点法は、候補解をの境界に沿って更新する単体法とは異なり、実行可能領域の内部を通るよう更新する。この更新は解の精度を定数倍改善し、これを繰り返すことで最適解（optimal solution）に収束する。
rdf:langString
O algoritmo de Karmarkar é um algoritmo introduzido por Narendra Karmarkar, em 1984, para resolver problemas de programação linear. Foi o primeiro algoritmo razoavelmente eficiente que resolve esses problemas em tempo polinomial. O é também de tempo polinomial, mas provou ser ineficaz na prática. Onde é o número de variáveis e é o número de bits de entrada, o algoritmo de Karmarkar requer operações, números de dígitos, enquanto que no algoritmo elipsóide são necessárias operações. O tempo de execução do algoritmo de Karmarkar é: usando FFT (Fast Fourier Transform). O algoritmo de Karmarkar está na classe de método de pontos interiores: a atual estimativa para a solução não segue o limite da região viável como no método simplex, mas ele se move através do interior da região viável, melhorando a aproximação da ótima solução, por uma fração definitiva com cada iteração, e converge para uma ótima solução de dado racional.
rdf:langString
Алгоритм Кармаркара — это алгоритм, представленный Нарендра Кармаркаром в 1984 для решения задач линейного программирования. Это был первый достаточно эффективный алгоритм, который решал задачи за полиномиальное время. Метод эллипсоидов является также алгоритмом полиномиального времени, но он оказался неэффективным в практических приложениях. Если — число переменных и — число бит входных данных, алгоритм Кармаркара требует операций над числами с знаками, в то время как метод эллипсоидов требует таких операций. Время работы алгоритма Кармаркара равно при использовании метода умножения Шёнхаге — Штрассена (см. «O» большое). Алгоритм Кармаркара принадлежит классу методов внутренней точки — текущее допустимое решение не передвигается по границе области допустимых решений как в симплекс-методе, а движется по внутренним точкам области допустимых значений, улучшая с каждой итерацией аппроксимацию оптимального решения определённой дробью и приводя к оптимальному решению с рациональными данными.
xsd:nonNegativeInteger
17189
