Auswahl von k Sub-Posets

Ich stieß beim Experimentieren mit Klassifikationsalgorithmen auf das folgende algorithmische Problem. Elemente werden in eine Polyhierarchie klassifiziert, was ich als Poset mit einer einzigen Wurzel verstehe. Ich muss das folgende Problem lösen, das dem set cover problem sehr ähnelt.Auswahl von k Sub-Posets

Ich habe meine Latex-Ed Problembeschreibung here hochgeladen.

Einen Approximationsalgorithmus zu entwickeln, der 1 & 2 erfüllt, ist ziemlich einfach. Beginne einfach an den Scheitelpunkten von G und "gehe nach oben" oder fange an der Wurzel an und gehe "nach unten". Angenommen, Sie beginnen bei der Wurzel, erweitern iterativ die Scheitelpunkte und entfernen dann unnötige Scheitelpunkte, bis Sie mindestens k Untergitter haben. Die Approximationsgrenze hängt von der Anzahl der untergeordneten Elemente eines Stützpunkts ab, was für meine Anwendung in Ordnung ist.

Weiß jemand, ob dieses Problem einen richtigen Namen oder vielleicht die Tree-Version des Problems hat? Ich wäre daran interessiert herauszufinden, ob dieses Problem NP-schwer ist, vielleicht hat jemand Ideen für ein gutes NP-schweres Problem zu reduzieren oder hat einen polynomischen Algorithmus, um das Problem zu lösen. Wenn Sie beide haben, sammeln Sie your million dollar price. ;)

Quelle

2010-07-17 dareios

Ich verstehe nicht. Wenn Sie S '= {r} wählen, wobei r die Wurzel ist, dann gilt \ sigma (r) = V. Bedeutet man, dass sigma (s) alle Elemente kleiner oder gleich r und größer oder gleich s ist (wo immer kleiner die Gitterordnung ist? – deinst

@deinst Deshalb ist 'k' da: um das Problem interessanter zu machen :)' S = {r} 'ist die Lösung für' k = 1'. – Bolo

@dareios Sie möchten möglicherweise zwei kleinere Fehler in der Problembeschreibung korrigieren. 1) Der vorletzte Absatz ist im allgemeinen nicht wahr, hängt von der Wahl von 'G' ab (außer ich vermisse etwas, wenn' G' zwei Kinder enthält und nichts mehr, dann ist 'S = G' eine Lösung mit' l = k = 2 '. 2) Im drittletzten Absatz meinen Sie wahrscheinlich: "[...] wir wollen immer noch ** 2 ** behalten." – Bolo

Die DAG-Version ist hart durch (Trommelwirbel) eine Reduzierung von Set-Cover. Setze k = 2 und mache das Offensichtliche: Bedingung (2) verhindert, dass wir die Wurzel nehmen. (Man beachte, dass (3) aufgrund der unteren Grenze k eigentlich nicht (2) impliziert.)

Die Baumversion ist ein Spezialfall der seriell-parallelen Poset-Version, die genau in polynomieller Zeit gelöst werden kann. Hier ist eine rekursive Formel, die ein Polynom p (x) gibt, wobei der Koeffizient von x ⁿ die Anzahl der Abdeckungen der Kardinalität n ist.

Einzelner Vertex, der abgedeckt werden soll: p (x) = x.

Anderer Eckpunkt: p (x) = 1 + x.

Parallele Zusammensetzung, wobei q und r die Polynome für die zwei Posets sind: q (x) r (x).

Serienkomposition, wobei q das Polynom für das obere Poset und r ist, für das untere: Wenn das oberste Poset keine zu bedeckenden Ecken enthält, dann ist p (x) = (q (x) - 1) + r (x); andernfalls ist p (x) = q (x).

Quelle

2010-07-17 16:45:21 user382751

Gute Beobachtung mit (3) impliziert nicht (2), das habe ich total vermisst. In der Problembeschreibung geändert. Für den Rest denke ich, dass ich zuerst eine Nacht Schlaf brauche, danke für deine Antwort! – dareios

Die Reduktion ist in der Tat einfach, weiß nicht, warum ich es gestern nicht konnte. Vielen Dank! – dareios

Für die Tree-Version Rekursionsformel: Wenn ich einen einzelnen Vertex haben soll, habe ich p (x) = x, wie Sie sagen, da es nur eine Abdeckung gibt. Für keine zu bedeckenden Ecken sollten wir p (x) = 1 haben (da die Deckung leer ist). Ich verstehe nicht, wenn das "Andere Eckpunkt: p (x) = 1 + x" Polynom angewendet wird. Ich verstehe auch nicht, wenn die "obere Pose enthält keine Scheitelpunkte" (zu verdecken) gilt: Die obere Pose wird immer die anderen Posets enthalten, so dass die anderen Posets nicht enthalten, wenn sie keine zu bedeckenden Scheitelpunkte enthalten entweder. Vielleicht kommt hier die> = k-Beschränkung der Mindesteigenschaft ins Spiel? – dareios

Auswahl von k Sub-Posets

Antwort

Verwandte Themen