| dbo:abstract
|
- Within computer science and operations research,many combinatorial optimization problems are computationally intractable to solve exactly (to optimality).Many such problems do admit fast (polynomial time) approximation algorithms—that is, algorithms that are guaranteed to return an approximately optimal solution given any input. Randomized roundingis a widely used approach for designing and analyzing such approximation algorithms. The basic idea is to use the probabilistic methodto convert an optimal solution of a relaxationof the problem into an approximately optimal solution to the original problem. (en)
- В информатике и исследовании операций многие задачи комбинаторной оптимизации вычислительно для решения задачи точно (т.е. для получения оптимального решения).Многие такие задачи допускают быстрые (полиномиального времени) аппроксимационные алгоритмы — то есть алгоритмы, гарантированное возвращающие приближённое к оптимальному решение для любого входа. Вероятностное округление — это широко используемый подход для разработки и анализа таких аппроксимационных алгоритмов. Базовая идея — использование вероятностного метода для преобразования соответствующей оптимального решения задачи линейного программирования (ЛП) в приближённое к оптимальному решению исходной задачи. (ru)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 23865 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Within computer science and operations research,many combinatorial optimization problems are computationally intractable to solve exactly (to optimality).Many such problems do admit fast (polynomial time) approximation algorithms—that is, algorithms that are guaranteed to return an approximately optimal solution given any input. (en)
- В информатике и исследовании операций многие задачи комбинаторной оптимизации вычислительно для решения задачи точно (т.е. для получения оптимального решения).Многие такие задачи допускают быстрые (полиномиального времени) аппроксимационные алгоритмы — то есть алгоритмы, гарантированное возвращающие приближённое к оптимальному решение для любого входа. (ru)
|
| rdfs:label
|
- Randomized rounding (en)
- Вероятностное округление (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
