Algorithmes pour l'empaquetage des ensembles

Il semble y avoir beaucoup de travail, pour certains problèmes NP-Hard, sur le développement d'algorithmes exacts à temps exponentiel rapide (c'est-à-dire, les résultats de la forme: L'algorithme A résout le problème en temps O (c ^ n), avec c petit). Il semble y avoir beaucoup de travail dans ce sens pour certains problèmes NP-difficiles (par exemple, Mesurer et conquérir: un simple algorithme d'ensemble indépendant . SODA'06 ) mais je n'ai pas été capable de trouver un travail similaire pour le problème d'emballage défini. Il semble y avoir un travail similaire sur certaines restrictions du problème d'emballage d'ensemble (par exemple, un algorithme paramétré An pour l'emballage à 3 ensembles), mais je n'en ai trouvé aucun pour l'emballage d'ensemble général. problème. $x$ $O(2^{0.288n})$ $O^{*}(3.523^{k})$

Ma question est donc la suivante: quelle est la meilleure complexité temporelle pour résoudre exactement le problème de pondération des ensembles où il y a ensembles tirés d'un univers de éléments? $m$ $n$

Je m'intéresse également à la relation entre le nombre d'ensembles et la taille de l'univers. Par exemple, y a-t-il eu des travaux algorithmiques sur des situations où est relativement grand par rapport à (c'est-à-dire proche de )? $m$ $n$ $2^n$

ds.algorithms Service Travis
la source

Google ? "définir l'emballage"? en.wikipedia.org/wiki/Set_packing ce n'est pas encore une question de niveau de recherche (voir notre FAQ). Fermeture maintenant ...

Suresh Venkat

@Suresh, je suis intéressé par les résultats de la forme: L'algorithme A résout le problème d'emballage défini en temps O (c ^ n), avec c petit. Il y a un tel travail pour d'autres problèmes NP-difficiles (par exemple, Mesurer et conquérir: un simple algorithme d'ensemble indépendant O (2 ^ 0,288n). SODA'06). L'article wikipedia que vous liez ne traite pas de cela et je n'ai trouvé aucun article récent sur la complexité du temps de mise en paquet. La plupart des travaux que j'ai trouvés portent sur le problème d'emballage de k-set. Il s'agit d'une question de type "demande de référence". Ces sortes de questions sont-elles les bienvenues ici? ou peut-être que la question n'était pas assez bien écrite?

Travis Service du

Cela a beaucoup plus de sens en fait. le point clé est que vous recherchez des algorithmes EXACT pour le conditionnement des ensembles pondérés. Si vous souhaitez reformuler, fournir des références pour l' emballage

set (ainsi que ce que c'est), alors je serais heureux de rouvrir - il suffit de le signaler à l'attention du modérateur.

k

$k$

Suresh Venkat

Je recommanderais de rouvrir cette question. La «complexité temporelle» fait généralement référence à des algorithmes exacts, sauf indication contraire, non?

arnab

Cette question devrait être rouverte.

Peter Shor

En effet, l'empaquetage, le partitionnement et le recouvrement des ensembles ont été étudiés en termes de temps d'exécution exacts des algorithmes. Pour répondre à votre dernière question, vous pouvez résoudre l'empaquetage d'ensemble pondéré en temps par programmation dynamique dans tous les sous-ensembles de . De plus, si vos poids entiers sont limités par , vous pouvez le résoudre en temps , même si est aussi grand que , voir $O(m2^n)$ $[n]$ $M$ $O(M2^n)$ $m$ $2^n$

http://dx.doi.org/10.1137/070683933

BTW, Le résultat paramétré que vous indiquez pour ensembles n'est pas le plus connu, voir $3$

http://arxiv.org/abs/1007.1161

pour un algorithme de pointe et une liste des résultats précédents sur le problème.

Andreas Björklund
la source

Algorithmes pour l'empaquetage des ensembles

Réponses: