Forum:  Graphentheorie
Thema: Maximaler Schnitt und Zielfunktionen
Themen-Übersicht
joey24
Junior
Dabei seit: 11.08.2020
Mitteilungen: 5
Aus:
Themenstart: 2020-08-11 10:50

Hallo Community,
ist mein erster Post daher nimmt es mir bitte nicht übel wenn ich einige Formalien nicht richtig einhalte.

Ich befasse mich aktuell mit dem MaxCut Problem.
Die Zielfunktion ist recht trivial.
Meine Frage wäre, gibt es verschiedene Zielfunktionen, die sich auf das MaxCut Problem beziehen und welche Vorteile bringen sie ?

Bspw ist Goemans Williamson ein approximations Algorithmus, wäre es sinnvoll es hier umzuformulieren um eine andere Zielfunktion zu erhalten ?

Und ausserdem ist es nicht so dass MaxCut <=> MinCut mit negativen Gewichten ist ? Ist dann MinCut.. auch NP ?
Dann würden sich einige vers. Zielfunktionen ergeben.

LG
Joey


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6233
Aus: Milchstraße
Beitrag No.1, eingetragen 2020-08-11 11:24

Hallo joey24,

willkommen auf dem Matheplaneten.

Beim Max-Cut- und beim Min-Cut-Problem werden stets nicht-negative Kantengewichte vorausgesetzt. Und: Das Min-Cut-Problem liegt in P.

Deine Frage nach den verschiedenen Zielfunktionen habe ich nicht verstanden.

Grüße
StrgAltEntf


[Verschoben aus Forum 'Numerik & Optimierung' in Forum 'Graphentheorie' von StrgAltEntf]


joey24
Junior
Dabei seit: 11.08.2020
Mitteilungen: 5
Aus:
Beitrag No.2, vom Themenstarter, eingetragen 2020-08-11 11:30

Hi, vorweg danke für die Antwort.

Die eigentliche Problematik besteht darin , das MaxCut Problem in Quantum Computer zu formulieren, sprich die Zielfunktion als Hamiltonian.

Die Zielfunktion die hier normalerweise Verwendet wird lautet:
C(z) = 1/2 sum(1-z_i*z_j)

Nun ist die Aufgabe:
Verschiedene Zielfunktionen bereitzustellen, die sich auf das MaxCut Problem beziehen.

LG


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6233
Aus: Milchstraße
Beitrag No.3, eingetragen 2020-08-11 12:20

Wahrscheinlich bin ich hier nicht der richtige Kompetenzträger.

Was ist denn z bzw. z_i?


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6571
Aus: Niedersachsen
Beitrag No.4, eingetragen 2020-08-11 13:23

Sei $G=(V,E)$ der Graph.
Ich vermute, dass die Zielfunktion $1/2\sum_{i<j,\{i,j\}\in E}{1-z_iz_j}$ heißen soll.
Dabei nimmt $z_i$ den Wert $1$ an, wenn der Knoten $v_i$ in der Knotenmenge $A$ ist und den Wert $-1$, wenn der Knoten in der Menge $V-A$ ist.
Die Summe zählt also alle Kanten, bei denen ein Endknoten in $A$ ist und der andere nicht.

Eine andere mögliche Zielfunktion wäre $\sum_{\{i,j\}\in E}{(1-z_i)z_j}$, wobei die $z_i$ Werte aus $\{0,1\}$ annehmen.

Das Ganze kann man auch mit Kantengewichten versehen, also in etwa
$1/2\sum_{i<j,\{i,j\}\in E}{(1-z_iz_j)\cdot w_{ij}}$ .


joey24
Junior
Dabei seit: 11.08.2020
Mitteilungen: 5
Aus:
Beitrag No.5, vom Themenstarter, eingetragen 2020-08-11 14:11

Danke euch beiden :)

Genau so habe ich es gemeint :)

Die Frage die sich mir jetzt stellt ist, man könnte auch äquivalent z_j aus {0,1} nehmen und hätte die gleiche Zielfunktion.

Ausserdem, kann man die Bedingung dass die Klausel erfüllt ist auch auf {0,1} überführen und behaupten das es der Knoten in der Menge V-A enthalten ist z_i = 0 gesetzt wird ?

Alle guten Dinge sind drei :D daher noch die Frage, wären die drei Zielfunktionen die einzigen die man aus der MaxCut Problematik formulieren kann ?
LG


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6571
Aus: Niedersachsen
Beitrag No.6, eingetragen 2020-08-11 15:52

Ich verstehe nicht, worauf Du hinaus willst.
Du hast jetzt zwei verschiedene Modellierungen für das MAXCUT-Problem.
Die Variablen-Werte haben unterschiedliche Bedeutungen, es wird auf unterschiedliche Weise gezählt und die Summenformeln sehen unterschiedlich aus.
Das lässt sich sicher auch noch anders formulieren:
$\sum_{i\in V}{(1-z_i)\sum_{j\in N(i)}{z_j}}$, oder ...
Letzten Endes zählen aber alle Formeln das Gleiche: Die Zahl der Kanten zwischen eine irgendwie gekennzeichneten Menge A und dem Rest V-A.

Mir ist nicht klar, ob Du das suchst, oder eigentlich Varianten des MAXCUT-Problems mit _anderen_ Zielfunktionen oder zusätzlichen Bedingungen:
- gewichtetes MAXCUT
- maximaler Schnitt, der den Graph in genau zwei Zusammenhangskomponenten teilt
- MAXCUT auf speziellen Graphen
- ...


joey24
Junior
Dabei seit: 11.08.2020
Mitteilungen: 5
Aus:
Beitrag No.7, vom Themenstarter, eingetragen 2020-08-11 16:15

Die eigentliche Frage lautet:

"Stelle verschiedene Zielfunktionen auf, die sich auf das MaxCut Problem beziehen:

    -Welche Aspekte tragen zum Erfolg bei?
    -Welche Aspekte halten sie für nützlich?
    -Können sie andere nützliche Zielfunktionen für das MaxCut Problem
     bereitstellen ? "


Da bin ich davon ausgegangen dass die Rede von Zielfunktionen ist und jetzt bin ich auch ein wenig verwirrt 🙄


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6571
Aus: Niedersachsen
Beitrag No.8, eingetragen 2020-08-11 21:10

Beziehen sich diese Fragen auf die Lösbarkeit mit Hilfe eines Quantencomputers? Leider kann ich in dem Fall nicht sagen, welche Aspekte dafür nützlich sind.

Eine interessante Gleichung ist mir noch eingefallen. Im Fall $z_i, z_j\in\{-1,+1\}$ gilt wegen $z_i^2=z_j^2=1$:
$1-z_i\cdot z_j = (z_i-z_j)^2/2$.


joey24
Junior
Dabei seit: 11.08.2020
Mitteilungen: 5
Aus:
Beitrag No.9, vom Themenstarter, eingetragen 2020-08-12 18:49

Genau, mit Hilfe des Quantencomputers und in diesem Fall QAOA.
Danke für die interessante Gleichung :)




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=248987=7080
Druckdatum: 2020-10-20 00:01