平面图上的PTAS（Polynomial Time Approximation Scheme）

PTAS（英语：Polynomial Time Approximation Scheme）是一种用于（通常是困难的）问题的近似算法，它有一个大于0的值$ε$作为参数，并输出一个解，在最小化问题中不超过最优解的$(1 + ε)$倍，在最大化问题中至少是$(1 - ε)$倍。重要的是，算法的运行时间必须是关于$n$的多项式。

Baker方法

1994年，Baker开发了一种用于设计平面图上各种困难问题的PTAS的技术[^1]。主要执行以下步骤

1. 将输入图分成k个外部平面环（其中$k=1/ε$）
2. 通过树分解和动态规划在每一个环上计算最优解
3. 将最优子解组合成近似整体解

项目描述

在此项目中，实现了Baker方法。 这里 讨论了处理平面图和平面嵌入所使用的数据结构和算法。 这里 描述了PTAS各个步骤的算法。运行时间测试的概述可以在 这里 找到。

[^1]: BAKER, BRENDA S. 1994. Planar Graphs NP-Complete Problems Approximation Algorithms, J. ACM 41, January 1994, pp 153-180

CLI工具

创建

要构建CLI工具，可以使用以下命令

cargobuild --release --features="cli"

使用

CLI工具可以使用以下方式使用

• ./target/release/graph-algo-ptas-cli <选项>
• 或者 cargo run --release --features="cli" -- <options>（在这种情况下不需要cargo build）

USAGE:
    graph-algo-ptas-cli [OPTIONS] [SUBCOMMAND]

OPTIONS:
    -g, --generate <n>    Generate Random graph with n vertices
    -h, --help            Print help information
    -i, --input <FILE>    File in dot format to read input graph from
    -V, --version         Print version information

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