Ein PTAS (engl.: Polynomial Time Approximation Scheme) ist ein Approximationsalgorithmus für ein (meist schweres) Problem, der einen Wert $ε > 0$ als Parameter hat und eine Lösung ausgibt, die bei Minimierungsproblemen höchstens $(1 + ε)$-Mal und bei Maximierungsproblemen mindestens $(1 - ε)$-Mal so groß wie die Optimallösung ist. Wichtig ist, dass die Laufzeit des Algorithmus polynomiell in $n$ sein muss.
Eine Technik zum Entwurf von PTAS für verschiedene schwere Probleme auf planaren Graphen wurde 1994 von Baker entwickelt [^1]. Im Wesentlichen werden folgende Schritte durchgeführt:
Im Rahmen dieses Projekts wurde Bakers Ansatz implementiert. Hier wird auf die verwendeten Datenstrukturen und Algorithmen zum Umgang mit planaren Graphen und planaren Einbettungen eingegangen. Hier werden die die Algorithmen für die einzelnen Schritte des PTAS beschrieben. Eine Übersicht über die durchgeführen Laufzeittests ist hier zu finden.
Um das CLI Tool zu bauen, kann folgender Befehl verwendet werden:
cargo build --release --features="cli"
Das CLI Tool kann hiernach folgendermaßen verwendet werden:
./target/release/graph-algo-ptas-cli <options> cargo run --release --features="cli" -- <options> (Hierbei wird cargo build nicht benötigt.)Dabei können folgende Optionen angegeben werden:
```sh USAGE: graph-algo-ptas-cli [OPTIONS] [SUBCOMMAND]
OPTIONS:
-g, --generate
SUBCOMMANDS: embed Generates an embedding for the graph help Print this message or the help of the given subcommand(s) independent-set Calculates Maximal Independent Set (Default) print Prints the generated/input graph vertex-cover Calculates Minimal Vertex Cover ```
:warning: Hierbei ist zu beachten, dass die Option
-g <n>oder-i <FILE>immer angegeben werden muss.
Zur Verwendung dieser Crate muss einfach nur graph-algo-ptas zur cargo.toml hinzugefügt werden. Eine Dokumentation aller zur Verfügung stehenden Funktionen befindet sich hier.