| dbo:abstract
|
- Das Mengenüberdeckungsproblem (oft mit set-covering-Problem notiert) ist ein Entscheidungsproblem der Kombinatorik. Es fragt, ob zu einer Menge und Teilmengen von und einer natürlichen Zahl eine Vereinigung von oder weniger Teilmengen existiert, die der Menge entspricht (Überdeckung). Als Optimierungsproblem formuliert, wird eine Überdeckung mit möglichst kleiner Anzahl der Teilmengen gesucht oder, falls den Teilmengen Kosten zugeordnet sind, eine Überdeckung mit geringsten Kosten. Das Mengenüberdeckungsproblem gehört zur Liste der 21 klassischen NP-vollständigen Probleme, von denen Richard Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte. (de)
- El problema del Set Covering, también conocido por sus siglas SCP es un problema clásico en combinatoria, ciencias de la computación y teoría de la complejidad computacional. Es un problema que ha llevado al desarrollo de técnicas fundamentales para el campo de los algoritmos de aproximación. También es uno de los problemas de la Lista de 21 problemas NP-completos de Karp cuya NP-completitud fue demostrada en 1972. Dado un conjunto de elementos (llamado universo) y conjuntos cuya unión comprende el universo, el problema del conjunto de cobertura consiste en identificar el menor número de conjuntos cuya unión aun contiene todos los elementos del universo. Por ejemplo, sea y los conjuntos . Claramente, la unión de todos los conjuntos de contiene todos los elementos de . Sin embargo, podemos cubrir todos los elementos con el siguiente conjunto de elementos, con menor número de elementos: . (es)
- The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972. Given a set of elements {1, 2, …, n} (called the universe) and a collection S of m sets whose union equals the universe, the set cover problem is to identify the smallest sub-collection of S whose union equals the universe. For example, consider the universe U = {1, 2, 3, 4, 5} and the collection of sets S = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} }. Clearly the union of S is U. However, we can cover all of the elements with the following, smaller number of sets: { {1, 2, 3}, {4, 5} }. More formally, given a universe and a family of subsets of , a cover is a subfamily of sets whose union is . In the set covering decision problem, the input is a pair and an integer ; the question is whether there is a set covering of size or less. In the set covering optimization problem, the input is a pair , and the task is to find a set covering that uses the fewest sets. The decision version of set covering is NP-complete, and the optimization/search version of set cover is NP-hard. It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms. If each set is assigned a cost, it becomes a weighted set cover problem. (en)
- En informatique théorique, le problème de couverture par ensembles (Set Cover problem en anglais) est un problème d'algorithmique particulièrement important car c'est l'un des 21 problèmes NP-complets de Karp. Étant donné un ensemble A, on dit qu'un élément e est couvert par A si e appartient à A. Étant donné un ensemble U et une famille S de sous-ensembles de U, le problème consiste à couvrir tous les éléments U avec une sous-famille de S la plus petite possible. Une version plus générale consiste à assigner des poids aux éléments de S, et à chercher la sous-famille de poids minimal. (fr)
- 집합 덮개 문제(set cover)는 전산학과 복잡도 이론에서 다루는 오랜 문제로, 어떠한 전체집합과 그 집합의 부분집합들이 주어졌을 때, 부분집합들 중에서 가능한 한 적은 집합을 골라서 그 집합들의 합집합이 원래 전체집합이 되도록, 즉 그 집합들이 원래 전제집합을 '덮도록' 집합을 선택하는 문제이다. 이때 집합을 가능한 한 적게 골라내는 것이 목표이다. 이 문제의 결정 문제판은 리처드 카프가 NP-완전임을 증명했던 최초의 21문제 중 하나이다. 엄밀히 정의하면, 전체집합 와 의 부분집합으로 이루어진 집합족 가 있을 때, 어떠한 부분집합족 에 대해 에 속하는 집합들의 합집합이 가 된다면, 를 덮개라고 정의한다. 이때 집합 덮개 문제의 결정 문제판은 쌍과 정수 가 입력될 때, 이하인 집합 덮개가 있는지 묻는 문제이다. 최적화 문제판의 경우 입력이 쌍뿐이고, 집합 수가 가장 적은 덮개를 찾는 문제가 된다. 이 문제는 결정 문제의 경우 NP-완전, 최적화 문제의 경우 NP-난해에 속한다. (ko)
- 集合被覆問題（しゅうごうひふくもんだい）は、集合 U とその部分集合の族 S1,...,Sm が与えられたとき、U の要素を全てカバーするように部分集合の族から最小個数の部分集合を選ぶ問題。ここで、S1,...,Sm の和集合は、U に等しくなるものとする。 各部分集合 Si に対し重み wi が与えられ、選択した部分集合の重みの和を最小化する問題のことを指す場合もある。このような場合、重み付き集合被覆問題 と区別して呼ぶことも多い。全ての i について wi が等しいとき、重み無し集合被覆問題と等価なので、重み無し集合被覆問題は、重み付き集合被覆問題の特殊な場合とも言える。 重み無し・重み付きを問わず、この問題はNP困難であることが知られている。そのため、集合に制約を加えた問題や近似アルゴリズムの研究がさかんである。 (ja)
- Gegeven een verzameling U (de universele verzameling), en anderzijds een verzameling S van deelverzamelingen van U, waarvan de vereniging gelijk is aan U. Een verzamelingenoverdekking (set cover) van U bestaat uit een of meer verzamelingen uit S zodanig dat hun vereniging ook gelijk is aan U. In het vervolg van dit artikel wordt overal overdekking gebruikt in plaats van verzamelingenoverdekking. (nl)
- O problema de cobertura de conjuntos é uma questão clássica em combinatória, ciência da computação, pesquisa operacional e teoria da complexidade computacional . É um dos 21 problemas NP-completos de Karp mostrado ser NP-completo em 1972. É um problema "cujo estudo levou ao desenvolvimento de técnicas fundamentais para todo o campo" dos algoritmos de aproximação . Dado um conjunto universo e uma coleção de conjuntos cuja união é igual ao conjunto universo, o problema de cobertura de conjunto é identificar a menor sub-coleção de cuja união é igual ao conjunto universo. Por exemplo, considere o conjunto universo e a coleção de conjuntos . Claramente a união de é . No entanto, podemos cobrir todos os elementos com o mínimo número de conjuntos a seguir : . Mais formalmente, dado um conjunto universo e uma família de subconjuntos de , uma capa é uma subfamília de conjuntos cuja união é . No conjunto que cumpre o problema de decisão, a entrada é um par e um inteiro ; a questão é se há uma cobertura de conjuntos de tamanho ou menos. No conjunto que cumpre o problema de otimização, a entrada é um par , e a tarefa é encontrar uma cobertura de conjuntos que use o menor número de conjuntos. A versão de decisão da cobertura do conjunto é NP-completa, e a versão de otimização / busca da cobertura do conjunto é NP-difícil . Se cada conjunto tiver um custo atribuído, ele se tornará um problema de cobertura de conjuntos ponderado . (pt)
- Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает NP-полную задачу о вершинном покрытии (и потому является NP-сложной). Несмотря на то, что задача о вершинном покрытии сходна с данной, подход, использованный в приближённом алгоритме, здесь не работает. Вместо этого мы рассмотрим жадный алгоритм. Даваемое им решение будет хуже оптимального в логарифмическое число раз. С ростом размера задачи качество решения ухудшается, но всё же довольно медленно, поэтому такой подход можно считать полезным. (ru)
- Задача про покриття множини є класичним питанням інформатики і теорії складності. Ця задача узагальнює NP-повну задачу про вершинне покриття (і тому є NP-складною). Попри те, що задача про вершинне покриття подібна до цієї, підхід, використаний у наближеному алгоритмі, тут не працює. Замість цього ми розглянемо жадібний алгоритм. Отриманий за ним розв'язок буде гіршим від оптимального в логарифмічне число разів. Із зростанням розміру задачі якість розв'язку погіршується, але все ж досить повільно, тому такий підхід можна вважати корисним. (uk)
- 集合覆盖问题（ Set covering problem，SCP）是组合数学、计算机科学和计算复杂性理论中的一个经典问题。 集合覆盖的决定性问题是卡普的二十一个NP-完全问题之一。 (zh)
|
| rdfs:comment
|
- En informatique théorique, le problème de couverture par ensembles (Set Cover problem en anglais) est un problème d'algorithmique particulièrement important car c'est l'un des 21 problèmes NP-complets de Karp. Étant donné un ensemble A, on dit qu'un élément e est couvert par A si e appartient à A. Étant donné un ensemble U et une famille S de sous-ensembles de U, le problème consiste à couvrir tous les éléments U avec une sous-famille de S la plus petite possible. Une version plus générale consiste à assigner des poids aux éléments de S, et à chercher la sous-famille de poids minimal. (fr)
- 집합 덮개 문제(set cover)는 전산학과 복잡도 이론에서 다루는 오랜 문제로, 어떠한 전체집합과 그 집합의 부분집합들이 주어졌을 때, 부분집합들 중에서 가능한 한 적은 집합을 골라서 그 집합들의 합집합이 원래 전체집합이 되도록, 즉 그 집합들이 원래 전제집합을 '덮도록' 집합을 선택하는 문제이다. 이때 집합을 가능한 한 적게 골라내는 것이 목표이다. 이 문제의 결정 문제판은 리처드 카프가 NP-완전임을 증명했던 최초의 21문제 중 하나이다. 엄밀히 정의하면, 전체집합 와 의 부분집합으로 이루어진 집합족 가 있을 때, 어떠한 부분집합족 에 대해 에 속하는 집합들의 합집합이 가 된다면, 를 덮개라고 정의한다. 이때 집합 덮개 문제의 결정 문제판은 쌍과 정수 가 입력될 때, 이하인 집합 덮개가 있는지 묻는 문제이다. 최적화 문제판의 경우 입력이 쌍뿐이고, 집합 수가 가장 적은 덮개를 찾는 문제가 된다. 이 문제는 결정 문제의 경우 NP-완전, 최적화 문제의 경우 NP-난해에 속한다. (ko)
- 集合被覆問題（しゅうごうひふくもんだい）は、集合 U とその部分集合の族 S1,...,Sm が与えられたとき、U の要素を全てカバーするように部分集合の族から最小個数の部分集合を選ぶ問題。ここで、S1,...,Sm の和集合は、U に等しくなるものとする。 各部分集合 Si に対し重み wi が与えられ、選択した部分集合の重みの和を最小化する問題のことを指す場合もある。このような場合、重み付き集合被覆問題 と区別して呼ぶことも多い。全ての i について wi が等しいとき、重み無し集合被覆問題と等価なので、重み無し集合被覆問題は、重み付き集合被覆問題の特殊な場合とも言える。 重み無し・重み付きを問わず、この問題はNP困難であることが知られている。そのため、集合に制約を加えた問題や近似アルゴリズムの研究がさかんである。 (ja)
- Gegeven een verzameling U (de universele verzameling), en anderzijds een verzameling S van deelverzamelingen van U, waarvan de vereniging gelijk is aan U. Een verzamelingenoverdekking (set cover) van U bestaat uit een of meer verzamelingen uit S zodanig dat hun vereniging ook gelijk is aan U. In het vervolg van dit artikel wordt overal overdekking gebruikt in plaats van verzamelingenoverdekking. (nl)
- Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает NP-полную задачу о вершинном покрытии (и потому является NP-сложной). Несмотря на то, что задача о вершинном покрытии сходна с данной, подход, использованный в приближённом алгоритме, здесь не работает. Вместо этого мы рассмотрим жадный алгоритм. Даваемое им решение будет хуже оптимального в логарифмическое число раз. С ростом размера задачи качество решения ухудшается, но всё же довольно медленно, поэтому такой подход можно считать полезным. (ru)
- Задача про покриття множини є класичним питанням інформатики і теорії складності. Ця задача узагальнює NP-повну задачу про вершинне покриття (і тому є NP-складною). Попри те, що задача про вершинне покриття подібна до цієї, підхід, використаний у наближеному алгоритмі, тут не працює. Замість цього ми розглянемо жадібний алгоритм. Отриманий за ним розв'язок буде гіршим від оптимального в логарифмічне число разів. Із зростанням розміру задачі якість розв'язку погіршується, але все ж досить повільно, тому такий підхід можна вважати корисним. (uk)
- 集合覆盖问题（ Set covering problem，SCP）是组合数学、计算机科学和计算复杂性理论中的一个经典问题。 集合覆盖的决定性问题是卡普的二十一个NP-完全问题之一。 (zh)
- Das Mengenüberdeckungsproblem (oft mit set-covering-Problem notiert) ist ein Entscheidungsproblem der Kombinatorik. Es fragt, ob zu einer Menge und Teilmengen von und einer natürlichen Zahl eine Vereinigung von oder weniger Teilmengen existiert, die der Menge entspricht (Überdeckung). Als Optimierungsproblem formuliert, wird eine Überdeckung mit möglichst kleiner Anzahl der Teilmengen gesucht oder, falls den Teilmengen Kosten zugeordnet sind, eine Überdeckung mit geringsten Kosten. (de)
- El problema del Set Covering, también conocido por sus siglas SCP es un problema clásico en combinatoria, ciencias de la computación y teoría de la complejidad computacional. Es un problema que ha llevado al desarrollo de técnicas fundamentales para el campo de los algoritmos de aproximación. También es uno de los problemas de la Lista de 21 problemas NP-completos de Karp cuya NP-completitud fue demostrada en 1972. (es)
- The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972. More formally, given a universe and a family of subsets of , a cover is a subfamily of sets whose union is . In the set covering decision problem, the input is a pair and an integer ; the question is whether there is a set covering of size or less. In the set covering optimization problem, the input is a pair , and the task is to find a set covering that uses the fewest sets. (en)
- O problema de cobertura de conjuntos é uma questão clássica em combinatória, ciência da computação, pesquisa operacional e teoria da complexidade computacional . É um dos 21 problemas NP-completos de Karp mostrado ser NP-completo em 1972. É um problema "cujo estudo levou ao desenvolvimento de técnicas fundamentais para todo o campo" dos algoritmos de aproximação . A versão de decisão da cobertura do conjunto é NP-completa, e a versão de otimização / busca da cobertura do conjunto é NP-difícil . (pt)
|
