What are matroids in mathematical optimization? In mathematical optimization, greedy algorithms optimally solve combinatorial problems that have t...
In mathematical optimization, greedy algorithms optimally solve combinatorial problems that have the properties of matroids and give constant factor approximations to optimization problems with submodular structure.
A matroid is a structure that takes and generalizes the concept of linear independence in vector spaces.
Matroids are used to model problems in which a set of objects must be selected subject to certain constraints.
Matroids have a set function called the rank function that assigns a non-negative integer to each subset of the ground set.
The rank function satisfies the properties of monotonicity, submodularity, and the augmentation property.
💡 1 Resposta
Ed 
Matroids são estruturas matemáticas que generalizam o conceito de independência linear em espaços vetoriais. Em otimização matemática, os matroids são usados para modelar problemas nos quais um conjunto de objetos deve ser selecionado sujeito a certas restrições. Eles possuem uma função chamada função de classificação (rank function) que atribui um número inteiro não negativo a cada subconjunto do conjunto base. A função de classificação satisfaz propriedades como monotonicidade, submodularidade e propriedade de aumento. Os matroids são importantes na otimização combinatória, pois permitem o uso de algoritmos gananciosos que resolvem problemas combinatórios de forma ótima e fornecem aproximações com fator constante para problemas de otimização com estrutura submodular.
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Outros materiais
Perguntas relacionadas
Materiais relacionados
15 pág.
10 pág.
Compartilhar