| 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 |
http://techreports.lib.berkeley.edu/accessPages/CSD-85-242.html |
| dbo:wikiPageID |
26754386 (xsd:integer) |
| dbo:wikiPageLength |
23865 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1122644512 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Probabilistic_method dbr:Method_of_conditional_probabilities dbr:Algorithm dbr:Approximation_algorithm dbc:Probabilistic_arguments dbr:Derandomization dbr:Independent_set_(graph_theory) dbr:Intractability_(complexity) dbr:Analysis_of_algorithms dbr:Graph_(discrete_mathematics) dbr:Approximation_algorithms dbr:Combinatorial_optimization dbr:Combinatorica dbr:Computer_science dbr:Linear_programming dbr:Linear_programming_relaxation dbr:Expected_value dbr:Journal_of_Computer_and_System_Sciences dbr:Association_for_Computing_Machinery dbc:Algorithms dbr:Boole's_inequality dbr:Polynomial_time dbr:Operations_research dbr:Markov's_inequality dbr:Turán's_theorem dbr:Semidefinite_programming dbr:Integer_linear_program dbr:Pessimistic_estimator dbr:Set_Cover dbr:Set_cover |
| dbp:wikiPageUsesTemplate |
dbt:Citation dbt:Confusing dbt:Harv dbt:Reflist |
| dct:subject |
dbc:Probabilistic_arguments dbc:Algorithms |
| rdf:type |
yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Argument106648724 yago:Communication100033020 yago:Event100029378 yago:Evidence106643408 yago:Indication106797169 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms yago:WikicatProbabilisticArguments |
| 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 |
freebase:Randomized rounding yago-res:Randomized rounding wikidata:Randomized rounding dbpedia-ru:Randomized rounding https://global.dbpedia.org/id/4tfFQ |
| prov:wasDerivedFrom |
wikipedia-en:Randomized_rounding?oldid=1122644512&ns=0 |
| foaf:isPrimaryTopicOf |
wikipedia-en:Randomized_rounding |
| is dbo:wikiPageWikiLink of |
dbr:Probabilistic_method dbr:Method_of_conditional_probabilities dbr:David_Shmoys dbr:Maximum_cut dbr:Feedback_arc_set dbr:Proportional_approval_voting dbr:Linear_programming_relaxation dbr:Set_cover_problem dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Unrelated-machines_scheduling |
| is foaf:primaryTopic of |
wikipedia-en:Randomized_rounding |