| dbo:abstract
|
- Das Mengenpackungsproblem (oft mit set-packing-Problem notiert) ist ein Entscheidungsproblem der Kombinatorik. Es fragt, ob zu einer endlichen Menge und Teilmengen von eine Anzahl von mindestens paarweise disjunkter Teilmengen existieren. Als Optimierungsproblem formuliert, wird eine Packung mit möglichst vielen Teilmengen gesucht oder, falls den Teilmengen Bewertungen zugeordnet sind, eine Packung mit maximaler Bewertung. Das Mengenpackungsproblem gehört zur Liste der 21 klassischen NP-vollständigen Probleme, von denen Richard M. Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte. (de)
- Empaquetamiento de conjuntos es un problema clásico NP-completo en Teoría de la complejidad computacional y combinatoria, y fue uno de los . Supongamos que tenemos un conjunto finito S y una lista de subconjuntos de S. Entonces, el problema de empaquetamiento de conjuntos pregunta si algunos de los k subconjuntos en la lista son conjuntos (en otras palabras, ninguno de ellos tiene un elemento en común). Más formalmente, dado un universo y una familia de subconjuntos de , un empaquetamiento es una subfamilia de conjuntos tal que todos los conjuntos en son disjuntos 2 a 2, y el tamaño del empaquetamiento es . En el de empaquetemiento de conjuntos, la entrada es un par y un entero ; la pregunta es si existe un empaquetamiento de conjuntos de tamaño mayor o igual que . En el empaquetamiento de conjuntos , la entrada es un par , y la tarea es encontrar un empaquetamiento de conjuntos que use la mayor cantidad de conjuntos. El problema es claramente un problema debido a que, dadok subconjuntos, podemos fácilmente verificar que ellos son disjuntos 2 a 2 en . La versión del problema como problema de optimización, máximo empaquetamiento de conjuntos, pregunta por el máximo número de conjuntos disjuntos 2 a 2 en la lista. Es un problema de maximización que puede ser formulado naturalmente como un ,perteneciendo a la clase de los , y su es el problema de cubrimiento de conjuntos. (es)
- Le problème de set packing est un problème d'optimisation combinatoire NP-complet. Il peut être considéré comme une version particulière du problème du sac à dos multidimensionnel où les poids des objets sont égaux à 0 ou 1 et où les capacités du sac sont toutes égales à 1.
* Portail de l'informatique théorique (fr)
- Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems.Suppose one has a finite set S and a list of subsets of S. Then, the set packing problem asks if some k subsets in the list are pairwise disjoint (in other words, no two of them share an element). More formally, given a universe and a family of subsets of ,a packing is a subfamily of sets such that all sets in are pairwise disjoint. The size of the packing is . In the set packing decision problem, the input is a pair and an integer ; the question is whetherthere is a set packing of size or more. In the set packing optimization problem, the input is a pair , and the task is to find a set packing that uses the most sets. The problem is clearly in NP since, given k subsets, we can easily verify that they are pairwise disjoint in polynomial time. The optimization version of the problem, maximum set packing, asks for the maximum number of pairwise disjoint sets in the list. It is a maximization problem that can be formulated naturally as an integer linear program, belonging to the class of packing problems. (en)
- Empacotamento de conjuntos é um clássico NP-completo problema em complexidade computacional teoria e análise combinatória, e foi um dos Karp 21 problemas NP-completos. Suponha que temos um conjunto finito S e uma lista de subconjuntos de S. Então, problema de empacotamento de conjuntos pergunta se algum conjunto com k subconjuntos da lista são dois a dois disjuntos (em outras palavras, não há dois compartilham um elemento). Mais formalmente, dado um universo e uma família de subconjuntos de , um empacotamento é uma subfamília de conjuntos de tal forma que todos os conjuntos em são disjuntos dois a dois, e o tamanho do pacote é . No problema de decisão de empacotamento de conjuntos, a entrada é um par e um inteiro ; a questão é se há um pacote de conjuntos de tamanho ou mais. No problema de otimização de empacotamento de conjuntos, a entrada é o par , e a tarefa é encontrar um pacote de conjuntos que utilize a maioria dos conjuntos. O problema está, claramente, em NP, uma vez que, dado k subconjuntos, podemos facilmente verificar que eles são pares disjuntos em tempo polinomial. A versão otimizada do problema, o máximo empacotamento de conjuntos, pede-lhe o número máximo de pares disjuntos conjuntos na lista. É um problema de maximização, que pode ser formulado, naturalmente, como um programa linear inteiro, pertence à classe de problemas de empacotamento, e o seu dual programa linear é o problema da cobertura de conjuntos. (pt)
- Упаковка множеств — это классическая NP-полная задача в теории вычислительной сложности и комбинаторике и является одной из 21 NP-полных задач Карпа. Представим, что мы имеем конечное множество S и список подмножеств множества S. Задача упаковки задаётся вопросом, есть ли k подмножеств в списке, которые попарно не пересекаются. Более формально, если задано множество и семейство подмножеств множества ,упаковка — это подсемейство множеств, такое, что все множества из попарно не пересекаются, а называется размером упаковки. В задаче разрешимости упаковки, входом является пара и число . Вопрос заключается в определении, существует ли упаковка размера или более. В задаче оптимизации упаковки входом является пара , а задача заключается в поиске упаковки, использующей как можно больше множеств. Ясно, что задача принадлежит NP, поскольку, если задано k подмножеств, мы можем просто проверить, что они попарно не пересекаются, за полиномиальное время. Оптимизационная версия задачи, максимальная упаковка множеств, задаёт вопрос о максимальном числе попарно непересекающихся множеств из списка. Эта задача может естественным образом быть сформулирована как задача целочисленного линейного программирования, она принадлежит классу задач упаковки, а её является задачей о покрытии множества. (ru)
- Set packing 问题是复杂性理论和组合数学中一个经典的NP完全问题，是卡普的二十一個NP-完全問題之一。 (zh)
|
| rdfs:comment
|
- Le problème de set packing est un problème d'optimisation combinatoire NP-complet. Il peut être considéré comme une version particulière du problème du sac à dos multidimensionnel où les poids des objets sont égaux à 0 ou 1 et où les capacités du sac sont toutes égales à 1.
* Portail de l'informatique théorique (fr)
- Set packing 问题是复杂性理论和组合数学中一个经典的NP完全问题，是卡普的二十一個NP-完全問題之一。 (zh)
- Das Mengenpackungsproblem (oft mit set-packing-Problem notiert) ist ein Entscheidungsproblem der Kombinatorik. Es fragt, ob zu einer endlichen Menge und Teilmengen von eine Anzahl von mindestens paarweise disjunkter Teilmengen existieren. Als Optimierungsproblem formuliert, wird eine Packung mit möglichst vielen Teilmengen gesucht oder, falls den Teilmengen Bewertungen zugeordnet sind, eine Packung mit maximaler Bewertung. (de)
- Empaquetamiento de conjuntos es un problema clásico NP-completo en Teoría de la complejidad computacional y combinatoria, y fue uno de los . Supongamos que tenemos un conjunto finito S y una lista de subconjuntos de S. Entonces, el problema de empaquetamiento de conjuntos pregunta si algunos de los k subconjuntos en la lista son conjuntos (en otras palabras, ninguno de ellos tiene un elemento en común). El problema es claramente un problema debido a que, dadok subconjuntos, podemos fácilmente verificar que ellos son disjuntos 2 a 2 en . (es)
- Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems.Suppose one has a finite set S and a list of subsets of S. Then, the set packing problem asks if some k subsets in the list are pairwise disjoint (in other words, no two of them share an element). The problem is clearly in NP since, given k subsets, we can easily verify that they are pairwise disjoint in polynomial time. (en)
- Empacotamento de conjuntos é um clássico NP-completo problema em complexidade computacional teoria e análise combinatória, e foi um dos Karp 21 problemas NP-completos. Suponha que temos um conjunto finito S e uma lista de subconjuntos de S. Então, problema de empacotamento de conjuntos pergunta se algum conjunto com k subconjuntos da lista são dois a dois disjuntos (em outras palavras, não há dois compartilham um elemento). O problema está, claramente, em NP, uma vez que, dado k subconjuntos, podemos facilmente verificar que eles são pares disjuntos em tempo polinomial. (pt)
- Упаковка множеств — это классическая NP-полная задача в теории вычислительной сложности и комбинаторике и является одной из 21 NP-полных задач Карпа. Представим, что мы имеем конечное множество S и список подмножеств множества S. Задача упаковки задаётся вопросом, есть ли k подмножеств в списке, которые попарно не пересекаются. Ясно, что задача принадлежит NP, поскольку, если задано k подмножеств, мы можем просто проверить, что они попарно не пересекаются, за полиномиальное время. (ru)
|
