J'ai rencontré le problème algorithmique suivant lors de l'expérimentation d'algorithmes de classification. Les éléments sont classés dans une poly-hiérarchie, ce que je comprends être un poset avec une seule racine. Je dois résoudre le problème suivant, qui ressemble beaucoup à set cover problem.Sélection de k sous-poses
J'ai téléchargé ma description du problème Latex-ed here.
Développer un algorithme d'approximation qui satisfait 1 & 2 est assez facile, commencez simplement aux sommets de G et «marchez» ou commencez à la racine et «descendez». Supposons que vous commenciez à la racine, développez itérativement les vertex, puis supprimez les vertices inutiles jusqu'à ce que vous ayez au moins k sous-réseaux. L'approximation liée dépend du nombre d'enfants d'un sommet, ce qui est OK pour mon application.
Est-ce que quelqu'un sait si ce problème a un nom propre, ou peut-être la version arborescente du problème? Je serais intéressé de savoir si ce problème est NP-difficile, peut-être que quelqu'un a des idées pour un bon problème NP-difficile à réduire ou a un algorithme polynomial pour résoudre le problème. Si vous avez tous deux recueillir your million dollar price. ;)
Je ne comprends pas. Si vous choisissez S '= {r} où r est la racine, alors \ sigma (r) = V. Voulez-vous dire sigma (s) être tous les éléments inférieurs ou égaux à r et supérieurs ou égaux à s (où moins et plus grand sont l'ordre partiel de réseau)? – deinst
@deinst C'est pourquoi 'k' est là: pour rendre le problème plus intéressant :)' S = {r} 'est la solution pour' k = 1'. – Bolo
@dareios Vous pouvez corriger deux erreurs mineures dans l'énoncé du problème. 1) Le second dernier paragraphe n'est pas vrai en général, dépend du choix de 'G' (sauf si je manque quelque chose, si' G' contient deux enfants et rien de plus, alors 'S = G' est une solution avec' l = k = 2 »2) Au troisième paragraphe, vous voulez probablement dire:« [...] nous voulons toujours garder ** 2 ** ». – Bolo