1375 lines
68 KiB
TeX
1375 lines
68 KiB
TeX
% !TeX spellcheck = de_DE
|
|
\documentclass[11pt,a4paper,toc]{scrartcl}
|
|
\usepackage[a4paper,left=2.5cm,right=2.5cm,top=2.5cm,bottom=2.5cm]{geometry}
|
|
\usepackage[ngerman]{babel}
|
|
\usepackage{amssymb}
|
|
\usepackage{scrextend}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage[T1]{fontenc}
|
|
\usepackage{amsmath}
|
|
\usepackage{amsthm}
|
|
\usepackage{enumitem}
|
|
\usepackage{mathtools}
|
|
\usepackage[load=named]{siunitx}
|
|
\usepackage{csquotes}
|
|
\usepackage[hidelinks]{hyperref}
|
|
\usepackage{algorithmicx}
|
|
\usepackage{algpseudocode}
|
|
\usepackage{tikz}
|
|
%\usetikzlibrary{positioning}
|
|
%\usetikzlibrary{arrows.meta}
|
|
%\usetikzlibrary{quotes}
|
|
%\usetikzlibrary{angles}
|
|
%\usetikzlibrary{babel}
|
|
%\usetikzlibrary{fit}
|
|
%\usepackage{datetime}
|
|
%\usepackage{xcolor}
|
|
\usepackage{lmodern}
|
|
\usepackage[ngerman]{cleveref}
|
|
|
|
% Formatierung
|
|
\newcommand*{\algo}[1]{\textsc{#1}}
|
|
\newcommand*{\problem}[1]{\textsc{#1}}
|
|
|
|
% TODO: Set
|
|
|
|
\DeclarePairedDelimiter\abs{\lvert}{\rvert}
|
|
\DeclarePairedDelimiter\encoded{\langle}{\rangle}
|
|
|
|
\newcommand{\cupdot}{\mathbin{\mathaccent\cdot\cup}}
|
|
|
|
\newcommand{\transposed}[1]{#1^{\mathrm{T}}}
|
|
\DeclareMathOperator{\row}{row}
|
|
|
|
% Notation
|
|
\newcommand{\bigO}{\mathcal{O}}
|
|
\newcommand{\naturals}{\mathbb{N}}
|
|
\DeclareMathOperator{\maxnr}{maxnr}
|
|
\DeclareMathOperator{\poly}{poly}
|
|
% Modifier
|
|
\newcommand{\rel}{\mathrm{rel}}
|
|
\newcommand{\red}{\mathrm{red}}
|
|
|
|
% Optimierungsproblem
|
|
\newcommand{\domain}{\mathcal{D}}
|
|
\newcommand{\solution}{\mathcal{S}}
|
|
\newcommand{\ziel}{\mathrm{ziel}}
|
|
\DeclareMathOperator{\opt}{OPT}
|
|
|
|
% Graphen
|
|
\newcommand{\greedycol}{\algo{GreedyCol}}
|
|
\newcommand{\greedycoltwo}{\algo{GreedyCol2}}
|
|
\newcommand{\greedycoledge}{\algo{GreedyColEdge}}
|
|
\newcommand{\greedyplanarcol}{\algo{GreedyPlanarCol}}
|
|
\newcommand{\vertices}{\mathrm{V}}
|
|
\newcommand{\edges}{\mathrm{E}}
|
|
\newcommand{\degree}{\mathrm{deg}}
|
|
|
|
% Rucksackproblem
|
|
\newcommand{\rucksack}{\problem{Rucksack}}
|
|
\newcommand{\vol}{\mathrm{vol}}
|
|
\newcommand{\ark}{\algo{AR}[k]}
|
|
\newcommand{\dynrucksack}{\algo{DynRucksack}}
|
|
\newcommand{\fpasrucksack}{\algo{FPASRucksack}}
|
|
|
|
% Max-SAT
|
|
\newcommand{\maxsat}{\problem{Max-SAT}}
|
|
\DeclareMathOperator{\wahr}{wahr}
|
|
\newcommand{\true}{\textsc{True}}
|
|
\newcommand{\false}{\textsc{False}}
|
|
|
|
% Independet Set
|
|
\newcommand{\is}{\problem{IS}}
|
|
\newcommand{\greedyis}{\algo{GreedyIS}}
|
|
|
|
% Clique
|
|
\newcommand{\clique}{\problem{Clique}}
|
|
|
|
% TSP
|
|
\newcommand{\tsp}{\problem{TSP}}
|
|
\newcommand{\deltatsp}{\Delta\tsp}
|
|
\newcommand{\ch}{\mathrm{CH}}
|
|
|
|
% Hamilton
|
|
\newcommand{\hamilton}{\problem{Hamilton}}
|
|
|
|
% Set-Cover
|
|
\newcommand{\setcover}{\problem{SetCover}}
|
|
\newcommand{\cov}{\mathrm{cov}}
|
|
\newcommand{\detroundsc}{\algo{DetRoundSC}}
|
|
\newcommand{\randroundscr}{\algo{RandRoundSC}[r]}
|
|
\newcommand{\lasvegassc}{\algo{LasVegasSC}}
|
|
\newcommand{\lasvegasscr}{\lasvegassc[r]}
|
|
\newcommand{\dualpursc}{\algo{DualPurSC}}
|
|
\newcommand{\primaldualscone}{\algo{PrimalDualSC\_1}}
|
|
\newcommand{\primaldualsctwo}{\algo{PrimalDualSC\_2}}
|
|
|
|
% Vertex-Cover
|
|
\newcommand{\vertexcover}{\problem{VertexCover}}
|
|
\newcommand{\greedyvc}{\algo{GreedyVC}}
|
|
|
|
% BinPacking
|
|
\newcommand{\binpacking}{\problem{BinPacking}}
|
|
\newcommand{\nextfit}{\algo{NextFit}}
|
|
|
|
% Beweisumgebungen
|
|
\newtheorem*{satz}{Satz}
|
|
\newtheorem*{lemma}{Lemma}
|
|
\newtheorem*{zeuge}{Zeuge}
|
|
|
|
\setlist[enumerate,1]{label={\arabic*.}}
|
|
\setlist[enumerate,2]{label={\alph*)}}
|
|
|
|
\title{Approximationsalgorithmen}
|
|
\author{Marco Ammon}
|
|
\date{\today}
|
|
|
|
\makeatletter
|
|
\g@addto@macro\bfseries{\boldmath}
|
|
\makeatother
|
|
|
|
\hyphenation{Gü-te-ga-ran-tie}
|
|
|
|
\begin{document}
|
|
\maketitle
|
|
|
|
\begin{abstract}
|
|
Dies ist der Versuch einer inoffiziellen Zusammenfassung der Vorlesung \enquote{Approximationsalgorithmen} von Prof. Wanka und basiert auf seinem Buch \enquote{Approximationsalgorithmen --- Eine Einführung}.
|
|
Ich garantiere weder für Vollständigkeit noch Korrektheit des folgenden Dokuments.
|
|
\end{abstract}
|
|
|
|
\tableofcontents
|
|
\clearpage
|
|
\section{Allgemeine Definitionen}
|
|
\subsection{Kombinatorisches Optimierungsproblem $\Pi$}
|
|
\begin{align*}
|
|
\domain &= \text{Menge der Eingaben $I$}\\
|
|
\solution(I \in \domain) &= \text{Menge der zur Eingabe $I$ zulässigen Lösungen}\\
|
|
f: \solution(I) \mapsto \naturals^{\neq 0} &= \text{Bewertungs-/Kosten-/Maßfunktion}\\
|
|
\ziel \in \{\min, \max\}
|
|
\end{align*}
|
|
\begin{itemize}
|
|
\item Beschränkung auf natürliche Zahlen, weil Vergleich reeller Zahlen bislang nicht beweisbar schnell funktioniert.
|
|
\item Ausschluss der 0 für spätere Definitionen sinnvoll (lässt sich durch Modifikation von $f$ in der Regel trivial erreichen)
|
|
\end{itemize}
|
|
|
|
Gesucht ist zu $I \in \domain$ eine zulässige Lösung $\sigma_\mathrm{opt} \in \solution(I)$, sodass
|
|
\begin{equation*}
|
|
\opt(I) = f(\sigma_\mathrm{opt}) = \ziel\{f(\sigma) \mid \sigma \in \solution(I) \}
|
|
\end{equation*}
|
|
|
|
\subsubsection{Das Rucksackproblem \rucksack}
|
|
\begin{align*}
|
|
\domain &= \{\encoded*{ W, \vol, p, B} \mid W = \{1, \dots, n\}, \vol: W \mapsto \naturals, p: W\mapsto \naturals, B \in \naturals,\\
|
|
&\qquad \forall w \in W: vol(w) \le B\}\\
|
|
\solution(\encoded*{ W, \vol, p, B}) &= \{ A \subseteq W \mid \sum_{w\in A}\vol(w) \le B\}\\
|
|
f(A) &= \sum_{w\in A} p_w\\
|
|
\ziel &= \max
|
|
\end{align*}
|
|
Die Restriktion der verfügbaren Waren auf solche, die in den leeren Rucksack passen, hilft gegen das künstliche Aufblähen der Eingabe.
|
|
|
|
\subsubsection{Das Knotenfärbungsproblem \problem{Col}}
|
|
\begin{align*}
|
|
\domain &= \{\encoded*{ G} \mid G = (V, E)\,\text{ein ungerichteter Graph mit mindestens einer Kante}\}\\
|
|
\solution(\encoded*{ G }) &= \{ c_\vertices \mid c_\vertices\, \text{ist eine Knotenfärbung von}\, G\}\\
|
|
f(c_\vertices) &= \abs*{c_\vertices(V)}\\
|
|
\ziel &= \min
|
|
\end{align*}
|
|
|
|
Die Größe der kleinsten möglichen Knotenfärbung ist die chromatische Zahl $\chi(G)$.
|
|
|
|
\subsubsection{Das Kantenfärbungsproblem \problem{EdgeCol}}
|
|
\begin{align*}
|
|
\domain &= \{\encoded*{ G} \mid G = (V, E)\,\text{ein ungerichteter Graph mit mindestens einer Kante}\}\\
|
|
\solution(\encoded*{ G }) &= \{ c_\edges \mid c_\edges\, \text{ist eine Kantenfärbung von}\, G\}\\
|
|
f(c_\edges) &= \abs*{c_\edges(E)}\\
|
|
\ziel &= \min
|
|
\end{align*}
|
|
Die Größe der kleinsten möglichen Kantenfärbung ist der chromatische Index $\chi'(G)$.
|
|
|
|
\subsubsection{Das Traveling-Salesperson-Problem \tsp}
|
|
\begin{align*}
|
|
\domain &= \{\encoded*{ K_n, c} \mid K_n\, \text{vollständiger Graph auf $n$ Knoten}, c: E \mapsto \naturals,\}\\
|
|
\solution(\encoded*{ K_n, c }) &= \{ C \mid C = (v_{i_1}, v_{i_2}, \dots, v_{i_n}, v_{i_i})\,\text{ist ein Hamiltonkreis}\}\\
|
|
f(C) &= c(v_{i_n}, v_{i_1}) + \sum_{j=1}^{n-1} c(v_{i_j}, v_{i_{j+1}})\\
|
|
\ziel &= \min
|
|
\end{align*}
|
|
|
|
\subsubsection{Das metrische Traveling-Salesperson-Problem $\deltatsp$}
|
|
\begin{align*}
|
|
\domain &= \{\encoded*{ K_n, c} \mid K_n\, \text{vollständiger Graph auf $n$ Knoten}, c: E \mapsto \naturals,\\
|
|
&\forall u, v, w \in V: \underbrace{c(u,v) \le c(u,w) + c(w, v)}_\text{Dreiecksungleichung}\}\\
|
|
\solution(\encoded*{ K_n, c }) &= \{ C \mid C = (v_{i_1}, v_{i_2}, \dots, v_{i_n}, v_{i_i})\,\text{ist ein Hamiltonkreis}\}\\
|
|
f(C) &= c(v_{i_n}, v_{i_1}) + \sum_{j=1}^{n-1} c(v_{i_j}, v_{i_{j+1}})\\
|
|
\ziel &= \min
|
|
\end{align*}
|
|
|
|
\subsubsection{Das Problem der Unabhängigen Knotenmengen \is}
|
|
\begin{align*}
|
|
\domain &= \{\encoded*{ G} \mid G = (V, E)\,\text{ein Graph}\}\\
|
|
\solution(\encoded*{ G }) &= \{ U \mid U \subseteq V, \forall u, v \in U: (u, v) \notin E\}\\
|
|
f(U) &= \abs*{U}\\
|
|
\ziel &= \max
|
|
\end{align*}
|
|
|
|
\subsubsection{Das Cliquenproblem \clique}
|
|
\begin{align*}
|
|
\domain &= \{\encoded*{ G} \mid G = (V, E)\,\text{ein Graph}\}\\
|
|
\solution(\encoded*{ G }) &= \{ U \mid U \subseteq V, \forall u, v \in U: (u, v) \in E\}\\
|
|
f(U) &= \abs*{U}\\
|
|
\ziel &= \max
|
|
\end{align*}
|
|
|
|
\subsubsection{Das Erfüllbarkeitsproblem \maxsat}
|
|
Sei $V = \{x_1, \dots, x_n\}$ die Menge der Variablen.
|
|
Als Literal $l$ bezeichnet man eine Variable $x_i \in V$ oder ihre Negation $\overline{x_i}$.
|
|
Eine Oder-Klausel (kurz Klausel) $C = l_1 \lor \dots \lor l_k$ ist eine Oder-Verknüpfung von Literalen.
|
|
|
|
Eine Boolesche $(n, m)$-Formel $\Phi = C_1 \land \dots \land C_m$ in konjunktiver Normalform ist eine Und-Verknüpfung von Oder-Klauseln aus $n$ Variablen aus $V$.
|
|
|
|
\begin{align*}
|
|
\domain &= \{\encoded*{ \Phi} \mid \Phi\,\text{eine boolesche $(n,m)$-Formel in KNF}\}\\
|
|
\solution(\encoded*{ \Phi }) &= \{ b \mid b: V \mapsto \{\false{}, \true{}\}\}\\
|
|
\wahr(\Phi, b) &= \abs*{\{j \mid C_j \in \Phi, b(C_j) = \true{}\}}\\
|
|
\ziel &= \max
|
|
\end{align*}
|
|
|
|
\subsubsection{Das Mengenüberdeckungsproblem \setcover}
|
|
\begin{align*}
|
|
\domain &= \{S \mid S = \{S_1, \dots, S_m\}, V = \cup_{i=1}^{m}S_i = \{u_1, \dots, u_n\}\}\\
|
|
\solution(S) &= \{ S_\cov \mid S_\cov = \{S_{i_1}, \dots, S_{i_l}\}, V = \cup_{j=1}^{l} S_{i_j}\}\\
|
|
f(S_\cov) &= \abs*{S_\cov}\\
|
|
\ziel &= \min
|
|
\end{align*}
|
|
|
|
\subsubsection{Das Knotenüberdeckungsproblem \vertexcover}
|
|
Spezialfall von \setcover:
|
|
\begin{align*}
|
|
\domain &= \{\encoded*{G} \mid \text{$G = (E, V)$ ein Graph}\}\\
|
|
\solution(\encoded*{G}) &= \{ C \mid C \subset V, \forall e \in E: e \cap C \neq \emptyset\}\\
|
|
f(C) &= \abs*{C}\\
|
|
\ziel &= \min
|
|
\end{align*}
|
|
|
|
\subsubsection{Das Behälterproblem \binpacking}
|
|
\begin{align*}
|
|
\domain &= \{M \mid M = \left\{a_1,\dots, a_n\right\}, 1 \ge s(a_1)\ge\dots\ge s(a_n)\ge 0\}\\
|
|
\solution(M) &= \{ B \mid B = \{B_1, \dots,B_k\}, \cupdot_{B_i\in B} B_i = M, \forall B_i \in B: s(B_i)\le 1\}\\
|
|
f(M) &= \abs*{M}\\
|
|
\ziel &= \min
|
|
\end{align*}
|
|
|
|
\subsection{$t(n)$-Zeit-Approximationsalgorithmus}
|
|
Berechnet ein Algorithmus $A$ in Zeit $t(\abs*{I})$ eine Ausgabe $\sigma_I^A \in \solution(I)$ für Eingabe $I \in \domain$, wird er als $t(n)$-Zeit-Approximationsalgorithmus bezeichnet. Es gilt die Schreibweise $A(I) = f(\sigma_I^A)$.
|
|
|
|
\subsection{Pseudo-polynomieller Algorithmus}
|
|
Sei $\Pi$ ein kombinatorisches Optimierungsproblem, sodass in allen Instanzen $I$ alle vorkommenden Zahlen natürliche Zahlen sind. Sei $\maxnr(I)$ die größte in $I$ vorkommende Zahl. Ein Algorithmus wird als pseudo-polynomiell bezeichnet, falls es ein Polynom $\poly(\cdot, \cdot)$ gibt, sodass für alle Instanzen $I$ seine Laufzeit $\poly(\abs*{I}, \maxnr(I))$ ist.
|
|
|
|
Kann also das Problem so eingeschränkt werden, dass für alle Instanzen $I$ die größte vorkommende Zahl durch ein Polynom der Eingabelänge begrenzt wird, also $\maxnr(I) \le q(\abs*{I})$ mit Polynom $q$ gilt, so ist auch die Laufzeit des Algorithmus polynomiell in der Eingabegröße.
|
|
|
|
\subsection{Starke NP-Vollständigkeit}
|
|
Ein NP-vollständiges Entscheidungsproblem $L$ wird als stark NP-vollständig bezeichnet, wenn es ein Polynom $q$ gibt, sodass $L_q = \{x \mid x \in L, \maxnr(x) \le q(\abs*{x})\}$ NP-vollständig ist. Gibt es kein solches Polynom, gilt $L$ als schwach NP-vollständig.
|
|
|
|
Eine äquivalente Charakterisierung ist: Das NP-vollständige Entscheidungsproblem $L$ ist stark vollständig, falls es keinen pseudo-polynomiellen Algorithmus für $L$ gibt (unter der Annahme $P \neq NP$).
|
|
|
|
\begin{itemize}
|
|
\item \hamilton{} und \problem{Clique} sind stark NP-vollständig, da bei ihnen das Polynom $q(n) = n$ ausreicht.
|
|
\item \tsp{} ist stark NP-vollständig, da sogar das $\deltatsp$ mit Gewichten 1 und 2 NP-vollständig ist.
|
|
\item \rucksack{} ist schwach NP-vollständig, weil es einen pseudo-polynomiellen Algorithmus für die Optimierungsvariante gibt, der auch für das Entscheidungsproblem verwendet werden kann.
|
|
\end{itemize}
|
|
|
|
\subsection{Planarer Graph}
|
|
Ein planarer Graph kann so auf einer Kugel dargestellt werden, dass sich keine seiner Kanten kreuzen.
|
|
\begin{satz}[Eulerscher Polyedersatz]
|
|
Für einen beliebigen zusammenhängenden planaren Graph mit $n$ Knoten, $m$ Kanten und $f$ Facetten gilt:
|
|
\begin{equation*}
|
|
n - m + f = 2
|
|
\end{equation*}
|
|
\end{satz}
|
|
\begin{proof}[Beweis durch Induktion]
|
|
\begin{itemize}
|
|
\item Induktionsanfang: Für einen Knoten gilt $1 - 0 + 1 =2$.
|
|
\item Induktionsschritt: Fallunterscheidung:\begin{itemize}
|
|
\item Hinzufügen einer Ecke: Die Ecke wird mit einer bestehenden Kante verbunden (zusammenhängender Graph), also gilt $n + 1 - (m + 1) + f = n - m +f = 2$.
|
|
\item Hinzufügen einer Kante: Eine bestehende Fläche wird in zwei geteilt, also gilt $n - (m + 1) + f + 1 = n - m + f = 2$.
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{proof}
|
|
|
|
\begin{satz}
|
|
Für einen planaren Graph gilt
|
|
\begin{equation*}
|
|
m \le 3\cdot n - 6
|
|
\end{equation*}
|
|
\end{satz}
|
|
|
|
\begin{satz}
|
|
Ein planarer Graph enthält mindestens einen Knoten mit Grad 5 oder weniger.
|
|
\end{satz}
|
|
|
|
\section{Absolute Gütegarantie}
|
|
\subsection{Definition}
|
|
\begin{enumerate}
|
|
\item $A$ hat bei Eingabe $I$ absolute Güte von
|
|
\begin{equation*}
|
|
\kappa_A(I) = \abs*{A(I) - \opt(I)}
|
|
\end{equation*}
|
|
\item Die absolute Worst-Case-Güte von $A$ ist die Funktion
|
|
\begin{equation*}
|
|
\kappa_A^{\mathrm{wc}}(n) = \max\{\kappa_A(I) \mid I \in \domain, \abs*{I} \le n\}
|
|
\end{equation*}
|
|
\item $A$ garantiert eine absolute Güte von $\kappa_A: \naturals \mapsto \naturals$, falls für alle $n \in \naturals$ gilt:
|
|
\begin{equation*}
|
|
\kappa_A^{\mathrm{wc}}(n) \le \kappa_A(n)
|
|
\end{equation*}
|
|
\item $A$ hat eine absolute Abweichung von $\kappa'_A: \naturals \mapsto \naturals$, falls für unendlich viele $n$ gilt
|
|
\begin{equation*}
|
|
\kappa'_A(n) \le \kappa_A^{wc}(n)
|
|
\end{equation*}
|
|
Eine unendlich große Menge $\domain' \subseteq \domain$ heißt $\kappa'_A(n)$-Zeugenmenge gegen $A$, wenn für alle $I \in \domain'$ gilt:
|
|
\begin{equation*}
|
|
\kappa_A(I) \ge \kappa'_A(\abs*{I})
|
|
\end{equation*}
|
|
\end{enumerate}
|
|
|
|
\subsection{Unmöglichkeitsergebnis für das Rucksackproblem}
|
|
\begin{satz}
|
|
Falls $P \neq NP$, dann gibt es keine Konstante $n\in \naturals$, sodass es einen polynomiellen Approximationsalgorithmus $A$ für \rucksack{} gibt mit
|
|
\begin{equation*}
|
|
\abs*{A(I) - \opt(I)} \le k
|
|
\end{equation*}
|
|
\end{satz}
|
|
\begin{proof}[Widerspruchsbeweis]
|
|
Unter der Annahme, dass $A$ und $k$ existieren, kann \rucksack{} in Polynomzeit exakt gelöst werden, was $P = NP$ zur Folge hat:
|
|
|
|
Konstruiere aus einer Instanz $I = \encoded*{ W, \vol, p, B }$ eine neue Probleminstanz $I' = \encoded*{W, \vol, p', B}$ mit $p'(w) = (k + 1) \cdot p(w)$.
|
|
Eine zulässige Lösung $\sigma$ für $I$ ist auch eine zulässige Lösung für $I'$. Gleiches gilt aufgrund der Monotonie der Multiplikation auch für optimale Lösungen.
|
|
Durch die Multiplikation aller Preise mit $k + 1$ beträgt die \enquote{Lücke} zwischen den optimalen und der ersten nicht-optimalen Lösung für $I'$ mindestens $k + 1$.
|
|
|
|
Da $A$ eine absolute Güte von $k$ garantiert und in Polynomzeit terminiert, kann es nur eine optimale Lösung für $I'$, welche auch optimal für $I$ ist, zurückgeben. Damit ist das $NP$-vollständige \rucksack{} in Polynomzeit exakt lösbar.
|
|
\end{proof}
|
|
|
|
Die hierbei verwendete Vorgehensweise einer Selbstreduktion sowie das \enquote{Aufblasen} des Problems (\enquote{Scaling}, \enquote{Gap Amplification}) lässt sich auch auf viele andere Probleme wie etwa \setcover{} anwenden. Folglich kann eine konstante Gütegarantie nur für vergleichsweise wenig Probleme erreicht werden.
|
|
|
|
\section{Relative Gütegarantie}
|
|
\subsection{Definition}
|
|
\begin{enumerate}
|
|
\item $A$ hat bei Eingabe $I$ eine relative Güte von
|
|
\begin{equation*}
|
|
\rho_A(I) = \max\left\{\frac{A(I)}{\opt(I)}, \frac{\opt(I)}{A(I)}\right\} \ge 1
|
|
\end{equation*}
|
|
\item Die relative Worst-Case-Güte von $A$ ist die Funktion
|
|
\begin{equation*}
|
|
\rho_A^\mathrm{wc}(n) = \max\left\{\rho_A(I)\mid I \in \domain, \abs*{I}\le n\right\}
|
|
\end{equation*}
|
|
\item $A$ garantiert eine relative Güte von $\rho_A : \naturals \mapsto \naturals$, falls für alle $n \in \naturals$ gilt
|
|
\begin{equation*}
|
|
\rho_A^{\mathrm{wc}}(n) \le \rho_A(n)
|
|
\end{equation*}
|
|
\item $A$ macht für die Eingabe $I \in \domain$ einen relativen Fehler von
|
|
\begin{equation*}
|
|
\varepsilon_A(I) = \frac{\abs*{A(I) - \opt(I)}}{\opt(I)} = \abs*{\frac{A(I)}{\opt(I)} - 1}
|
|
\end{equation*}
|
|
\item $A$ garantiert einen relativen Fehler von $\varepsilon_A(n)$, falls für alle $\{I\mid I \in \domain, \abs*{I}\le n\}$ gilt
|
|
\begin{equation*}
|
|
\varepsilon_A(I) \le \varepsilon_A(n)
|
|
\end{equation*}
|
|
\item $A$ hat eine relative Abweichung von $\rho'_A : \naturals \mapsto \naturals$, falls für unendlich viele $n$ gilt
|
|
\begin{equation*}
|
|
\rho_A^\mathrm{wc}(n) \ge \rho'_A(n)
|
|
\end{equation*}
|
|
|
|
Eine unendlich große Menge $\domain' \subseteq \domain$ heißt $\rho'_A(n)$-Zeugenmenge gegen $A$, wenn für alle $I \in \domain'$ gilt
|
|
\begin{equation*}
|
|
\rho_A(I) \ge \rho'_A(\abs*{I})
|
|
\end{equation*}
|
|
\end{enumerate}
|
|
|
|
Es folgen daraus direkt, dass
|
|
\begin{enumerate}
|
|
\item bei einem Minimierungsproblem $1 + \varepsilon_A(n) = \rho_A(n)$ ist.
|
|
\item bei einem Maximierungsproblem $1 - \varepsilon_A(n) = \frac{1}{\rho_A(n)}$ ist.
|
|
\item für alle Probleme $\varepsilon_A(n) \le \rho_A(n) - 1$ ist.
|
|
\end{enumerate}
|
|
|
|
Weiter lassen sich damit obere bzw. untere Schranken der Optimallösung aus einer approximierten Lösung angeben. Es folgt, dass
|
|
\begin{enumerate}
|
|
\item bei einem Minimierungsproblem gilt
|
|
\begin{equation*}
|
|
\frac{1}{\rho_A(\abs*{I})} \cdot A(I) \le \opt(I) \le A(I) \le \rho_A(\abs*{I})\cdot \opt(I)
|
|
\end{equation*}
|
|
\item bei einem Maximierungsproblem gilt
|
|
\begin{equation*}
|
|
\frac{1}{\rho_A(\abs*{I})} \cdot \opt(I) \le A(I) \le \opt(I) \le \rho_A(\abs*{I}) \cdot A(I)
|
|
\end{equation*}
|
|
\item bei beiden Problemtypen mit der Beziehung
|
|
\begin{equation*}
|
|
\abs*{A(I) - \opt(I)} \le \varepsilon_A(\abs*{I}) \cdot \opt(I)
|
|
\end{equation*}
|
|
gilt
|
|
\begin{equation*}
|
|
(1 - \varepsilon_A(\abs*{I})) \cdot \opt(I) \le A(I) \le (1 + \varepsilon_A(\abs*{I})) \cdot \opt(I)
|
|
\end{equation*}
|
|
\end{enumerate}
|
|
|
|
\subsection{Unmöglichkeitsergebnis für das allgemeine (volle) \tsp}
|
|
\begin{satz}
|
|
Wenn es einen polynomiellen Approximationsalgorithmus $A$ mit konstanter relativer Gütegarantie $r$ für das volle \tsp{} gibt, dann gilt $P = NP$.
|
|
\end{satz}
|
|
\begin{proof}[Beweis durch Reduktion]
|
|
Durch Benutzung von $A$ mit beliebiger konstanter relativer Gütegarantie $r \in \naturals$ kann \hamilton{} auf das volle \tsp{} reduziert werden. Es wird also $\hamilton{} \le_\mathrm{p} \tsp[r]$ für alle $r$ gezeigt:
|
|
|
|
Sei der Graph $G = (V, E)$ mit $n = \abs*{V}$, gegeben. Dazu wird nun passend eine Probleminstanz $I_G = \encoded*{ K_n, c}$ für \tsp{} erzeugt. $c$ wird wie folgt konstruiert:
|
|
\begin{equation*}
|
|
c(u,v) = \begin{cases*}
|
|
1 & falls $\{u, v\} \in E$ (\enquote{kurze} Kante)\\
|
|
\left(r - 1\right)\cdot n + 2 & sonst (\enquote{lange} Kante)
|
|
\end{cases*}
|
|
\end{equation*}
|
|
$I_G$ kann in Polynomzeit aus $G$ berechnet werden. Es gilt weiter:
|
|
\begin{itemize}
|
|
\item $G \in \hamilton{} \Rightarrow$ kürzeste Rundreise in $I_G$ hat die Länge $n$
|
|
\item $G \notin \hamilton{} \Rightarrow$ kürzeste Rundreise in $I_G$ nimmt mindestens eine der langen Kanten und hat damit eine Länge von mindestens
|
|
\begin{equation*}
|
|
(r - 1) \cdot n + 2 + n - 1 = r \cdot n +1 > r \cdot n
|
|
\end{equation*}
|
|
\item $I_G$ besitzt keine zulässige Lösung $\sigma$ mit $n + 1\le c(\sigma) \le r \cdot n$.
|
|
\end{itemize}
|
|
|
|
|
|
Durch den folgenden Algorithmus kann also \hamilton{} entschieden werden:
|
|
\begin{algorithmic}[1]
|
|
\State konstruiere $I_G$
|
|
\State approximiere mit $A$ eine kürzeste Rundreise $A(I_G)$
|
|
\If{$A(I_G) > r \cdot \abs*{V}$}
|
|
\State \Return $G \notin \hamilton{}$
|
|
\Else
|
|
\State \Return $G \in \hamilton{}$
|
|
\EndIf
|
|
\end{algorithmic}
|
|
\end{proof}
|
|
|
|
Der Ansatz der Konstruktion von Probleminstanzen anderer $NP$-schwerer Probleme und der anschließenden Verwendung eines Scaling-Arguments kann auch für weitere Probleme verwendet werden. Ebenfalls können damit bestimmte Bereiche für mögliche konstante relative Gütegarantien ausgeschlossen werden, etwa $\rho < \frac{3}{2}$ bei \problem{BinPacking} (in Verbindung mit \problem{Partition}).
|
|
|
|
\section{Approximationsschemata}
|
|
Während die Ergebnisse von Approximationsalgorithmen mit absoluter oder relativer Gütegarantie nur durch eine Modifikation oder Wechsel des Algorithmus verbessert werden können, ist es manchmal gewünscht, im Gegenzug für eine verlängerte Laufzeit eine bessere Güte zu erreichen. Dafür sind sogenannte Approximationsschemata geeignet.
|
|
|
|
\subsection{Definition}
|
|
Sei $\Pi$ ein Optimierungsproblem und $A$ ein Approximationsalgorithmus für $\Pi$, der eine Probleminstanz $I$ von $\Pi$ und ein $0 < \varepsilon < 1$ bekommt.
|
|
\begin{enumerate}
|
|
\item $A$ ist ein polynomielles Approximationsschema (PAS) für $\Pi$, wenn $A$ zu jedem $I$ und für jedes $\varepsilon$ in Zeit $\bigO(\poly(\abs*{I}))$ eine zulässige Lösung zu $I$ mit relativem Fehler $\varepsilon_A(I, \varepsilon) \le \varepsilon$ berechnet.
|
|
\item $A$ ist ein streng polynomielles Approximationsschema (FPAS), wenn $A$ ein PAS mit Laufzeit $\bigO\left(poly\left(\abs*{I}, \frac{1}{\varepsilon}\right)\right)$ ist.
|
|
\end{enumerate}
|
|
|
|
\begin{satz}[Umwandlung eines (F)PAS in einen exakten Algorithmus]
|
|
Sei $A$ ein (F)PAS und zu jeder Eingabe $I$ $Z(I)$ eine obere Schranke. Sei $\varepsilon^* = \frac{1}{Z(I) + 1}$, dann ist $A(I, \varepsilon^*) = \opt(I)$. Sofern $A$ ein FPAS ist, liegt die Laufzeit in $\bigO(\poly(\abs*{I}, Z(I)))$.
|
|
\end{satz}
|
|
\begin{proof}
|
|
Starte $A$ mit Eingabe $I$ und $\varepsilon^*$. Es wird eine zulässige Lösung zu $I$ gefunden, für ihren relativen Fehler gilt
|
|
\begin{equation*}
|
|
\varepsilon_a(I, \varepsilon^*) = \frac{\abs*{\opt(I) - A(I, \varepsilon^*)}}{\opt(I)} \le \varepsilon^*
|
|
\end{equation*}
|
|
Weil $\opt(I) \le Z(I)$ beschränkt ist, folgt für die Abweichung
|
|
\begin{equation*}
|
|
\abs*{\opt(I) - A(I, \varepsilon^*)} \le \varepsilon^* \cdot \opt(I) = \frac{\opt(I)}{Z(I) + 1} < 1
|
|
\end{equation*}
|
|
Da die Werte zulässiger Lösungen immer ganzzahlig sind, folgt $\abs*{\opt(I) - A(I, \varepsilon^*)} = 0$, damit also die Optimalität von $A(I, \varepsilon^*)$.
|
|
\end{proof}
|
|
|
|
\subsection{Unmöglichkeitsergebnisse für Approximationschemata}
|
|
\begin{satz}
|
|
Sei $\Pi$ ein Optimierungsproblem. Wenn es ein Polynom $q(\cdot, \cdot)$ gibt, sodass $\forall I \in \domain: \opt(I) \le q(\abs*{I}, \maxnr(I))$ gilt, dann folgt aus der Existenz eines FPAS für $\Pi$, dass ein pseudo-polynomieller exakter Algorithmus für $\Pi$ existiert.
|
|
\end{satz}
|
|
\begin{satz}
|
|
Wenn es für eine Optimierungsvariante eines stark NP-vollständigen Problems ein FPAS gibt, dann folgt $P = NP$.
|
|
\end{satz}
|
|
|
|
\section{\greedyis{} für \is}
|
|
\begin{algorithmic}[1]
|
|
\State $U = \emptyset, t = 0, V^{(0)} = V$
|
|
\While{$V^{(t)} \neq \emptyset$}
|
|
\State $G^{(t)} =\, \text{der durch}\,V^{(t)}\,\text{induzierte Graph}$
|
|
\State $u_l =$ ein Knoten mit minimalem Grad in $G^{(t)}$
|
|
\State $V^{(t+1)} = V^{(t)} - \left(\{u_l\} \cup \Gamma_{G^{(t)}}(u_l)\right)$
|
|
\State $U = U \cup \{u_l\}$
|
|
\State $t = t + 1$
|
|
\EndWhile
|
|
\State \Return $U$
|
|
\end{algorithmic}
|
|
|
|
\begin{satz}
|
|
Sei $G$ ein knoten-$k$-färbbarer Graph, dann ist
|
|
\begin{equation*}
|
|
\greedyis(G) \ge \left\lceil \log_k\left(\frac{\abs*{V}}{3}\right) \right\rceil
|
|
\end{equation*}
|
|
\end{satz}
|
|
|
|
\begin{proof}
|
|
Mit dem folgenden Hilfslemma kann eine Beziehung zwischen der Anzahl der notwendigen Farben und dem minimalen Grad des Graphs hergestellt werden.
|
|
\begin{lemma}
|
|
Sei $G$ ein knoten-$k$-färbbarer Graph, dann gilt:
|
|
\begin{equation*}
|
|
\exists u \in V: \degree_G(u) \le \left\lfloor \left(1 - \frac{1}{k}\right) \cdot \abs*{V}\right\rfloor
|
|
\end{equation*}
|
|
\end{lemma}
|
|
\begin{proof}
|
|
Da $G$ mit $k$ Farben gefärbt ist, gibt es $k$ Mengen $U_i$ an Knoten, die jeweils mit der gleichen Farbe $i$ gefärbt sind.
|
|
Es muss nach einem Durchschnitsargument eine Menge $U_i$ mit $\abs*{U_i} \geq \left\lceil \frac{1}{k}\cdot \abs*{V}\right\rceil$ geben. Jeder der Knoten $u$ in $U_i$ kann maximal mit allen Knoten aus $V \setminus U_i$ verbunden sein. Es folgt also
|
|
\begin{equation*}
|
|
\degree_G(u) \leq \abs*{V} - \abs*{U_i} \le \abs*{V} - \left\lceil \frac{1}{k}\cdot \abs*{V}\right\rceil = \left\lfloor \left(1 - \frac{1}{k}\right) \cdot \abs*{V}\right\rfloor
|
|
\end{equation*}
|
|
\end{proof}
|
|
Zur Vereinfachung gelte $n = \abs*{V}$ und $n_t = \abs*{V^{(t)}}$. Es kann $k \ge 2$ angenommen werden.
|
|
Mit dem Hilfslemma ergibt sich für die Anzahl der Knoten folgende Rekursion:
|
|
\begin{align*}
|
|
n_0 &= n\\
|
|
n_{t+1} &\ge n_t - \left\lfloor \left(1 - \frac{1}{k}\right) \cdot n_t\right\rfloor -1 \ge \frac{n_t}{k} - 1
|
|
\end{align*}
|
|
Sie kann zur Ungleichung
|
|
\begin{equation*}
|
|
n_t \ge \frac{n}{k^t} - \underbrace{\frac{k}{k - 1} \cdot \left(1 - \frac{1}{k^t}\right)}_{\le 2\, \text{für $k\ge 2$}} \ge \frac{n}{k^t} - 2
|
|
\end{equation*}
|
|
aufgelöst werden. Solange $n_t \ge 1$ gilt, wird ein neuer Knoten nach $U$ gelegt. Durch Umformen obiger Ungleichung lässt sich dies für $t \ge \log_k\left(\frac{n}{3}\right)$ garantieren. Es folgt also $\abs*{U} \ge \left\lceil\log_k\left(\frac{n}{3}\right)\right\rceil$.
|
|
\end{proof}
|
|
|
|
\section{Knotenfärbungsalgorithmen}
|
|
\subsection{\greedycol}
|
|
\begin{algorithmic}[1]
|
|
\ForAll{$u_i \in V$}
|
|
\State $c_\vertices(u_i) = \infty$
|
|
\EndFor
|
|
\ForAll{$i \in \{1,\dots, \abs*{V}\}$}
|
|
\State $c_\vertices(u_i) = \min\{\naturals\setminus\{c_\vertices(\Gamma(u_i))\}\}$
|
|
\EndFor
|
|
\State\Return $c_\vertices$
|
|
\end{algorithmic}
|
|
|
|
\begin{satz}
|
|
\greedycol{} berechnet in Zeit $\bigO(\abs*{V} + \abs*{E})$ eine Knotenfärbung aus höchstens $\Delta(G) + 1$ Farben.
|
|
\end{satz}
|
|
\begin{proof}
|
|
Da ein Knoten $u$ maximal $\Delta(G)$ viele Nachbarn haben kann, muss in $[1,\dots,\Delta(G)+1]$ noch mindestens eine Farbe frei sein.
|
|
\end{proof}
|
|
|
|
\begin{satz}
|
|
\greedycol{} garantiert eine absolute Güte von
|
|
\begin{equation*}
|
|
\kappa_\greedycol(G) = \greedycol(G) - \opt(G) \le \Delta(G) + 1 - 2 = \Delta(G) - 1
|
|
\end{equation*}
|
|
, weil die untere Schranke $\opt(G)\ge 2$ für Graphen mit $\abs*{V} \ge 2$ gilt.
|
|
\end{satz}
|
|
|
|
\begin{satz}
|
|
\greedycol{} liefert eine Knotenfärbung aus höchstens $\left\lceil \sqrt{2\cdot \abs*{E}}\right\rceil$.
|
|
\end{satz}
|
|
|
|
\begin{zeuge}
|
|
$\Delta(G) - 1$-Zeuge gegen \greedycol: TODO (Abbildung 2.1)
|
|
\end{zeuge}
|
|
|
|
\subsection{\greedyplanarcol}
|
|
\begin{algorithmic}[1]
|
|
\If{$G$ ist knoten-2-färbbar}\Comment{$\in P$}
|
|
\State \Return berechne Knoten-2-Färbung \Comment{$\in P$}
|
|
\EndIf
|
|
\State wähle Knoten $u$ mit höchstem Grad $\Gamma(u)$ \Comment{$\Gamma(u) \le 5$}
|
|
\State entferne $u$ und seine $\Gamma(u) \le 5$ Kanten aus $G$
|
|
\ForAll{übrige Teilgraphen $G_i$} \Comment{$1 \le i \le \Gamma(u)$}
|
|
\State $c_\vertices = c_\vertices \cup \greedyplanarcol(G_i)$
|
|
\EndFor
|
|
\State $c_\vertices(u) =$ kleinste der freien Farbe aus $\{1, \dots, \gamma(u) + 1\}$
|
|
\State \Return $c_\vertices$
|
|
\end{algorithmic}
|
|
\begin{satz}
|
|
\greedyplanarcol{} hat eine maximale Gütegarantie von $\kappa_\greedyplanarcol(n) = 3$.
|
|
\end{satz}
|
|
\begin{proof}
|
|
Ist $G$ knoten-2-färbbar, so liefert \greedyplanarcol{} auch eine Knoten-2-Färbung zurück. Es gilt also im Folgenden $\opt(G) \ge 3$ und damit
|
|
\begin{equation*}
|
|
\kappa_\greedyplanarcol(n) = \abs*{\greedyplanarcol(G) - \opt(G)} \le \abs*{6 - 3} = 3
|
|
\end{equation*}
|
|
\end{proof}
|
|
|
|
\subsection{\greedycoltwo}
|
|
\begin{algorithmic}[1]
|
|
\State $t = 1, V^{(1)} = V$
|
|
\While{$V^{(t)} \neq \emptyset$}
|
|
\State $G^{(t)} =$ der durch $V^{(t)}$ induzierte Graph
|
|
\State $U_t = \greedyis(G^{(t)})$
|
|
\State färbe alle Knoten in $U_t$ mit Farbe $t$
|
|
\State $V^{(t+1)} = V^{(t)} - U_t$
|
|
\State $t = t + 1$
|
|
\EndWhile
|
|
\State \Return berechnete Färbung
|
|
\end{algorithmic}
|
|
|
|
\begin{satz}
|
|
Für einen knoten-$k$-färbbaren Graph $G = (V, E)$ mit $n = \abs*{V}$ gibt \greedycoltwo{} eine Färbung mit höchstens $\frac{3n}{\log_k \left(\frac{n}{16}\right)}$. Die relative Gütegarantie liegt als in $\bigO\left(\frac{n}{\log n}\right)$.
|
|
\end{satz}
|
|
\begin{proof}
|
|
Zur Vereinfachung bezeichne $n_t = \abs*{V^{(t)}}$. Aus der Analyse von \greedyis{} folgt $\abs*{U_t} \ge \log_k\left(\frac{n_t}{3}\right)$. Es ergibt sich die Rekursion
|
|
\begin{align*}
|
|
n_1 &= n\\
|
|
n_{t + 1} &\le n_t - \log_k\left(\frac{n_t}{3}\right)
|
|
\end{align*}
|
|
|
|
Nun wird bestimmt, für welches $t$ $n_t < 1$ eintritt, denn dann bricht der Algorithmus ab.
|
|
Behelfsmäßig sei $n_t \ge \frac{n}{\log_k\left(\frac{n}{16}\right)}$. Mit der Beziehung $\frac{n}{\log_k n} \ge \frac{3}{4}\cdot \sqrt{n}$ ergibt sich
|
|
\begin{equation*}
|
|
\log_k\left(\frac{n_t}{3}\right) \ge \log_k \left(\frac{n}{3 \cdot \log_k n}\right) \ge \log_k\left(\sqrt{\frac{n}{16}}\right) = \frac{1}{2} \cdot \log_k\left(\frac{n}{16}\right)
|
|
\end{equation*}
|
|
Solange $n_t \ge \frac{n}{\log_k\left(\frac{n}{16}\right)}$ also gilt, werden pro Runde mindestens $\frac{1}{2} \cdot \log_k\left(\frac{n}{16}\right)$ Knoten pro Runde gefärbt. Nach höchstens $t \le \frac{2n}{\log_k\left(\frac{n}{16}\right)}$ gilt die Ungleichung nicht mehr. Färbt man jetzt alle verbliebenen Knoten mit jeweils einer eigenen Farbe, werden insgesamt maximal $ \frac{n}{\log_k\left(\frac{n}{16}\right)} + t \leq \frac{3n}{\log_k\left(\frac{n}{16}\right)}$ vergeben.
|
|
|
|
Mit $k = \chi_G = \opt(G)$ ergibt sich für die relative Gütegarantie:
|
|
\begin{equation*}
|
|
\frac{\algo{GreedyCol2(G)}}{\opt(G)} \le \frac{\frac{3n}{\log_k\left(\frac{n}{16}\right)}}{k} = \bigO\left(\frac{n}{\log n}\right)
|
|
\end{equation*}
|
|
\end{proof}
|
|
|
|
\section{Kantenfärbungsalgorithmen}
|
|
\subsection{\greedycoledge}
|
|
\begin{algorithmic}[1]
|
|
\ForAll{$e_i \in E$}
|
|
\State $c_\edges(e_i) = \infty$
|
|
\EndFor
|
|
\ForAll{$\{u, v\} \in E$}
|
|
\State $c_\edges\lparen \{u, v\}\rparen \gets \min \lparen \mathbb{N} \setminus \left \lparen \lbrace c_\edges\lparen \lbrace u, w\rbrace\rparen \vert \lbrace u, w\rbrace \in E\rbrace \cup \lbrace c_\edges\lparen \lbrace v, w\rbrace\rparen \vert \lbrace v, w\rbrace \in E\rbrace \right\rparen \rparen$ \Comment Kante bekommt kleinste freie Farbe
|
|
\EndFor
|
|
\State\Return $c_\edges$
|
|
\end{algorithmic}
|
|
\begin{satz}
|
|
\greedycoledge{} liefert eine Kantenfärbung mit höchstens $2\cdot \Delta(G) - 1$ Farben, für die absolute Gütegarantie gilt $\kappa_\greedycoledge = \Delta(G) - 1$.
|
|
\end{satz}
|
|
\begin{proof}
|
|
Erreicht \greedycoledge{} eine noch ungefärbte Kante, können an ihre beiden Knoten jeweils maximal $\Delta(G) - 1$ andere Kanten antreffen. Es muss also noch mindestens eine Farbe aus der Menge $\{1,\dots, 2\cdot \Delta(G) - 1\}$ frei sein.
|
|
|
|
Für eine Kantenfärbung werden mindestens $\Delta(G)$ Farben benötigt, also folgt
|
|
\begin{equation*}
|
|
\kappa_\greedycoledge = \abs*{\greedycoledge(2) - \opt(G)} \leq \abs*{2\cdot \Delta(G) - 1 - \Delta(G)} = \Delta(G) - 1
|
|
\end{equation*}
|
|
\end{proof}
|
|
|
|
\section{\greedyvc{} für \vertexcover}
|
|
\begin{algorithmic}[1]
|
|
\State $C = \emptyset$
|
|
\While{$E \neq \emptyset$}
|
|
\State wähle beliebige Kante $\{u, v\} \in E$
|
|
\State $C = C \cup \{u,v\}$
|
|
\State lösche $u,v$ und die dazu adjazenten Kanten aus $G$
|
|
\EndWhile
|
|
\State\Return $C$
|
|
\end{algorithmic}
|
|
|
|
\begin{satz}
|
|
\greedyvc{} liefert eine Knotenüberdeckung mit relativer Güte $2$.
|
|
\end{satz}
|
|
\begin{proof}
|
|
Wenn \greedyvc{} zwei Knoten hinzufügt, könnte es auch ausreichen, nur eine einzelne Kante aufzunehmen. Es werden außerdem nie mehr als 2 Knoten pro Kante aufgenommen.
|
|
\end{proof}
|
|
|
|
\section{\nextfit{} für \binpacking}
|
|
\begin{algorithmic}[1]
|
|
\State $k = 1$
|
|
\State $B_1 = \emptyset$
|
|
\ForAll{$i \in \{1,\dots,n\}$}
|
|
\If{$s(a_i)+ s(B_k) > 1$}
|
|
\State $k = k+1$
|
|
\State $B_k = \emptyset$
|
|
\EndIf
|
|
\State $B_k = B_k \cup \{a_i\}$
|
|
\EndFor
|
|
\State \Return $(B_1,\dots,B_k)$
|
|
\end{algorithmic}
|
|
\begin{satz}
|
|
\nextfit{} approximiert \binpacking{} mit relativer Gütegarantie $\rho_\nextfit = 2$.
|
|
\end{satz}
|
|
|
|
\section{Christofides' Algorithmus \algo{CH} für $\deltatsp$}
|
|
Ein Matching $M$ eines kantengewichteten Graphen $G$ ist ein Teilgraph von $G$ mit $\Delta(G) \le 1$. Ist $G$ ein vollständiger Graph mit $\abs*{V}$ gerade, dann gibt es perfekte Matchings. In einem perfekten Matching haben alle Knoten genau den Grad 1. Ein perfektes Matching mit kleinstmöglichem Gewicht wird als leichtestes Matching bezeichnet. Ein solches leichtestes Matching kann in $\bigO(n^{2.5}\cdot (\log n)^4)$ berechnet werden.
|
|
|
|
Als Multi-Graph wird ein Graph bezeichnet, der um mehrere Kanten zwischen den gleichen Knoten erweitert wurde.
|
|
|
|
Wird in einem Pfad jede Kante des (Multi-)Graph genau einmal besucht, so spricht man von einem Euler-Pfad. Bildet der Pfad einen Kreis, so nennt man ihn Euler-Kreis oder Euler-Tour. Haben alle Knoten von $G$ geraden Grad, so existiert eine Euler-Tour in $G$. Diese lässt sich in $\bigO(\abs*{V} + \abs*{E})$ berechnen.
|
|
|
|
Der Algorithmus von Christofides (\algo{CH}) geht wie folgt vor:
|
|
\begin{algorithmic}[1]
|
|
\State berechne einen minimalen Spannbaum $T_\ch$ von $I = \encoded*{ K_n, c}$
|
|
\State $S = \{v \in T_\ch \mid \degree_{T_\ch}(v)\, \text{ungerade}\}$ \Comment{$\abs*{S}$ ist gerade}
|
|
\State berechne auf dem durch $S$ induzierten Teilgraphen des $K_n$ ein leichtestes Matching $M_\ch$
|
|
\State berechne eine Euler-Tour $E = (u_1, u_2, \dots)$ auf $T_\ch \cupdot M_\ch$ \Comment{$T_\ch \cupdot M_\ch$ kann Multi-Graph sein, alle Knoten haben geraden Grad}
|
|
\State entferne Wiederholungen von Knoten in $E$, sodass man $E'$ erhält
|
|
\State\Return $E'$
|
|
\end{algorithmic}
|
|
|
|
\begin{satz}
|
|
\algo{CH}, gestartet mit einer Eingabe auf $n$ Knoten, garantiert eine relative Güte von $\rho_\ch \le \frac{3}{2} - \frac{1}{n}$ in einer Laufzeit von $\bigO(n^{2.5}\cdot (\log n)^4)$.
|
|
\end{satz}
|
|
\begin{proof}
|
|
Sei $R^*$ eine optimale Rundreise für $I$, d.h. $c(R^*) = \opt(I)$. Es gilt $\algo{CH}(I) = c(E') \le (\frac{3}{2} - \frac{1}{n}) \cdot c(R^*)$ zu zeigen.
|
|
\begin{enumerate}
|
|
\item Da $R^*$ aus $n$ Kanten besteht, muss durch ein Durchschnittsargument mindestens eine Kante $e$ mit $c(e) \ge \frac{c(R^*)}{n}$ existieren. Wird diese aus $R^*$ entfernt, so enthält man einen Spannbaum des $K_n$. Da $T_\ch$ minimal ist, gilt
|
|
\begin{equation*}
|
|
c(T_\ch) \le c(R^*) - \frac{c(R^*)}{n} = \left(1 - \frac{1}{n}\right) \cdot c(R^*)
|
|
\end{equation*}
|
|
\item In beliebigen Bäumen ist die Anzahl der Knoten mit ungeradem Grad gerade.
|
|
\item Zur Vereinfachung werden die Knoten so umbenannt, dass $R^* = (u_1, u_2, \dots, u_n, u_1)$ ist.
|
|
$S$ kann dann als $S = \{u_{i_1}, \dots, u_{i_{\abs*{S}}}\}$ mit $i_1 < \dots < i_{\abs*{S}}$ geschrieben werden.
|
|
|
|
Aus $S$ kann ein Kreis $H = (u_{i_1}, \dots, u_{i_{\abs*{S}}}, u_{i_1})$ gebildet werden. Durch die Dreiecksungleichung ($\abs*{H} \le n$ und jede \enquote{Abkürzung} ist maximal gleich lang wie der Weg in $R^*$) gilt $c(H) \le c(R^*)$.
|
|
|
|
Es können zwei perfekte Matching $M_1$ und $M_2$ auf $H$ berechnet werden, denn $\abs*{S}$ ist gerade. Weil $M_\ch$ minimal ist, folgt o.B.d.A. mit $c(M_1) \le c(M_2)$ die Aussage
|
|
\begin{equation*}
|
|
c(M_\ch) \leq c(M_1) \le \frac{1}{2} \cdot (c(M_1) + c(M_2)) = \frac{1}{2} \cdot c(H) \le \frac{1}{2} \cdot c(R^*)
|
|
\end{equation*}
|
|
\item Da jeder Knoten in $T_\ch \cupdot M_\ch$ geraden Grad hat, kann eine Euler-Tour $E$ berechnet werden. Weil diese nur Kanten aus $T_\ch \cupdot M_\ch$ benutzt, kann ihre Länge mit den vorherigen Ergebnissen wie folgt beschränkt werden:
|
|
\begin{equation*}
|
|
c(E) = c(T_\ch \cupdot M_\ch) \le \left(1 - \frac{1}{n}\right)\cdot c(R^*) + \frac{1}{2}\cdot c(R^*) = \left(\frac{3}{2} - \frac{1}{n}\right) \cdot \opt(I)
|
|
\end{equation*}
|
|
\item Durch die Dreiecksungleichung kann $E'$ nicht länger als $E$ werden.
|
|
\end{enumerate}
|
|
\end{proof}
|
|
\begin{zeuge}
|
|
TODO
|
|
\end{zeuge}
|
|
|
|
\section{Approximationsschema für \rucksack}
|
|
\subsection{\dynrucksack{} zur exakten Lösung von \rucksack}
|
|
Für eine Instanz $I = \encoded*{ W, \vol, p, B}$ kann direkt eine obere und eine untere Grenze für den maximalen Wert der Füllung angegeben werden:
|
|
\begin{equation*}
|
|
P_{\max} \le \opt(I) \le n \cdot P_{\max}
|
|
\end{equation*}
|
|
|
|
Sei $F_j(\alpha)$, wobei $j \in \{0, 1, \dots, n\}$ und $\alpha \in \mathbb{Z}$ gilt, das kleinste benötigte Rucksackvolumen, mit dem man einen Wert von mindestens $\alpha$ erreichen kann, wenn man die ersten $j$ Waren einpacken darf.
|
|
Die formale Definition
|
|
\begin{equation*}
|
|
F_j(\alpha) = \min\{\vol(R)\mid R \subseteq \{1, \dots, j\}, p(R) \ge \alpha\}
|
|
\end{equation*}
|
|
lässt sich durch die folgende Rekursion ausdrücken:
|
|
\begin{equation*}
|
|
f_j(\alpha) = \begin{cases*}
|
|
0 & falls $\alpha \le 0$\\
|
|
\infty & falls $\alpha \ge 1, j = 0$\\
|
|
\min\{F_{j-1}(\alpha - p_j) + \vol(j), F_{j-1}(\alpha)\} & sonst (sog. Bellmannsche Optimalitätsgl.)
|
|
\end{cases*}
|
|
\end{equation*}
|
|
|
|
Der Algorithmus \dynrucksack{} setzt diese durch dynamische Programmierung um:
|
|
\begin{algorithmic}[1]
|
|
\State $\alpha = 0$
|
|
\Repeat
|
|
\State $\alpha = \alpha + 1$
|
|
\For{$j \in \{1,\dots,n\}$}
|
|
\State $F_j(\alpha) = \min\{F_{j-1}(\alpha - p_j) + \vol(j), F_{j-1}(\alpha)\}$
|
|
\EndFor
|
|
\Until{$B < F_n(\alpha)$}
|
|
\State \Return $\alpha - 1$
|
|
\end{algorithmic}
|
|
|
|
\begin{satz}
|
|
\dynrucksack{} berechnet zur Eingabe $I$ den Wert $\opt(I)$ in Zeit $\bigO(n \cdot \opt(I)) = \bigO(n^2 \cdot P_{\max})$.
|
|
\end{satz}
|
|
|
|
\subsection{$\ark$ zur Approximation mit konstantem relativen Fehler}
|
|
Der Algorithmus $\ark$ rechnet mit um den Faktor $k$ reduzierten, gerundeten Preisen:
|
|
\begin{algorithmic}[1]
|
|
\State $p_\red(w) = \left\lfloor\frac{p(w)}{k}\right\rfloor$
|
|
\State $I_\red = \encoded*{ W, \vol, p_\red, B }$
|
|
\State $R_k = \Call{\dynrucksack{}}{I_\red}$
|
|
\State \Return $R_k$
|
|
\end{algorithmic}
|
|
|
|
\begin{satz}
|
|
$\ark$ macht bei Eingabe $I$ einen relativen Fehler von $\varepsilon_{\ark} \le \frac{k \cdot n}{P_{\max}}$ und hat eine Laufzeit von $\bigO(n^2 \cdot \frac{P_{\max}}{k})$.
|
|
\end{satz}
|
|
\begin{proof}
|
|
Sei $R^*$ die Indexmenge einer optimalen Rucksackfüllung für $I$ und $R_k$ die berechnete Indexmenge der Lösung des um $k$ reduzierten Problems $I_\red$.
|
|
|
|
Da $R_k$ eine optimale Lösung für $I_\red$ ist, gilt $\opt(I_\red) \geq \sum_{j\in R^*}\left\lfloor\frac{p_j}{k}\right\rfloor$. Weiterhin ist $R_k$ eine zulässige Lösung für $I$.
|
|
Es gilt dann:
|
|
\begin{align*}
|
|
\ark(I) &= p(R_k) \ge k \cdot \sum_{j\in R_k} \left\lfloor \frac{p_j}{k}\right\rfloor = k \cdot \opt(I_\red)\\
|
|
&\ge k\cdot \sum_{j\in R^*} \left\lfloor \frac{p_j}{k}\right\rfloor \ge k \cdot \sum_{j\in R^*}\left(\frac{p_j}{k} - 1\right) = \sum_{j\in R^*}\left(p_j - k\right) = p(R^*) - k \cdot \abs*{R^*}\\
|
|
&= \opt(I) - k \cdot \abs*{R^*} \ge \opt(I) - k \cdot n
|
|
\end{align*}
|
|
|
|
Damit folgt für den relativen Fehler die zu zeigende Aussage
|
|
\begin{equation*}
|
|
\varepsilon_{\ark} = \frac{\abs*{\ark(I) - \opt(I)}}{\opt(I)} \le \frac{k\cdot n}{\opt(I)} \le \frac{k\cdot n}{P_{\max}}
|
|
\end{equation*}
|
|
\end{proof}
|
|
|
|
\subsection{\fpasrucksack{} zur Umwandlung in ein streng polynomielles Approximationsschema}
|
|
Um ein FPAS zu erreichen, muss gezeigt werden, dass jedes $\varepsilon \in ]0, 1[$ als relativer Fehler erreichbar ist.
|
|
Der Algorithmus \fpasrucksack{} verwendet dazu $\ark$ und konstruiert ein passendes $k$:
|
|
\begin{algorithmic}[1]
|
|
\State bestimme $n$ und $P_{\max}$ aus der Eingabe $I$
|
|
\State $k = \varepsilon \cdot \frac{P_{\max}}{n}$
|
|
\State \Return \Call{$\ark$}{$I$}
|
|
\end{algorithmic}
|
|
|
|
\begin{satz}
|
|
\fpasrucksack{} ist ein FPAS für \rucksack{} mit einer Laufzeit von $\bigO\left(n \cdot \log \frac{1}{\varepsilon} + \frac{1}{\varepsilon^4}\right)$.
|
|
\end{satz}
|
|
|
|
\section{Randomisierte Approximationsalgorithmen}
|
|
\subsection{Die probabilistische Methode mit Algorithmus $A$}
|
|
\begin{satz}
|
|
Sei $\Phi$ eine boolesche $(n,m)$-Formel in KNF, dann gilt
|
|
\begin{equation*}
|
|
\max\{\wahr\left(\false{}, \dots, \false{}, \Phi\right), \wahr\left(\true{}, \dots, \true{}, \Phi\right)\} \ge \frac{1}{2}\cdot m
|
|
\end{equation*}
|
|
\end{satz}
|
|
\begin{proof}
|
|
Wenn eine Belegung aus lediglich o.B.d.A. \true{} weniger als die Hälfte der Klauseln erfüllt, muss die Belegung aus lediglich \false{} den Rest, also mehr als die Häflte erfüllen.
|
|
\end{proof}
|
|
|
|
Der folgende Algorithmus $A$ nutzt die sogenannte probabilistische Methode aus, in dem eine Belegung für jede Variable stochastisch unabhängig durchgeführt wird:
|
|
\begin{algorithmic}[1]
|
|
\For{$i \in \{1,\dots,n\}$}
|
|
\State $x_i = \begin{cases*}
|
|
\true{} & mit Wahrscheinlichkeit $\frac{1}{2}$\\
|
|
\false{} & mit Wahrscheinlichkeit $\frac{1}{2}$
|
|
\end{cases*}$
|
|
\EndFor
|
|
\State \Return $b_A = (x_1, \dots, x_n)$
|
|
\end{algorithmic}
|
|
|
|
\begin{satz}
|
|
Sei $k_j$ die Anzahl der Literale in $C_j$. Es gilt
|
|
\begin{equation*}
|
|
P\left[C_j\,\text{wird durch den Algorithmus $A$ erfüllt}\right] = 1 - \frac{1}{2^{k_j}}
|
|
\end{equation*}
|
|
\end{satz}
|
|
\begin{proof}
|
|
Beweis über Gegenwahrscheinlichkeit, dass alle Literale nicht erfüllt sind (stochastische Unabhängigkeit).
|
|
\end{proof}
|
|
|
|
\begin{satz}
|
|
Für jede boolesche $(n, m)$-Formel $\Phi$ in KNF, in der jede Klausel mindestens $k$ Literale hat, gilt:
|
|
\begin{equation*}
|
|
E\left[A(\Phi)\right] \ge \left(1 - \frac{1}{2^k}\right) \cdot m
|
|
\end{equation*}
|
|
Des Weiteren existiert eine Belegung $b$ mit $\wahr(b, \Phi) \ge \left(1 - \frac{1}{2^k}\right) \cdot m$.
|
|
\end{satz}
|
|
\begin{proof}
|
|
Für jede Klausel $C_j$ wird eine Indikator-Variable $Z_j$ mit
|
|
\begin{equation*}
|
|
Z_j = \begin{cases*}
|
|
1 & falls $b_A(C_j) = $\true{}\\
|
|
0 & sonst
|
|
\end{cases*}
|
|
\end{equation*}
|
|
eingeführt. Da ihr Erwartungswert gleich der Wahrscheinlichkeit, dass sie 1 annimmt, ist, folgt
|
|
\begin{equation*}
|
|
E\left[A(\Phi)\right] = E\left[\wahr(b_A, \Phi)\right] = E\left[\sum_{j=1}^{m} Z_j\right] = \sum_{j=1}^{m} \left(1 - \frac{1}{2^{k_j}}\right) \ge \left(1 - \frac{1}{2^k}\right) \cdot m
|
|
\end{equation*}
|
|
Die Existenz einer solchen Belegung folgt aus einem klassischen Durchschnittsargument.
|
|
\end{proof}
|
|
|
|
\begin{satz}
|
|
Sei $2^k > m$, dann ist jede boolesche $(n,m)$-Formel $\Phi$ in KNF, in der jede Klausel mindestens $k$ Literale hat, erfüllbar.
|
|
\end{satz}
|
|
\begin{proof}
|
|
Eingesetzt in die vorherige Aussage, erhält man dann $\left(1 - \frac{1}{2^k}\right) \cdot m = m - \overbrace{\frac{m}{2^k}}^{< 1}$ = m. Aus einem Durchschnittsargument folgt auch hier, dass es eine Belegung $b$ mit $\wahr(b, \Phi) = m$ geben muss.
|
|
\end{proof}
|
|
|
|
\begin{satz}
|
|
Algorithmus $A$ hat für jede $(n, m)$-Formel $\Phi$ in KNF, in der jede Klausel mindestens $k$ Literale hat, eine erwartete relative Güte von
|
|
\begin{equation*}
|
|
E\left[\rho_A(\Phi)\right] = \frac{\opt(\Phi)}{E\left[A(\Phi)\right]} \le \frac{m}{\left(1 - \frac{1}{2^k}\right)\cdot m} = \frac{1}{1 - \frac{1}{2^k}}
|
|
\end{equation*}
|
|
. Die Laufzeit des Algorithmus ist $\bigO(n)$. Wenn die kürzeste Klausel mindestens 2 Literale hat, hat $A$ die erwartete relative Güte $\frac{4}{3}$.
|
|
\end{satz}
|
|
|
|
\begin{satz}
|
|
Algorithmus $A$ garantiert für jede boolesche $(n,m)$-Formel $\Phi$ in KNF sogar eine erwartete relative Güte von $\frac{3}{2}$.
|
|
\end{satz}
|
|
|
|
\subsection{Arithmetisierung und Randomized Rounding mit Algorithmus $B$}
|
|
\maxsat{} kann auch als Lineares Programm (LP) ausgedrückt werden.
|
|
Es bezeichnen im Folgenden $S_j^{\oplus}$ die Menge der Variablen, die in $C_j$ nicht negiert vorkommen, und $S_j^{\ominus}$ die Menge der Variablen, die in $C_j$ negiert vorkommen.
|
|
Für jede boolesche Variable $x_i$ wird eine 0-1-Variable $\hat{x}_i$ eingeführt; für jede Klausel $C_j$ eine 0-1-Variable $\hat{Z}_j$.
|
|
Es ergibt sich also das folgende ganzahlige lineare Programm (ILP) $B$ für \maxsat:
|
|
\begin{align*}
|
|
\text{maximiere} &\quad\sum_{j=1}^{m} \hat{Z}_j\\
|
|
\text{gemäß} &\quad\sum_{x_i \in S_j^{\oplus}} \hat{x}_i + \sum_{x_i \in S_j^{\ominus}} \left(1 - \hat{x}_i\right) \ge \hat{Z}_j &\forall j\\
|
|
&\quad\hat{x}_i \in \{0, 1\} &\forall i\\
|
|
&\quad\hat{Z}_j \in \{0, 1\} &\forall j
|
|
\end{align*}
|
|
Relaxiert man die Bedingungen, dass $\hat{x}_i, \hat{Z}_j \in \{0, 1\}$ gelten muss, und fordert stattdessen $\forall i, j: 0\le \hat{x}_i, \hat{Z}_j \le 1$, kann das resultierende LP $B_\rel$ in Polynomzeit gelöst werden. Das LP selbst hat ebenfalls eine polynomiell beschränkte Anzahl an Bedingungen, sodass die Gesammtlaufzeit auch polynomiell beschränkt ist.
|
|
|
|
Durch die Relaxierung entsteht die folgende Beziehung (exemplarisch für ein Maximierungsproblem), die als Superoptimalität bezeichnet wird:
|
|
\begin{equation*}
|
|
\opt(B_\rel) \ge \opt(B) = \opt(\Phi)
|
|
\end{equation*}
|
|
|
|
Im Allgemeinen ist die rationale Lösung $\sigma_\rel$ von $B_\rel$ also keine zulässige Lösung für $B$.
|
|
Hierzu müssen die $\hat{x}_i$ auf 0 oder 1 (bzw. die $x$ auf \false{} oder \true{}) gerundet werden.
|
|
Eine Möglichkeit hierzu stellt der durch die stochastische Funktion $\pi: \left[0, 1\right] \mapsto \left[0, 1\right]$ parametrisierte Algorithmus $\algo{RandomizedRounding}[\pi]$ dar:
|
|
\begin{algorithmic}[1]
|
|
\For{$i \in \{1,\dots,n\}$}
|
|
\State $x_i = \begin{cases*}
|
|
\true{} & mit Wahrscheinlichkeit $\pi(\hat{x}_i)$\\
|
|
\false{} & mit Wahrscheinlichkeit $1 - \pi(\hat{x}_i)$\\
|
|
\end{cases*}$
|
|
\EndFor
|
|
\State \Return $b_B = (x_1,\dots,x_n)$
|
|
\end{algorithmic}
|
|
|
|
Damit kann dann der Algorithmus $B$ gebildet werden, der \maxsat{} approximiert:
|
|
\begin{algorithmic}[1]
|
|
\State konstruiere das LP $B_\rel$ zur Eingabe $\Phi$
|
|
\State ermittle die rationale Lösung $b_\rel$ von $B_\rel$
|
|
\State \Return \Call{$\algo{RandomizedRounding}[\pi(x) = x]$}{$b_\rel$}
|
|
\end{algorithmic}
|
|
|
|
\begin{satz}
|
|
Sei $k_j$ die Anzahl der Literale in $C_j$, dann gilt:
|
|
\begin{equation*}
|
|
P\left[C_j\,\text{wird durch den Algorithmus $B$ erfüllt}\right] \ge \left(1 - \left(1 - \frac{1}{k_j}\right)^{k_j}\right)\cdot \hat{Z}_j
|
|
\end{equation*}
|
|
\end{satz}
|
|
\begin{proof}
|
|
Erneut wird über die Gegenwahrscheinlichkeit argumentiert:
|
|
\begin{equation*}
|
|
P\left[C_j\,\text{wird durch den Algorithmus $B$ nicht erfüllt}\right] = \left[\Pi_{x_i\in S_j^{\oplus}} \left(1 - \hat{x}_i\right)\right] \cdot \left[\Pi_{x_i\in S_j^{\ominus}} \hat{x}_i\right]
|
|
\end{equation*}
|
|
Es folgt
|
|
\begin{align*}
|
|
P&\left[C_j\,\text{wird durch den Algorithmus $B$ erfüllt}\right] = 1- \left[\Pi_{x_i\in S_j^{\oplus}} \left(1 - \hat{x}_i\right)\right] \cdot \left[\Pi_{x_i\in S_j^{\ominus}} \hat{x}_i\right]\\
|
|
&\ge 1 - \left(\frac{\sum_{x_i \in S_j^{\oplus}}\left(1 - \hat{x}_i\right) + \sum_{x_i \in S_j^{\ominus}}\hat{x}_i}{k_j}\right)^{k_j}\\
|
|
&= 1 - \left(\frac{\abs*{S_j^{\oplus}} - \sum_{x_i \in S_j^{\oplus}}\hat{x}_i + \abs*{S_j^{\ominus}} - \sum_{x_i \in S_j^{\ominus}}\left(1 -\hat{x}_i\right)}{k_j}\right)^{k_j}\\
|
|
&= 1 - \left(\frac{k_j - \left(\sum_{x_i \in S_j^{\oplus}}\hat{x}_i + \sum_{x_i \in S_j^{\ominus}}\left(1 -\hat{x}_i\right)\right)}{k_j}\right)^{k_j}\\
|
|
&\overset{\text{NB von $B$}}{\ge} 1 - \left(1 - \frac{\hat{Z}_j}{k_j}\right)^{k_j} \overset{\text{Konkavität}}{\ge} \left(1 - \left(1 - \frac{1}{k_j}\right)^{k_j}\right)\cdot \hat{Z}_j
|
|
\end{align*}
|
|
\end{proof}
|
|
|
|
\begin{satz}
|
|
Für jede boolesche Formel $\Phi$ in KNF, in der jede Klausel höchstens $k$ Literale hat, gilt
|
|
\begin{equation*}
|
|
E\left[B(\Phi)\right] \ge \left(1 - \left(1 - \frac{1}{k}\right)^{k}\right)\cdot\opt(\Phi)
|
|
\end{equation*}
|
|
\end{satz}
|
|
\begin{satz}
|
|
Mit der bekannten Abschätzung $1 - \left(1 - \frac{1}{k}\right)^k \ge 1 -\frac{1}{e}$ für alle $k \in \naturals$
|
|
beträgt die erwartete Anzahl an erfüllten Klauseln von Algorithmus $B$ bei einer Eingabe $\Phi$ in KNF mindestens $\left(1 - \frac{1}{e}\right)\cdot\opt(\Phi) \approx 0.632\cdot\opt(\Phi)$.
|
|
|
|
Algorithmus $B$ hat also eine erwartete relative Güte von
|
|
\begin{equation*}
|
|
E\left[\rho_B(\Phi)\right] \le \frac{1}{1 - \frac{1}{e}} \approx 1.582
|
|
\end{equation*}
|
|
\end{satz}
|
|
|
|
\begin{satz}
|
|
Mit $\pi(x) = \frac{1}{2}\cdot x + \frac{1}{4}$ oder $1 - \frac{1}{4^x} \le \pi(x) \le 4^{x-1}$ kann Algorithmus $B$ sogar eine erwartete relative Güte von $\frac{4}{3}$ erreichen.
|
|
\end{satz}
|
|
|
|
\subsection{Hybrider Ansatz durch Kombination mehrerer Verfahren}
|
|
Aus den bestimmten Gütegarantien lässt sich ablesen, dass Algorithmus $A$ besonders gut für Formeln geeignet ist, die keine Klauseln aus nur einem Literal enthalten. Algorithmus $B$ eignet sich allgemein gut, wenn die auftretenden Klauseln kurz sind.
|
|
|
|
Beide Verfahren können nun automatisch kombiniert werden, um eine insgesamt bessere Gütegarantie zu erreichen.
|
|
Dier erste Möglichkeit hierzu ist der Algorithmus $C_{p_A}$:
|
|
\begin{algorithmic}[1]
|
|
\State \Return $\begin{cases*}
|
|
A(\Phi) & mit Wahrscheinlichkeit $p_A$\\
|
|
B(\Phi) & mit Wahrscheinlichkeit $1 - p_A$
|
|
\end{cases*}$
|
|
\end{algorithmic}
|
|
Alternativ startet der Algorithmus $C_\mathrm{alle}$ immer beide Algorithmen:
|
|
\begin{algorithmic}[1]
|
|
\State $b_A = A(\Phi)$
|
|
\State $b_B = B(\Phi)$
|
|
\State \Return $\max\{b_A, b_B\}$
|
|
\end{algorithmic}
|
|
|
|
Es gilt offensichtlich \begin{equation*}
|
|
E\left[C_\mathrm{alle}(\Phi)\right] \ge E\left[C_{p_A}(\Phi)\right] = p_A \cdot E\left[A(\Phi)\right] + \left(1 - p_A\right) \cdot E\left[B(\Phi)\right]
|
|
\end{equation*} für alle $p_A \in \left[0, 1\right]$.
|
|
|
|
\begin{satz}
|
|
Der Algorithmus $C_{\frac{1}{2}}$ hat eine erwartete relative Güte von $\frac{4}{3}$.
|
|
\end{satz}
|
|
\begin{proof}
|
|
Es sind folgende Erwartungswerte bekannt:
|
|
\begin{align*}
|
|
E\left[A(\Phi)\right] & = \sum_{k=1}^{n} \sum_{C_j\,\text{hat}\,k\,\text{Literale}} \left(1 - \frac{1}{2^k}\right) \overset{0 \le \hat{Z}_j \le 1}{\ge} \sum_{k=1}^{n} \sum_{C_j\,\text{hat}\,k\,\text{Literale}} \left(1 - \frac{1}{2^k}\right) \cdot \hat{Z}_j\\
|
|
E\left[B(\Phi)\right] &\ge \sum_{k=1}^{n} \sum_{C_j\,\text{hat}\,k\,\text{Literale}} \left(1 - \left(1 - \frac{1}{k}\right)^k\right)\cdot \hat{Z}_j
|
|
\end{align*}
|
|
Es folgt also für $C_\frac{1}{2}$:
|
|
\begin{align*}
|
|
E\left[C_{\frac{1}{2}}(\Phi)\right] &\ge \frac{1}{2} \cdot \sum_{k=1}^{n} \sum_{C_j\,\text{hat}\,k\,\text{Literale}} \underbrace{\left(1 - \frac{1}{2^k} + 1 - \left(1 - \frac{1}{k}\right)^k\right)}_{\ge \frac{3}{2}}\cdot \hat{Z}_j\\
|
|
& \ge \frac{1}{2}\cdot\frac{3}{2}\cdot \sum_{k=1}^{n} \sum_{C_j\,\text{hat}\,k\,\text{Literale}} \hat{Z}_j\\
|
|
&= \frac{3}{4}\sum_{j=1}^{m} \hat{Z}_j \ge \frac{3}{4}\cdot \opt(\Phi)
|
|
\end{align*}
|
|
\end{proof}
|
|
|
|
\subsection{Derandomisierung durch die Methode der bedingten Erwartungswerte}
|
|
Die Ansätze mancher randomisierter Algorithmen können so modifiziert werden, dass sie deterministisch ein Ergebnis zurückliefern, was mindestens so gut wie der Erwartungswert des nicht-deterministischen Algorithmus ist.
|
|
Man macht sich hierbei unter anderem die Eigenschaft des randomisierten Algorithmus zu Nutze, dass der Erwartungswert auch ohne wirkliche Ausführung des Algorithmus berechenbar ist.
|
|
|
|
Der Algorithmus \algo{Derand\_$A$} benutzt den Erwartungswert für Algorithmus $A$ um nach und nach alle Variablen $x_i$ zu belegen. Für jede Variable wird einmal \true{} und \false{} eingesetzt, dann mit der resultierenden Formel mit höherem Erwartungswert fortgefahren:
|
|
\begin{algorithmic}[1]
|
|
\For{$i \in \{1,\dots,n(I)\}$}
|
|
\State $W_\false{} = E\left[A(I)\mid x_1,\dots,x_{i-1}, x_i = \false{}\right]$
|
|
\State $W_\true{} = E\left[A(I)\mid x_1,\dots,x_{i-1}, x_i = \true{}\right]$
|
|
\If{$W_\false{} < W_\true{}$}
|
|
\State $x_i = \true{}$
|
|
\Else
|
|
\State $x_i = \false{}$
|
|
\EndIf
|
|
\EndFor
|
|
\State \Return $b = (x_1, \dots, x_{n(I)})$
|
|
\end{algorithmic}
|
|
\begin{satz}
|
|
Der Algorithmus \algo{Derand\_$A$} approximiert \maxsat{} mit relativer Worst-Case-Güte\\
|
|
$\rho_{\algo{Derand\_}A}^{\mathrm{wc}} = \frac{1}{1 - \frac{1}{2^k}}$ in Polynomzeit.
|
|
\end{satz}
|
|
|
|
\section{Approximation durch Lineare Optimierung}
|
|
Die zum Lösen eines LP mit $k$ Variablen benötigte Zeit wird im Folgenden als $L\left(\abs*{\mathrm{LP}}, k\right)$ bezeichnet.
|
|
Sie liegt in der Größenordnung $\bigO(k^4 \cdot \abs*{\encoded*{\mathrm{LP}}}^2)$.
|
|
|
|
\subsection{Ganzzahligkeitslücke}
|
|
Der für \maxsat{} gewählte Ansatz lässt sich im Prinzip auch auf verschiedenste andere kombinatorische Optimierungsprobleme $\Pi$ anwenden. Verallgemeinert bezeichnet man ihn als Rundungsansatz (exemplarisch für Maximierungsprobleme):
|
|
\begin{enumerate}
|
|
\item Beschreibung der Instanz $I$ von $\Pi$ durch ein ganzzahliges Lineares Programm $X$, was als Arithmetisierung bezeichnet wird.
|
|
Es gilt damit $\opt(I) = \opt(X)$.
|
|
\item Fallenlassen der Ganzzahligkeitsbedingung (Relaxierung), sodass das entstandene Lineare Programm $X_\rel$ in Polynomzeit lösbar ist.
|
|
Durch die Superoptimalität gilt $\opt(X_\rel) \ge \opt(X)$.
|
|
\item Der Approximationsalgorithmus $A$ löst $X_\rel$ und rundet die rationale Lösung geschickt zu einer zulässigen Lösung $\sigma \in \solution(I)$.
|
|
\item Beweis, dass $A(I) \ge \frac{1}{\rho}\cdot \opt(X_\rel)$ gilt.
|
|
\item Aus der Superoptimalität folgt $A(I) \ge \frac{1}{p}\cdot \opt(I)$.
|
|
\end{enumerate}
|
|
|
|
Für ein kombinatorisches Maximierungsproblem $\Pi$ mit Eingaben $I \in \domain$ sei $X$ jeweils das äquivalente ILP und $X_\rel$ jeweils das relaxierte LP.
|
|
Dann bezeichnet
|
|
\begin{equation*}
|
|
\gamma = \max\left\{\frac{\opt(X_\rel)}{\opt(X)} \mid I\in \domain \right\} \ge 1
|
|
\end{equation*}
|
|
die Ganzzahligkeitslücke (\enquote{integrality gap}) der Relaxierung.
|
|
|
|
Für das LP $B_\rel$ für \maxsat{} bestimmt sich die Ganzzahligkeitslücke aus der booleschen $(2,4)$-Formel $\Phi = (x_1 \lor x_2) \land (\overline{x_1} \lor x_2) \land (x_1 \lor \overline{x_2}) \land (\overline{x_1} \lor \overline{x_2})$:
|
|
$\opt(\Phi) = 3$, aber $\opt(B_\rel) = 4$. Damit folgt $\gamma \le \frac{4}{3}$.
|
|
|
|
Allgemein folgen mit $\gamma \ge \frac{\opt(X_\rel)}{\opt(X)}$ die beiden Aussagen
|
|
\begin{align*}
|
|
A(I) &\ge \frac{\gamma}{\rho}\cdot \opt(I)\\
|
|
\rho &\ge \gamma
|
|
\end{align*}
|
|
|
|
Daraus kann geschlossen werden, dass der Rundungsansatz die Ganzzahligkeitslücke nicht überwinden kann und Modellierung in LP mit geringer Ganzzahligkeitslücke wichtig ist.
|
|
|
|
\subsection{Arithmetisierung von \setcover}
|
|
Sei $X = \{S_{i_1}, \dots, S_{i_l}\}$ eine Sammlung von Gruppen, dann bezeichne die Notation $V(X) = S_{i_1} \cup \dots \cup S_{i_l}$ die Menge der von $X$ überdeckten Objekte.
|
|
Weiter bezeichne $G_S = \max\{\abs*{S_i}\mid 1\le i\le m\}$ die Mächtigkeit der größten Gruppe, $\degree_S(u) = \abs*{\{S_i \mid u \in S_i \in S\}}$ den Grad des Objekts $u \in V$ und $\Delta_S = \max{\{\degree_S(u)\mid u \in V\}}$ den Grad von $S$.
|
|
|
|
Bei der Arithmetisierung wird pro Gruppe $S_i$ eine 0-1-Variable $x_i$ eingeführt, die genau dann 1 ist, wenn $S_i \in S_\cov$.
|
|
Damit lautet das ILP $X$ für \setcover:
|
|
\begin{align*}
|
|
\min &\quad \sum_{i=1}^{m} x_i\\
|
|
\text{gemäß} &\quad \sum_{i: u \in S_i} x_i \ge 1 & \forall u \in V\\
|
|
&\quad x_i \in \{0, 1\} & \forall i \in \{1, \dots, m\}
|
|
\end{align*}
|
|
|
|
\begin{satz}
|
|
Für die kanonische Relaxierung $X_\rel$ von $X$ gilt für die Ganzzahligkeitslücke
|
|
\begin{equation*}
|
|
\gamma \ge \frac{1}{2}\cdot \log n
|
|
\end{equation*}
|
|
\end{satz}
|
|
|
|
\subsection{Deterministisches Runden mit \detroundsc}
|
|
\begin{algorithmic}[1]
|
|
\State $(x_1, \dots, x_m) = $ löse $X_\rel$
|
|
\State $S_\cov = \emptyset$
|
|
\For{$i \in \{1,\dots,m\}$}
|
|
\If{$x_i \ge \frac{1}{\Delta_S}$}
|
|
\State $S_\cov = S_\cov \cup \{S_i\}$
|
|
\EndIf
|
|
\EndFor
|
|
\State \Return $S_\cov$
|
|
\end{algorithmic}
|
|
|
|
\begin{satz}
|
|
\detroundsc{} berechnet für eine Instanz $S$ von \setcover{} in Zeit $\bigO(m + L(nm, m))$ eine Überdeckung.
|
|
Ferner gilt $\detroundsc(S) \le \Delta_S \cdot \opt(S)$.
|
|
\end{satz}
|
|
\begin{proof}
|
|
Zu einem beliebigen Objekt $u\in V$ gehört die Nebenbedingung $\sum_{i: u \in S_i} x_i \ge 1$ mit $\degree_S(u)$ Summanden.
|
|
Mit einem Durchschnittsargument kann jetzt also gefolgert werden, dass für einen der Summanden $x_i$ gilt:
|
|
\begin{equation*}
|
|
x_i \ge \frac{1}{\degree_S(u)} \ge \frac{1}{\Delta_S}
|
|
\end{equation*}
|
|
Damit wird für jedes $u$ mindestens ein überdeckendes $S_i$ aufgenommen, also stellt die Ausgabe eine Überdeckung dar.
|
|
|
|
Weil für jede Gruppe $S_i \in S_\cov$ $\Delta_S \cdot x_i \ge 1$ gilt, folgt für die Qualität der Ausgabe
|
|
\begin{equation*}
|
|
\detroundsc(S) = \abs*{S_\cov} \le \sum_{i=1}^{m} \Delta_S \cdot x_i =\Delta_S \cdot \sum_{i=1}^{m} x_i = \Delta_S \cdot \opt(X_\rel) \le \Delta_S \cdot \opt(S)
|
|
\end{equation*}
|
|
\end{proof}
|
|
|
|
\subsection{Unzuverlässiges Randomized Rounding mit $\randroundscr$}
|
|
\begin{algorithmic}[1]
|
|
\State $(x_1, \dots, x_m) =$ löse $X_\rel$
|
|
\State $\chi = \emptyset$
|
|
\For{$i \in \{1,\dots,m\}$}
|
|
\State mit Wahrscheinlichkeit $1 - e^{-r \cdot x_i}$: $\chi = \chi \cup \{S_i\}$
|
|
\EndFor
|
|
\State \Return $\chi$
|
|
\end{algorithmic}
|
|
\randroundscr{} ist ein sogenannter Monte-Carlo-Algorithmus, weil er auch nicht zulässige Lösungen zurückliefern kann.
|
|
|
|
\begin{satz}
|
|
Für eine Eingabe $S$ von \setcover{} sei $\chi$ die Ausgabe von $\randroundscr$. Dann gelten
|
|
\begin{enumerate}
|
|
\item $P\left[\chi\,\text{ist eine Überdeckung}\right] \ge 1 - n \cdot e^{-r}$
|
|
\item $E\left[\abs*{\chi}\right] \le r \cdot \opt(S)$
|
|
\end{enumerate}
|
|
\end{satz}
|
|
\begin{proof}
|
|
\begin{enumerate}
|
|
\item Sei $u \notin V$, dann gilt:
|
|
\begin{align*}
|
|
P\left[u \in V(\chi)\right] &= P\left[\forall i\,\text{mit}\, u \in S_i: S_i \notin \chi\right]\\
|
|
&= \Pi_{i: u\in S_i} e^{-r \cdot x_i} = \left(\Pi_{i: u\in S_i} e^{-x_i}\right)^r = \left(e^{- \sum_{i: u \in S_i} x_i}\right)^r\\
|
|
&\le e^{-r}
|
|
\end{align*}
|
|
Die Wahrscheinlichkeit, dass es ein nicht überdecktes Objekt gibt, ist folglich
|
|
\begin{equation*}
|
|
P\left[\exists U \in V: u \notin V(\chi)\right] \le n \cdot e^{-r}
|
|
\end{equation*}
|
|
\item Für $\abs*{\chi}$ folgt
|
|
\begin{equation*}
|
|
E\left[\abs*{\chi}\right] = \sum_{i=1}^{m} P\left[S_i \in \chi\right] = \sum_{i=1}^{m} \left(1 - e^{-r\cdot x_i}\right) \le r\cdot \sum_{i=1}^{m} x_i = r\cdot \opt(X_\rel) \le r \cdot\opt(S)
|
|
\end{equation*}
|
|
\end{enumerate}
|
|
\end{proof}
|
|
|
|
\subsection{Las-Vegas-Algorithmus $\lasvegasscr$ für zuverlässig zulässige Lösungen}
|
|
\begin{algorithmic}[1]
|
|
\State löse das LP $X_\rel$
|
|
\State $\tau = 0$
|
|
\Repeat
|
|
\State $\chi = \randroundscr(S)$
|
|
\State $\tau = \tau + 1$
|
|
\Until{$V(\chi) = V$}
|
|
\State \Return $S_\cov = \chi$
|
|
\end{algorithmic}
|
|
Das LP $X_\rel$ wird dabei nur einmal und nicht erneut in $\randroundscr{}$ gelöst.
|
|
$\lasvegasscr$ ist ein sogenannter Las-Vegas-Algorithmus, weil er immer eine zulässige Lösung zurückliefert, seine Laufzeit allerdings zufällig ist.
|
|
|
|
\begin{satz}
|
|
Sei $S$ eine Eingabe von \setcover{} und gelte $r > \ln n$. Für \lasvegasscr{} gelten dann
|
|
\begin{enumerate}
|
|
\item $S_\cov$ ist eine Überdeckung mit erwarteter Größe von höchstens $r \cdot \opt(S)$.
|
|
\item Die erwartete Anzahl der Iterationen der Repeat-Schleife ist höchstens $\frac{e^{2r}}{\left(n - e^{r}\right)^2}$.
|
|
\end{enumerate}
|
|
\end{satz}
|
|
\begin{proof}
|
|
\begin{enumerate}
|
|
\item Das Ergebnis folgt direkt aus der Analyse von \randroundscr.
|
|
\item \begin{align*}
|
|
E\left[\tau\right] &= \sum_{t=1}^\infty t \cdot P\left[\text{erst die $t$. Wiederholdung ist eine Überdeckung}\right]\\
|
|
&\le \sum_{t=1}^\infty t\cdot P\left[\text{ $t - 1$ Wiederholdungen sind keine Überdeckung}\right]\\
|
|
&\le \sum_{t=1}^\infty t\cdot \left(n\cdot e^{-r}\right)^{t-1} \overset{\text{Konvergenz durch}\, r > \ln n}{=} \frac{e^{2r}}{\left(n - e^r\right)^2}
|
|
\end{align*}
|
|
\end{enumerate}
|
|
\end{proof}
|
|
|
|
\begin{satz}
|
|
$\lasvegassc[\ln n + 1]$ garantiert eine relative erwartete Güte von $\ln n + 1$. Der Erwartungswert für die Anzahl der Iterationen der Schleife ist $\left(\frac{e}{e - 1}\right)^2 < 2.503$.
|
|
\end{satz}
|
|
|
|
% TODO: Umorganisieren: (I)LP sowie Arithmetisierungen in Allgemeine Definitionen, Dualität als eigene section?
|
|
\section{Ausnutzen der Dualität von Linearen Programmen}
|
|
\subsection{Herleitung der Dualität}
|
|
Ein LP für ein o.B.d.A. Minimierungsproblem kann wie folgt geschrieben werden:
|
|
\begin{align*}
|
|
\min &\quad z(\vec{x}) = \transposed{\vec{c}} \cdot \vec{x}\\
|
|
\text{gemäß} &\quad A \cdot \vec{x} \ge \vec{b}\\
|
|
&\quad \vec{x} \ge \vec{0}
|
|
\end{align*}
|
|
Es bezeichnen $\row_i\left[A\right]$ die $i$. Zeile der Matrix $A$ und $\row_i\left[A\right] \cdot \vec{x} \ge b_i$ die $i$. Nebenbedingung des LP.
|
|
|
|
Mit $\vec{y} \ge \vec{0}$ können folgende neue Nebenbedingungen erzeugt werden, die ebenfalls von jeder zulässigen Lösung erfüllt werden:
|
|
\begin{equation*}
|
|
\transposed{\vec{y}} \cdot A \cdot \vec{x} \ge \transposed{\vec{y}}\cdot \vec{b}
|
|
\end{equation*}
|
|
Wählt man die $y_j$ so, dass die aus ihnen berechneten Koeffizienten der $x_i$ kleiner als die jeweiligen $c_i$, gilt für diese $\vec{y}$: $z(\vec{x}) \ge \transposed{\vec{y}} \cdot A\cdot \vec{x} \ge \transposed{\vec{y}}\cdot \vec{b}$ für alle zulässigen Lösungen $\vec{x}$.
|
|
Damit bildet $\transposed{\vec{y}} \cdot \vec{b}$ eine untere Schranke für den Wert einer optimalen Lösung.
|
|
Diese untere Schranke kann folglich mit dem sogenannten dualen LP maximiert werden:
|
|
\begin{align*}
|
|
\max &\quad \zeta(\vec{y}) = \transposed{\vec{b}} \cdot \vec{y}\\
|
|
\text{gemäß} &\quad \transposed{A} \cdot \vec{y} \le \vec{c}\\
|
|
&\quad \vec{y} \ge \vec{0}
|
|
\end{align*}
|
|
\begin{satz}
|
|
Jede zulässige Lösung $\vec{y}$ liefert eine untere Schranke $\zeta(\vec{y})$ für die Zielfunktion $z(x)$ für alle zulässigen Lösungen des Primals.
|
|
Damit gilt die als schwache Dualität bezeichnete Beziehung
|
|
\begin{equation*}
|
|
\zeta(\vec{y}) \le z(\vec{x})
|
|
\end{equation*}
|
|
\end{satz}
|
|
\begin{satz}
|
|
Für optimale Lösungen $\vec{x}_\mathrm{opt}$ des Primals beziehungsweise $\vec{y}_\mathrm{opt}$ des Duals gilt $z(\vec{x}_\mathrm{opt}) = \zeta(\vec{y}_\mathrm{opt})$.
|
|
\end{satz}
|
|
|
|
Man bezeichnet die Differenz zwischen dem Wert einer Nebenbedingung und ihrer Grenze als Schlupf.
|
|
Der primale Schlupf der $j$. Nebenbedingung des Duals ist also $p_j = \row_j\left[A\right] \cdot \vec{x} - b_j$; der duale Schlupf der $i$. Nebenbedingung des Duals $s_i = c_i - \row_i\left[\transposed{A}\right] \cdot \vec{y}$.
|
|
Beträgt der Schlupf 0, so ist die Nebenbedingung scharf.
|
|
|
|
\begin{satz}[Satz vom komplementären Schlupf]
|
|
Seien $\vec{x}$ und $\vec{y}$ zulässige Lösungen des Primals beziehungsweise Duals.
|
|
Sie sind genau dann optimale Lösungen, wenn für alle $i$ und $j$ $y_j \cdot \left(\row_j\left[A\right] \cdot \vec{y} - b_j\right) = 0$ und $\left(c_i - \row_i\left[\transposed{A}\right]\cdot \vec{y}\right) \cdot x_i =0$ gilt.
|
|
Die Bedingung können auch als
|
|
\begin{align}
|
|
y_j > 0 &\Rightarrow \row_j\left[A\right]\cdot\vec{x} = b_j &\text{$j$. Nebenbedingung des Primals scharf}\label{eq:primaler-schlupf}\\
|
|
x_i > 0 &\Rightarrow \row_i\left[\transposed{A}\right] \cdot \vec{y} = c_i &\text{$i$. Nebenbedingung des Duals scharf}\label{eq:dualer-schlupf}
|
|
\end{align}
|
|
formuliert werden.
|
|
Für Approximationsalgorithmen ist vor allem die zweite Aussage wichtig.
|
|
\end{satz}
|
|
|
|
\begin{satz}
|
|
Sei $\Pi$ ein Minimierungsproblem, $I$ eine Instanz von $\Pi$, $X$ das zu $I$ gehörige ILP, $X_\rel$ dessen Relaxierung und $Y_\rel$ das Dual zu $X_\rel$ sowie $\vec{x}$ und $\vec{y}$ beliebige zulässige Lösungen von $X$ bzw. $Y_\rel$, dann gilt:
|
|
\begin{equation*}
|
|
\zeta(\vec{y}) \le \zeta(\vec{y}_\mathrm{opt}) = \opt(Y_\rel) = \opt(X_\rel) = z(\vec{x}_\mathrm{opt}) \le \opt(X) = \opt(I) \le z(\vec{x})
|
|
\end{equation*}
|
|
\end{satz}
|
|
|
|
\subsection{Lineare Programme für \setcover}
|
|
\subsubsection{Primal $X$}
|
|
\begin{align*}
|
|
\min &\quad \sum_{i=1}^{m} x_i\\
|
|
\text{gemäß} &\quad \sum_{i: u_j \in S_i} x_i \ge 1 &\forall u_j \in V\\
|
|
&\quad x_i \in \{0,1\} &\forall i \in \{1,\dots, m\}
|
|
\end{align*}
|
|
|
|
\subsubsection{Relaxiertes Dual $Y_\rel$}
|
|
\begin{align*}
|
|
\max &\quad \sum_{j=1}^{n} y_j\\
|
|
\text{gemäß} &\quad \sum_{j: u_j \in S_i} y_j \le 1 &\forall S_i \in S\\
|
|
&\quad 0 \le y_j \le 1 &\forall j \in \{1,\dots, n\}
|
|
\end{align*}
|
|
|
|
|
|
\subsection{Entwurf neuer Algorithmen für \setcover{} mittels Dual Fitting}
|
|
Beim Dual-Fitting wird allgemein versucht, \Cref{eq:dualer-schlupf} zu erfüllen.
|
|
Zunächst wird dazu eine zulässige Lösung $\vec{y}$ des Duals bestimmt, bei der einige Nebenbedingungen scharf sind.
|
|
Die den scharfen Nebenbedingungen entsprechenden Variablen $x_i$ des Primals werden dann als Approximation auf 1 gesetzt, die anderen auf 0.
|
|
Das so entstandene $\vec{x}$ gibt mit $z(\vec{x})$ eine obere Schranke an.
|
|
Die Qualität der Lösung hängt dabei stark vom ursprünglich bestimmten $\vec{y}$ ab.
|
|
|
|
\subsubsection{\dualpursc}
|
|
\dualpursc{} löst das relaxierte Dual optimal und baut damit eine zulässige 0-1-Lösung für $X$:
|
|
\begin{algorithmic}[1]
|
|
\State bestimme optimale Lösung $\vec{y}$ des relaxierten Duals $Y_\rel$
|
|
\For{$i \in \{1,\dots,m\}$}
|
|
\If{$i$. Nebenbedingung von $Y_\rel$ scharf}
|
|
\State $x_i = 1$ \Comment{mit erfüllter Nebenbedingung folgt $\sum_{j: u_j \in S_i} y_j = x_i$}
|
|
\Else
|
|
\State $x_i = 0$
|
|
\EndIf
|
|
\EndFor
|
|
\State \Return $(x_1,\dots, x_m)$
|
|
\end{algorithmic}
|
|
\begin{satz}
|
|
\dualpursc{} liefert eine Überdeckung der relativen Güte $\Delta_S$ in Zeit $\bigO(m + L(mn, n))$.
|
|
\end{satz}
|
|
\begin{proof}
|
|
Die Ausgabe ist eine Überdeckung, weil bei einer Nichtüberdeckung eines Objekts $u_i$ alle $x_i$ für $S_i \in S$ mit $u_j \in S_i$ gleich 0 wären.
|
|
Dann wäre auch der duale Schlupf der zugehörigen $i$. Nebenbedingung nicht 0 und $y_j$ könnte vergrößert werden.
|
|
Damit ist die ursprüngliche Lösung $\vec{y}$ aber nicht optimal gewesen.
|
|
|
|
Da für jedes $i$ mit $x_i = 1$ gilt $\sum_{j: u_j \in S_i} y_j = 1$, folgt für die Qualität der Lösung:
|
|
\begin{align*}
|
|
\dualpursc(S) &= \sum_{i=1}^{m} x_i = \sum_{i: x_i = 1} 1 = \sum_{i: x_i = 1} \sum_{j: u_j \in S_i} y_j \le \Delta_S \cdot \sum_{j=1}^{n} y_j\\
|
|
&= \Delta_S \cdot \opt(Y_\rel) \le \Delta_S \cdot \opt(S)
|
|
\end{align*}
|
|
\end{proof}
|
|
|
|
\subsubsection{\primaldualscone}
|
|
\primaldualscone{} berechnet jetzt keine optimale Lösung von $Y_\rel$ mehr:
|
|
\begin{algorithmic}[1]
|
|
\ForAll{$y_j$}
|
|
\State $y_j = 1$
|
|
\EndFor
|
|
\For{$i \in \{1,\dots,m\}$}
|
|
\State $x_i = 0$
|
|
\State $\mathrm{dualer\_schlupf}[i] = 1$
|
|
\EndFor
|
|
\While{es ein nicht überdecktes Objekt $u_j$ gibt}
|
|
\State bestimme eine Gruppe $S_i$ mit $u_j \in S_i$ mit minimalem $\mathrm{dualer\_schlupf}[i]$
|
|
\State $x_i = 1$
|
|
\State $y_j = \mathrm{dualer\_schlupf}[i]$ \Comment{$i$. Nebenbedingung scharf: $x_i = \sum_{j: u_j \in S_i} y_j$}
|
|
\ForAll{$i'$ mit $u_j \in S_{i'}$}
|
|
\State $\mathrm{dualer\_schlupf}[i'] = \mathrm{dualer\_schlupf}[i'] - y_j$ \Comment{Aktualisieren des dualen Schlupfs}
|
|
\EndFor
|
|
\EndWhile
|
|
\State \Return $(x_1, \dots, x_m)$
|
|
\end{algorithmic}
|
|
|
|
\begin{satz}
|
|
\primaldualscone{} gibt eine Überdeckung der relativen Güte $\Delta_S$ nach Zeit $\bigO(n\cdot m)$ aus.
|
|
\end{satz}
|
|
\begin{proof}
|
|
Die While-Schleife kann bis zu $n$ mal durchlaufen werden, wobei für die Bestimmung der Gruppe mit minimalem dualen Schlupf jeweils $\bigO(m)$ Schritte benötigt werden.
|
|
|
|
$\vec{y}$ ist zu Beginn eine zulässige Lösung und jeder Eintrag wird nur maximal einmal verändert, also ist auch $\vec{y}$ auch am Ende eine zulässige Lösung. Für die Qualität kann die Rechnung für \dualpursc{} erneut verwendet werden.
|
|
\end{proof}
|
|
|
|
\subsection{Analyse bestehender Algorithmen für \setcover}
|
|
Ein bestehender Algorithmus, der eine 0-1-Lösung des ursprünglichen ILPs $X$ berechnet, wird so erweitert, dass er gleichzeitig eine zulässige Lösung $\vec{y}$ für $Y_\rel$ konstruiert.
|
|
Da $\vec{x}$ und $\vec{y}$ von einander abhängen, hängt auch $z(\vec{x})$ von $\vec{y}$ ab.
|
|
Kann daraus der Wert $\zeta(\vec{y})$ isoliert werden, kann eine obere Schranke des Wertes der Lösung zu $I$ berechnet werden.
|
|
|
|
\subsubsection{\primaldualsctwo}
|
|
Ein bestehender gieriger Algorithmus, der immer die Gruppe wählt, die am meisten noch nicht überdeckte Objekte überdeckt, wird so erweitert, dass man die Dualität der LP zur Analyse verwenden kann.
|
|
Es sei $\mathcal{H}(n) = \sum_{i=1}^{n} \frac{1}{i}$ die $n$. harmonische Zahl.
|
|
Für sie gilt die Ungleichung $\mathcal{H}(n) \leq \ln n + 1$.
|
|
\begin{algorithmic}[1]
|
|
\ForAll{$i\in \{1,\dots, m\}$}
|
|
\State $x_i = 0$
|
|
\EndFor
|
|
\State $C = \emptyset$ \Comment{$C$ enthält die schon überdeckten Objekte}
|
|
\While{$C\neq V$}
|
|
\State bestimme einen Index $i$ mit maximalem $\abs*{S_i \setminus C}$
|
|
\State $x_i = 1$
|
|
\ForAll{$u_j\in S_i \setminus C$}
|
|
\State $p[u_j] = \frac{1}{\abs*{S_i \setminus C}}$ \Comment{$x_i = 1$ und $\sum_{u_j\in S_i \setminus C} p[u_j] = 1$}
|
|
\State $y_j = \frac{1}{\mathcal{H}(G_S)} \cdot p[u_j]$ \Comment{$\mathcal{H}(G_S) \cdot y_j = p[u_j]$}
|
|
\EndFor
|
|
\State $C = C \cup S_i$
|
|
\EndWhile
|
|
\State\Return $(x_1, \dots, x_m)$
|
|
\end{algorithmic}
|
|
|
|
\begin{satz}
|
|
\primaldualsctwo{} liefert eine Überdeckung der relativen Güte $\mathcal{H}(G_S)$ in Zeit $\bigO(n\cdot m)$.
|
|
\end{satz}
|
|
\begin{proof}
|
|
Erneut kann die While-Schleife maximal $n$ Mal durchlaufen werden, und die Bestimmung des Index $i$ kann $\bigO(m)$ Schritte dauern.
|
|
|
|
Zunächst ist zu zeigen, dass $\vec{y}$ eine zulässige Lösung von $Y_\rel$ bildet:
|
|
Betrachte die $i$. Nebenbedingung und die zugehörige Gruppe $S_i = \{u_{j_1},\dots,u_{j_k}\}$, wobei die Objekte in o.B.d.A. genau dieser Reihenfolge durch den Algorithmus überdeckt worden sein sollen.
|
|
Es gilt $k \le G_S$.
|
|
Nun wird die Runde betrachtet, in der $u_{j_l}$ überdeckt wurde.
|
|
Wäre $S_i$ in dieser Runde gewählt worden, wären neben $u_{j_1}$ noch $k - l$ weitere Objekte unüberdeckt.
|
|
Die tatsächlich gewählte Gruppe trifft also noch mindestens $k - l + 1$ Objekte inklusive $u_{j_l}$.
|
|
Damit gilt $p[u_{j_l}] \le \frac{1}{k - l + 1}$ und
|
|
\begin{equation*}
|
|
y_{j_l} \le \frac{1}{\mathcal{H}(G_S)}\cdot \frac{1}{k - l + 1}
|
|
\end{equation*}
|
|
Folglich ist die $i$. Nebenbedingung des Duals erfüllt mit
|
|
\begin{equation*}
|
|
\sum_{l=1}^{k} y_{j_l} \le \frac{1}{\mathcal{H}(G_S)} \cdot \sum_{l=1}^{k} \frac{1}{k - l + 1} = \frac{\mathcal{H}(k)}{\mathcal{H}(G_S)} \le 1
|
|
\end{equation*}
|
|
|
|
Für die ausgegebene Überdeckung gilt
|
|
\begin{equation*}
|
|
\primaldualsctwo(S) = \sum_{i=1}^{m} x_i = \sum_{j=1}^{n}p[u_j] = \mathcal{H}(G_S) \cdot \sum_{j=1}^{n} y_j \le \mathcal{H}(G_S) \cdot \opt(S)
|
|
\end{equation*}
|
|
\end{proof}
|
|
|
|
Mit $G_S \le n$ folgt unmittelbar, die relative Gütegarantie von $\ln n + 1$ von \primaldualsctwo{}.
|
|
\end{document} |