366 lines
19 KiB
TeX
366 lines
19 KiB
TeX
\documentclass[10pt,a4paper]{article}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage[T1]{fontenc}
|
|
\usepackage[ngerman,provide=*]{babel}
|
|
\usepackage{amsmath,amssymb}
|
|
\usepackage[margin=1.6cm]{geometry}
|
|
\usepackage{xcolor}
|
|
|
|
\setlength{\parindent}{0pt}
|
|
\setlength{\parskip}{0.25em}
|
|
|
|
\newcommand{\prob}[1]{\textsc{#1}}
|
|
\newcommand{\redp}{\le_p}
|
|
|
|
% Problemblock: Name
|
|
\newcommand{\pblock}[1]{\par\medskip\noindent\colorbox{black!8}{\parbox{\dimexpr\linewidth-2\fboxsep}{\textbf{\large #1}}}\par\nopagebreak\smallskip}
|
|
\newcommand{\feld}[1]{\par\nopagebreak\textbf{#1:}\ }
|
|
\newcommand{\hin}{\feld{$\Rightarrow$}}
|
|
\newcommand{\rueck}{\feld{$\Leftarrow$}}
|
|
\newcommand{\skizze}{\textcolor{red!70!black}{\textbf{[Skizze -- Detail selbst prüfen]}}\ }
|
|
|
|
\begin{document}
|
|
|
|
\begin{center}
|
|
{\LARGE\bfseries AAK Cheatsheet -- Problem-Arsenal}\\[2pt]
|
|
{\small Referenz: Definition · Beispiel · Reduktion · Konstruktion · ETH · Beweisidee je Richtung}
|
|
\end{center}
|
|
|
|
|
|
\pblock{SAT}
|
|
\feld{Def} KNF-Formel $\varphi$; existiert erfüllende Belegung?
|
|
\feld{Bsp} $(x \vee y) \wedge (\bar x \vee y \vee z) \wedge (\bar y)$ -- ja: $x{=}0, y{=}0, z{=}1$.
|
|
|
|
\pblock{3-SAT}
|
|
\feld{Def} KNF, jede Klausel $\le 3$ Literale; erfüllbar?
|
|
\feld{Bsp} $(x_1 \vee x_2 \vee x_3) \wedge (\bar x_1 \vee \bar x_2 \vee \bar x_3)$ -- ja: $x_1{=}1, x_2{=}0$.
|
|
\feld{Reduktion} von \prob{Sat}.
|
|
\feld{Konstruktion} Lange Klausel $(\ell_1 \vee \dots \vee \ell_k)$ mit frischen $y_i$ zerhacken: $(\ell_1 \vee \ell_2 \vee y_1)(\bar y_1 \vee \ell_3 \vee y_2)\dots$ $O(|\varphi|)$
|
|
\hin Erfülltes $\ell_j$ wählen, $y$-Kette davor wahr, danach falsch setzen.
|
|
\rueck Wären alle $\ell_j$ falsch, erzwingt die $y$-Kette einen Widerspruch (Dominoeffekt).
|
|
\feld{ETH} $n$, $m$, $n \le 3m$.
|
|
|
|
\pblock{$k$-CLIQUE}
|
|
\feld{Def} Graph $G$, Zahl $k$; existiert paarweise verbundene Knotenmenge $|C| \ge k$?
|
|
\feld{Bsp} Dreieck $\{1,2,3\}$ plus Kante $\{3,4\}$: $k{=}3$ ja, $k{=}4$ nein.
|
|
\feld{Reduktion} von \prob{Sat} (Vorlesung).
|
|
\feld{Konstruktion}\\
|
|
-- $V' = \{(j, \ell) \mid j \in [m],\ \ell \in C_j\}$ \quad $O(|\varphi|)$\\
|
|
-- $E' = \{\{(i, \ell), (j, \ell')\} \mid i, j \in [m],\ i \ne j,\ \ell \ne \bar\ell'\}$ \quad $O(|\varphi|^2)$\\
|
|
-- $k' = m$ \quad $O(1)$
|
|
\hin Erfüllende Belegung: pro Klausel ein wahres Literal wählen -- paarweise kompatibel $\to$ $m$-Clique.
|
|
\rueck $m$-Clique hat je Klausel genau einen Knoten; Literale widerspruchsfrei $\to$ Belegung erfüllt alle Klauseln.
|
|
\feld{ETH} $|V| = O(m)$, $|E| = O(m^2)$, $k = m$.
|
|
|
|
\pblock{$k$-INDEPENDENTSET}
|
|
\feld{Def} Graph $G$, Zahl $k$; existieren $k$ paarweise \emph{nicht} verbundene Knoten?
|
|
\feld{Bsp} Pfad $1{-}2{-}3{-}4$: $\{1,3\}$ oder $\{1,4\}$, $k{=}2$ ja.
|
|
\feld{Reduktion} von $k$-\prob{Clique}.
|
|
\feld{Konstruktion}\\
|
|
-- $V' = V$ \quad $O(|V|)$\\
|
|
-- $E' = \bar E$ \quad $O(|V|^2)$\\
|
|
-- $k' = k$ \quad $O(1)$
|
|
\hin Clique $C$ in $G$: keine $C$-interne Kante in $\bar G$ $\to$ IS der Größe $k$.
|
|
\rueck IS $S$ in $\bar G$: jedes Paar aus $S$ ist Kante in $G$ $\to$ Clique der Größe $k$.
|
|
\feld{ETH} $|V'| = |V|$, $|E'| \le |V|^2$, $k' = k$.
|
|
|
|
\pblock{VERTEXCOVER}
|
|
\feld{Def} Graph $G$, Zahl $k$; existiert $S \subseteq V$, $|S| \le k$, die jede Kante mit einem Endpunkt trifft?
|
|
\feld{Bsp} Stern (Zentrum $z$, 4 Blätter): $S = \{z\}$, $k{=}1$ ja.
|
|
\feld{Reduktion} von $k$-\prob{Clique} (Präsenz 10.2).
|
|
\feld{Konstruktion}\\
|
|
-- $V' = V$ \quad $O(|V|)$\\
|
|
-- $E' = \bar E$ \quad $O(|V|^2)$\\
|
|
-- $k' = n - k$ \quad $O(1)$
|
|
\hin Clique $C$ in $G$ $\to$ $V \setminus C$ deckt $\bar G$: in $\bar G$ gibt es keine Kante innerhalb $C$.
|
|
\rueck VC $V'$ in $\bar G$ $\to$ $V \setminus V'$ ist IS in $\bar G$ = Clique in $G$, Größe $\ge n - (n-k) = k$.
|
|
\feld{ETH} $|V'| = |V|$, $|E'| \le |V|^2$, $k' \le |V|$.
|
|
|
|
\pblock{FEEDBACKVERTEXSET (gerichtet)}
|
|
\feld{Def} Gerichteter Graph $G$, Zahl $k$; existiert $X \subseteq V$, $|X| \le k$, sodass $G \setminus X$ kreisfrei?
|
|
\feld{Bsp} Kreis $1 \to 2 \to 3 \to 1$: $X = \{1\}$, $k{=}1$ ja.
|
|
\feld{Reduktion} von \prob{VertexCover} (HA 10.1).
|
|
\feld{Konstruktion}\\
|
|
-- $V' = V$ \quad $O(|V|)$\\
|
|
-- $E' = \{(u,v), (v,u) \mid \{u,v\} \in E\}$ \quad $O(|E|)$\\
|
|
-- $k' = k$ \quad $O(1)$
|
|
\hin VC entfernt $\to$ keine Kanten mehr $\to$ kreisfrei.
|
|
\rueck Wäre Kante $\{u,v\}$ ungedeckt, bildet $(u,v,u)$ einen 2-Kreis -- Widerspruch.
|
|
\feld{ETH} $|V'| = |V|$, $|E'| = O(|E|)$, $k' = k$.
|
|
|
|
\pblock{$\Delta$COVER (Dreiecksüberdeckung)}
|
|
\feld{Def} Graph $G$, Zahl $k$; existiert $C_\Delta$, $|C_\Delta| \le k$, die jedes Dreieck trifft?
|
|
\feld{Bsp} Zwei Dreiecke mit gemeinsamer Kante $\{u,v\}$: $C_\Delta = \{u\}$, $k{=}1$ ja.
|
|
\feld{Reduktion} von \prob{VertexCover} (HA 11.1).
|
|
\feld{Konstruktion}\\
|
|
-- $V' = V \cup \{v_e \mid e \in E\}$ \quad $O(|V| + |E|)$\\
|
|
-- $E' = E \cup \{\{v_e, u\}, \{v_e, v\} \mid e = \{u,v\} \in E\}$ \quad $O(|E|)$\\
|
|
-- $k' = k$ \quad $O(1)$
|
|
\hin VC trifft jede Kante, also jedes Alt-Dreieck \emph{und} jedes neue Dreieck $\{u, v, v_e\}$.
|
|
\rueck ObdA $C_\Delta \subseteq V$ ($v_e$ durch $e_1$ tauschen, deckt weiter); dann trifft $C_\Delta$ jedes $\{u,v,v_e\}$, also jede Kante.
|
|
\feld{ETH} $|V'| = O(|V|^2)$, $|E'| = O(|E|)$.
|
|
|
|
\pblock{HAMILTONIANCYCLE (HC)}
|
|
\feld{Def} Graph $G$; existiert Kreis, der jeden Knoten genau einmal besucht?
|
|
\feld{Bsp} $C_5$ (Fünfeck): ja. $K_{1,3}$ (Stern): nein.
|
|
\feld{Reduktion} von \prob{HP}.
|
|
\feld{Konstruktion}\\
|
|
-- $V' = V \cup \{u\}$ \quad $O(|V|)$\\
|
|
-- $E' = E \cup \{\{u,v\} \mid v \in V\}$ \quad $O(|V| + |E|)$
|
|
\hin Ham-Pfad $v_1, \dots, v_n$ $\to$ Kreis $u, v_1, \dots, v_n, u$ (beide Anschlusskanten existieren via $u$).
|
|
\rueck HC in $G'$ besucht $u$ genau einmal; $u$ herausschneiden $\to$ Ham-Pfad über alle Altknoten in $G$.
|
|
\feld{ETH} $|V'| = O(|V|)$, $|E'| = O(|V|^2)$.
|
|
|
|
\pblock{HAMILTONIANPATH (HP)}
|
|
\feld{Def} Graph $G$; existiert Pfad, der jeden Knoten genau einmal besucht?
|
|
\feld{Bsp} Pfad $1{-}2{-}3$: ja. $K_{1,3}$ (Stern): nein.
|
|
\feld{Reduktion} von \prob{HC}.
|
|
\feld{Konstruktion} Wähle $v$.\\
|
|
-- $V' = V \cup \{v^*, s, t\}$ \quad $O(|V|)$\\
|
|
-- $E' = E \cup \{\{v^*, w\} \mid \{v, w\} \in E\} \cup \{\{s, v\}, \{t, v^*\}\}$ \quad $O(|E|)$
|
|
\hin HC bei $v$ aufschneiden $\to$ Pfad $s, v, \dots, v^*, t$.
|
|
\rueck Pfad muss $s, t$ als Enden haben; $v \dots v^*$ zusammenkleben ergibt HC.
|
|
\feld{ETH} $|V'| = O(|V|)$, $|E'| = O(|V|^2)$.
|
|
|
|
\pblock{TSP (Entscheidung)}
|
|
\feld{Def} Vollständiger Graph mit Distanzen, Budget $L$; Rundreise $\le L$?
|
|
\feld{Bsp} 4 Städte im Quadrat, Seitenlänge 1: OPT $= 4$.
|
|
\feld{Reduktion} von \prob{HC} (Skript).
|
|
\feld{Konstruktion}\\
|
|
-- $d(u,v) = 1$ falls $\{u,v\} \in E$, sonst $|V| + 1$ \quad $O(|V|^2)$\\
|
|
-- $L = |V|$ \quad $O(1)$
|
|
\hin HC $\to$ Tour aus lauter 1er-Kanten, Länge $|V| = L$.
|
|
\rueck Schon eine Nicht-Kante kostet $|V| + 1 > L$ $\to$ Tour $\le L$ nutzt nur Kanten aus $E$ $\to$ HC.
|
|
\feld{ETH} $|V'| = |V|$, $|E'| = O(|V|^2)$, $L = |V|$.
|
|
|
|
\pblock{$k$-COLOR}
|
|
\feld{Def} Graph $G$, Zahl $k$; existiert Färbung $f: V \to [k]$ mit $f(u) \ne f(v)$ für Kanten?
|
|
\feld{Bsp} $C_5$: 3 Farben nötig; $C_4$: 2 reichen.
|
|
\feld{Reduktion} von 3-\prob{Sat} (Skript, vollständig).
|
|
\feld{Konstruktion}\\
|
|
-- $V' = \{x_i, \bar x_i, v_i \mid i \in [n]\} \cup \{F_j \mid j \in [m]\} \cup \{z\}$ \quad $O(n + m)$\\
|
|
-- $E' = \{\{v_i, v_j\}, \{v_i, x_j\}, \{v_i, \bar x_j\} \mid i \ne j\} \cup \{\{x_i, \bar x_i\}\} \cup \{\{\ell, F_j\} \mid \text{Literal } \ell \notin C_j\} \cup \{\{v_i, z\}, \{F_j, z\}\}$ \quad $O(n^2 + nm)$\\
|
|
-- $k' = n{+}1$ \quad $O(1)$\\
|
|
Vorüberlegung: obdA $f(v_i) = i$, $f(z) = n{+}1$; dann $f(x_j), f(\bar x_j) \in \{j, n{+}1\}$ -- kodiert die Belegung.
|
|
\hin Wahres Literal bekommt Farbe $i$, falsches $n{+}1$; $F_j$ färbt man mit der Farbe eines erfüllenden Literals (keine Kante dorthin).
|
|
\rueck Wäre $F_j$ unerfüllt, sind alle Literale in $F_j$ mit $n{+}1$ gefärbt; $F_j$ sieht dann alle Farben $1, \dots, n{+}1$ -- Widerspruch.
|
|
\feld{ETH} $|V'| = O(m)$, $|E'| = O(m^2)$.
|
|
|
|
\pblock{$k$-COLOR-PRECOLORING}
|
|
\feld{Def} Graph $G$, Zahl $k$, Knoten $v_1, \dots, v_k$; existiert $k$-Färbung mit $f(v_i) = i$?
|
|
\feld{Bsp} Dreieck $v_1, v_2, w$ mit $k = 3$, $f(v_1){=}1$, $f(v_2){=}2$: $w$ bekommt Farbe 3 -- ja.
|
|
\feld{Reduktion} von $k$-\prob{Color}.
|
|
\feld{Konstruktion}\\
|
|
-- $V' = V \cup \{v_1, \dots, v_k\}$ \quad $O(|V| + k)$\\
|
|
-- $E' = E \cup \{\{v_i, v_j\} \mid i \ne j\}$ \quad $O(|E| + k^2)$\\
|
|
-- $k' = k$ \quad $O(1)$\\
|
|
-- ausgezeichnete Knoten: $v_1, \dots, v_k$ (die frischen) \quad $O(k)$
|
|
\hin $k$-Färbung von $G$ bleibt gültig; neue Clique bekommt Farben $1..k$ per Definition.
|
|
\rueck Einschränkung der Precoloring-Färbung auf $G$ ist $k$-Färbung.
|
|
\feld{ETH} $|V'| = O(|V|)$, $|E'| = O(|V|^2)$, $k' = k$.
|
|
|
|
\pblock{COVERCLIQUE}
|
|
\feld{Def} Graph $G$, Zahl $k$; existieren $k$ paarweise disjunkte Cliquen, die $V$ überdecken?
|
|
\feld{Bsp} $C_4$ (Viereck): 2 Cliquen (gegenüberliegende Kanten) -- ja für $k{=}2$.
|
|
\feld{Reduktion} von $k$-\prob{Color} (SS25-Klausur).
|
|
\feld{ETH} $|V'| = |V|$, $|E'| \le |V|^2$, $k' = k$.
|
|
|
|
\pblock{3-DIMENSIONALMATCHING (3-DM)}
|
|
\feld{Def} Disjunkte Mengen $W, X, Y$ ($|W|{=}|X|{=}|Y|{=}q$), Tripel $T \subseteq W {\times} X {\times} Y$; $q$ disjunkte Tripel, die alles überdecken?
|
|
\feld{Bsp} Ehe-Analogie mit 3 Geschlechtern: perfekte Dreier-Zuordnung.
|
|
\feld{Reduktion} von \prob{Sat} (Vorlesung; für ETH auf 3-\prob{Sat}-Instanzen anwenden).
|
|
\feld{ETH} $|W| = O(m^2)$, $|T| = O(m^4)$.
|
|
|
|
\pblock{3-EXACTCOVER (X3C)}
|
|
\feld{Def} Grundmenge $U$ ($|U| = 3q$), 3er-Mengen $F$; exakte Überdeckung durch disjunkte Mengen?
|
|
\feld{Bsp} $U = \{1,\dots,6\}$, $F = \{\{1,2,3\}, \{4,5,6\}, \{2,3,4\}\}$: ja (erste zwei Mengen).
|
|
\feld{Reduktion} von 3-DM.
|
|
\feld{ETH} $|U'| = O(|W|)$, $|F'| = |T|$.
|
|
|
|
\pblock{SUBSETSUM}
|
|
\feld{Def} Größen $a_1, \dots, a_n$, Ziel $T$; Teilmenge mit Summe genau $T$?
|
|
\feld{Bsp} $\{3, 5, 7, 11\}$, $T = 12$: ja ($5 + 7$).
|
|
\feld{Reduktion} von X3C (Vorlesung).
|
|
\feld{Konstruktion}\\
|
|
-- $c_j = \sum_{u_i \in S_j} (n{+}1)^{i-1}$ (Menge als Bitvektor zur Basis $n{+}1$) \quad $O(|F| \cdot |U|)$\\
|
|
-- $K = \sum_{j=0}^{3m-1} (n{+}1)^{j}$ (überall Ziffer 1) \quad $O(|U|)$
|
|
\hin Exact Cover $\to$ jede Position genau einmal überdeckt $\to$ Summe $= K$.
|
|
\rueck $\le n$ Summanden, Basis $n{+}1$ $\to$ kein Übertrag $\to$ jede Position genau eine 1 $\to$ gewählte Mengen überdecken exakt.
|
|
\feld{ETH} $n' = |F|$.
|
|
|
|
\pblock{SUBSETSUMCARDINALITY}
|
|
\feld{Def} Größen $c_1, \dots, c_n$ ($n$ gerade), Ziel $K$; existiert $S$ mit Summe $K$ und $|S| = n/2$?
|
|
\feld{Bsp} $\{1, 2, 3, 8\}$, $K = 9$, $|S| = 2$: ja ($1 + 8$).
|
|
\feld{Reduktion} von \prob{SubsetSum} (Präsenz 11.3).
|
|
\feld{Konstruktion}\\
|
|
-- $c_i' = c_i + 1$ für $i \in [n]$ \quad $O(n)$\\
|
|
-- $n$ Einser-Items: $c_{n+1}' = \dots = c_{2n}' = 1$ \quad $O(n)$\\
|
|
-- $K' = K + n$ \quad $O(1)$
|
|
\hin Lösung $S$ plus $n - |S|$ Einser: Kardinalität $n$, Summe $K + |S| + (n - |S|) = K + n$.
|
|
\rueck $S = S' \cap [n]$: Einser tragen $n - |S|$ bei $\to$ $\sum_{i \in S} c_i = K$.
|
|
\feld{ETH} $n' = O(n)$.
|
|
|
|
\pblock{$(a_1 = 1)$-SUBSETSUM}
|
|
\feld{Def} \prob{SubsetSum}-Instanz mit $a_1 = 1$; Teilmenge mit Summe genau $K$?
|
|
\feld{Bsp} $\{1, 4, 6\}$, $K = 7$: ja ($1 + 6$).
|
|
\feld{Reduktion} von \prob{SubsetSum}.
|
|
\feld{Konstruktion}\\
|
|
-- $a_1' = 1$ \quad $O(1)$\\
|
|
-- $a_{i+1}' = 2 c_i$ für $i \in [n]$ \quad $O(n)$\\
|
|
-- $K' = 2K$ \quad $O(1)$
|
|
\hin Lösung $S$ $\to$ verdoppelte Items summieren zu $2K$, ohne die 1.
|
|
\rueck $2K$ gerade, alle Items außer der 1 gerade $\to$ 1 nie nutzbar (Parität); halbieren ergibt Summe $K$.
|
|
\feld{ETH} $n' = O(n)$.
|
|
|
|
\pblock{SUBSETSUM MIT TEILBARKEIT (durch 3 oder 7)}
|
|
\feld{Def} \prob{SubsetSum}-Instanz, jede Größe durch 3 oder 7 teilbar; Teilmenge mit Summe genau $K$?
|
|
\feld{Bsp} $\{3, 7, 21\}$, $K = 10$: ja ($3 + 7$).
|
|
\feld{Reduktion} von \prob{SubsetSum}.
|
|
\feld{Konstruktion}\\
|
|
-- $a_i' = 21\, c_i$ \quad $O(n)$\\
|
|
-- $K' = 21\, K$ \quad $O(1)$
|
|
\hin Lösung skaliert mit: Summe $21K$.
|
|
\rueck Summe $21K$ durch 21 teilen $\to$ Summe $K$; $21c$ ist durch 3 und 7 teilbar.
|
|
\feld{ETH} $n' = n$.
|
|
|
|
\pblock{SUBSETSUM OHNE ZWEIERPOTENZEN}
|
|
\feld{Def} \prob{SubsetSum}-Instanz, keine Größe eine Zweierpotenz $2^t$; Teilmenge mit Summe genau $K$?
|
|
\feld{Bsp} $\{3, 5, 6\}$, $K = 9$: ja ($3 + 6$).
|
|
\feld{Reduktion} von \prob{SubsetSum}.
|
|
\feld{Konstruktion}\\
|
|
-- $a_i' = 3\, c_i$ \quad $O(n)$\\
|
|
-- $K' = 3K$ \quad $O(1)$
|
|
\hin Lösung skaliert mit: Summe $3K$.
|
|
\rueck Summe $3K$ durch 3 teilen; $3c$ ist nie $2^t$, da $3 \nmid 2^t$.
|
|
\feld{ETH} $n' = n$.
|
|
|
|
\pblock{PARTITION}
|
|
\feld{Def} Zahlen $c_1, \dots, c_n$; existiert $S$ mit $\sum_{i \in S} c_i = \frac12 \sum_i c_i$?
|
|
\feld{Bsp} $\{1, 2, 3, 4\}$: $\{1,4\} | \{2,3\}$ -- ja.
|
|
\feld{Reduktion} von \prob{SubsetSum} (Skript).
|
|
\feld{Konstruktion}\\
|
|
-- $N = \sum_{j=1}^n c_j + 1$ \quad $O(n)$\\
|
|
-- $c_{n+1} = N - K$, $c_{n+2} = K + 1$ \quad $O(1)$\\
|
|
-- Gesamtsumme $= 2N$, Hälfte $= N$
|
|
\hin Lösung $S$: $S \cup \{c_{n+1}\}$ summiert zu $K + (N - K) = N$.
|
|
\rueck $c_{n+1}, c_{n+2}$ nie zusammen (Summe $N + 1 > N$); obdA $c_{n+1} \in S$ $\to$ Rest von $S$ summiert zu $N - (N - K) = K$.
|
|
\feld{ETH} $n' = O(n)$.
|
|
|
|
\pblock{$P2\,\|\,C_{\max}$ (2 Maschinen)}
|
|
\feld{Def} Jobs $p_1, \dots, p_n$, Schranke $T$; Schedule auf 2 Maschinen mit Makespan $\le T$?
|
|
\feld{Bsp} Jobs $3,3,2,2,2$, $T = 6$: ja ($\{3,3\}$ und $\{2,2,2\}$).
|
|
\feld{Reduktion} von \prob{Partition}.
|
|
\feld{Konstruktion}\\
|
|
-- Jobs = Zahlen \quad $O(n)$\\
|
|
-- $m = 2$ \quad $O(1)$\\
|
|
-- $T = \frac12 \sum p_j$ \quad $O(n)$
|
|
\hin Partition $=$ perfekt balancierter Schedule.
|
|
\rueck Makespan $\frac12 \sum$ erzwingt exakte Balance $=$ Partition.
|
|
\feld{ETH} $n' = n$, $T = O(\textstyle\sum a_i)$.
|
|
|
|
\pblock{KNAPSACK (Entscheidung)}
|
|
\feld{Def} Gewichte $w_i$, Profite $p_i$, Schranken $K, P$; Auswahl mit $\sum w_i \le K$ und $\sum p_i \ge P$?
|
|
\feld{Bsp} Items $(w,p)$: $(2,3), (3,4)$; $K = 3$, $P = 4$: ja (zweites Item).
|
|
\feld{Reduktion} von \prob{SubsetSum}.
|
|
\feld{Konstruktion}\\
|
|
-- $w_i = p_i = a_i$ \quad $O(n)$\\
|
|
-- $K = P = T$ \quad $O(1)$
|
|
\hin Summe $= T$ $\to$ Gewicht $\le K$ und Profit $\ge P$.
|
|
\rueck Gewicht $\le T$ und Profit $\ge T$ zugleich $\to$ Summe exakt $T$.
|
|
\feld{ETH} $n' = n$, $K = P = T$.
|
|
|
|
\pblock{HITTINGSET}
|
|
\feld{Def} Universum $U$, Mengen $F_1, \dots, F_r$, Zahl $k$; existiert $H$, $|H| \le k$, das jede $F_i$ trifft?
|
|
\feld{Bsp} $U = \{1..5\}$, $F = \{1,2\}, \{2,3\}, \{4,5\}$: $H = \{2, 4\}$, $k{=}2$ ja.
|
|
\feld{Reduktion} von 3-\prob{Sat} (HA 12.2 / Probeklausur).
|
|
\feld{ETH} $|U| = O(n)$, $r = O(m)$, $k = n$.
|
|
|
|
\pblock{NAE-4-SAT}
|
|
\feld{Def} Klauseln $\le 4$ Literale; Belegung, sodass jede Klausel wahres UND falsches Literal hat (``not all equal'')?
|
|
\feld{Bsp} $(x \vee y \vee z)$: $x{=}1, y{=}0$ -- ja. $(x)$ allein: nein (nie beides).
|
|
\feld{Reduktion} von 3-\prob{Sat} (SS25-Klausur).
|
|
\feld{ETH} $n' = O(n)$, $m' = m$.
|
|
|
|
\pblock{HALT$_{\mathrm{TM}}$ (nur NP-schwer!)}
|
|
\feld{Def} DTM $M$, Wort $w$; hält $M$ auf $w$?
|
|
\feld{Bsp} $M$ = Endlosschleife auf jeder Eingabe: nein für jedes $w$.
|
|
\feld{Reduktion} von 3-\prob{Sat} (HA 11.2).
|
|
\feld{Konstruktion}\\
|
|
-- $M_\varphi$: probiere alle $2^n$ Belegungen; falls eine erfüllt, halte; sonst Endlosschleife \quad $O(|\varphi|)$\\
|
|
-- $w = \langle \varphi \rangle$ \quad $O(|\varphi|)$
|
|
\hin Erfüllbar $\to$ $M_\varphi$ findet Belegung und hält.
|
|
\rueck $M_\varphi$ hält nur im Erfolgsfall $\to$ erfüllbar.
|
|
|
|
\pblock{GÜTE: $\Delta$TSP1}
|
|
\feld{Algorithmus} MST $T$ $\to$ Kanten verdoppeln $\to$ Eulerkreis $\to$ Abkürzen.
|
|
\feld{Güte} $2$.
|
|
\feld{Beweis}\\
|
|
-- Kante aus optimaler Tour entfernen $\to$ Spannbaum $\to$ $w(T) \le \mathrm{OPT}$\\
|
|
-- Verdoppeln: Eulerkreis der Länge $2\,w(T) \le 2\,\mathrm{OPT}$\\
|
|
-- Abkürzen verlängert nicht ($\Delta$-Ungleichung)
|
|
|
|
\pblock{GÜTE: CHRISTOFIDES ($\Delta$TSP2)}
|
|
\feld{Algorithmus} MST $T$ $\to$ $X$ = Knoten ungeraden Grades $\to$ min.\ perfektes Matching $M$ auf $X$ $\to$ Eulerkreis in $T + M$ $\to$ Abkürzen.
|
|
\feld{Güte} $\frac32$.
|
|
\feld{Beweis}\\
|
|
-- $w(T) \le \mathrm{OPT}$ (Tour minus Kante = Spannbaum)\\
|
|
-- $|X|$ gerade; optimale Tour auf $X$ abkürzen $\to$ Kreis $C$ mit $d(C) \le \mathrm{OPT}$\\
|
|
-- $C$ zerfällt in zwei perfekte Matchings $M_1, M_2$ $\to$ $w(M) \le \min \le \frac12 \mathrm{OPT}$\\
|
|
-- Eulerkreis in $T + M$: $w(T) + w(M) \le \frac32 \mathrm{OPT}$; Abkürzen verlängert nicht
|
|
\feld{Scharf} Leitergraph (Präsenz 12.2): Zick-Zack-MST ($n{-}1$) + Matchingkante $\{1, n\}$ der Länge $\frac n2$ $\to$ Rate $\frac{n - 1 + n/2}{n} \to \frac32$.
|
|
|
|
\pblock{GÜTE: GREEDY-KNAPSACK (Widerlegung)}
|
|
\feld{Algorithmus} Absteigend nach Dichte $p_i/w_i$; packe jedes noch passende Item.
|
|
\feld{Güte} Unbeschränkt -- keine konstante Güte.
|
|
\feld{Beweis}\\
|
|
-- Instanz $(w, p) = (1, 1), (B, B{-}1)$, Kapazität $B$\\
|
|
-- Dichten: $1 > \frac{B-1}{B}$ $\to$ Greedy packt Item 1; Item 2 passt nicht mehr\\
|
|
-- $GA = 1$, $\mathrm{OPT} = B - 1$ $\to$ Rate $B - 1 \to \infty$
|
|
|
|
\pblock{GÜTE: MODIFIEDGREEDY (Knapsack)}
|
|
\feld{Algorithmus} $\mathrm{MGA} = \max\{\text{Greedy-Lösung},\ \text{profitreichstes Einzelitem}\}$.
|
|
\feld{Güte} $2$, d.h.\ $\mathrm{OPT} \le 2\,\mathrm{MGA}$.
|
|
\feld{Beweis}\\
|
|
-- $k{+}1$ = erstes Item, das Greedy nicht mehr packt\\
|
|
-- fraktionale Relaxierung: $\mathrm{OPT} \le \mathrm{OPT}_f \le p_1 + \dots + p_k + p_{k+1}$\\
|
|
-- $p_1 + \dots + p_k \le GA$ und $p_{k+1} \le p_{\max}$\\
|
|
-- $\mathrm{OPT} \le GA + p_{\max} \le 2 \max\{GA, p_{\max}\} = 2\,\mathrm{MGA}$
|
|
|
|
\pblock{GÜTE: LISTSCHEDULING ($P\,\|\,C_{\max}$)}
|
|
\feld{Algorithmus} Jobs der Reihe nach auf die aktuell leerste Maschine.
|
|
\feld{Güte} $2 - \frac1m$.
|
|
\feld{Beweis}\\
|
|
-- $J_k$ = letzter Job auf der vollsten Maschine (Last $L$); bei Platzierung war sie die leerste\\
|
|
-- alle Maschinen hatten Last $\ge L - p_k$ $\to$ $\sum_i p_i \ge m(L - p_k) + p_k$\\
|
|
-- $\mathrm{OPT} \ge \frac1m \sum_i p_i \ge L - (1 - \frac1m) p_k$\\
|
|
-- $p_k \le \mathrm{OPT}$ einsetzen $\to$ $L \le (2 - \frac1m)\,\mathrm{OPT}$
|
|
\feld{Scharf} (Skript!) $m(m{-}1)$ Einser + $1$ Job der Größe $m$: $LS = 2m - 1$, $\mathrm{OPT} = m$.
|
|
|
|
\pblock{GÜTE: LPT}
|
|
\feld{Algorithmus} Jobs absteigend sortieren, dann ListScheduling.
|
|
\feld{Güte} $\frac43 - \frac1{3m}$.
|
|
\feld{Beweis}\\
|
|
-- wie LS: $\mathrm{LPT} \le \mathrm{OPT} + (1 - \frac1m) p_n$ ($p_n$ = Job, der den Makespan setzt)\\
|
|
-- Fall $p_n \le \frac13 \mathrm{OPT}$: einsetzen $\to$ $(\frac43 - \frac1{3m})\,\mathrm{OPT}$\\
|
|
-- Fall $p_n > \frac13 \mathrm{OPT}$: alle Jobs $> \frac13 \mathrm{OPT}$ $\to$ optimal höchstens 2 Jobs pro Maschine $\to$ LPT ist optimal
|
|
|
|
\pblock{GÜTE: 2ApproxVC}
|
|
\feld{Algorithmus} Kanten durchgehen; sind beide Endpunkte neu, nimm beide in $C$ auf.
|
|
\feld{Güte} $2$, d.h.\ $|C| \le 2\,|C^*|$.
|
|
\feld{Beweis}\\
|
|
-- $A$ = aufgenommene Kanten $\to$ $|C| = 2|A|$\\
|
|
-- $A$ ist Matching: gemeinsamer Endpunkt wäre schon in $C$ gewesen\\
|
|
-- $C^*$ braucht pro Kante aus $A$ einen \emph{eigenen} Knoten $\to$ $|C^*| \ge |A|$\\
|
|
-- $|C| = 2|A| \le 2\,|C^*|$
|
|
|
|
\pblock{GÜTE: MAX-3-SAT}
|
|
\feld{Algorithmus} Werte $\beta_0$ (alles falsch) und $\beta_1$ (alles wahr) aus; gib die bessere zurück.
|
|
\feld{Güte} $2$, d.h.\ $v(A(\varphi)) \ge \frac12 v(\mathrm{OPT})$.
|
|
\feld{Beweis}\\
|
|
-- jede Klausel hat $\ge 1$ Literal; negatives Literal $\to$ $\beta_0$ erfüllt, positives $\to$ $\beta_1$\\
|
|
-- also $v(\beta_0) + v(\beta_1) \ge m$\\
|
|
-- $\max \ge$ Durchschnitt $\ge \frac m2 \ge \frac12 v(\mathrm{OPT})$
|
|
\feld{Scharf} $(x_1 \vee x_2 \vee x_3) \wedge (\bar x_1 \vee \bar x_2 \vee \bar x_3)$: $A = 1$, $\mathrm{OPT} = 2$ (via $x_1 = 1, x_2 = 0$).
|
|
|
|
\end{document}
|