<aside>

一般而言，算法要求

• 最优解 Solve problem to optimality
• 多项式时间 Solve problem in poly-time
• 对任意实例可行 Solve arbitrary instances of the problem

而（针对NP-hard问题的）近似算法，必须要进行舍弃

</aside>

启发式 ，$\\rho$-近似算法 ，

• 最优解→ 某种解（例如，启发式-最坏解没保证）

⇒ need to prove a solution’s value is close to optimum

• Load Balancing 调度问题

<aside>

（取最小问题）近似算法尝试寻找获得最小下界的算法，进而估计最优解；

即$\rho$ 越接近一越好

</aside>

• Center Selection Problem

The Pricing Method

• weighted vertex cover

  2-近似算法 ← 点半径覆盖

  weighted vertex cover-》 pricing method 竞价法→ 2-近似算法

  点覆盖要求每个边至少一个 端点被选中，竞价法在每条边上定义不大于端点weight的权值，并在任意边上取最大权值以使得两端点至少一个tight（$\sum_{(i,j)}p_e=w_i$），循环操作直至无法继续，tight node 构成一个weight vertex cover 问题的解

  这种方法是 2-近似算法：首先，算法终止时，tight构成vertex cover；其次，所有边的权值和小于等于任何一种 vertex cover构成的权值分布，因为边的两端点至少被计入一次

  $$ \sum_Ep_e\le \sum_{i\in S}\sum {(i,j)}p_e\le \sum{i\in S}w_i=w(S) $$

  最后，算法终结时每个vetex cover点是紧的

  $$ w(S)=\sum_{i\in S}w_i=\sum_{i\in S}\sum_{(i,j)}p_e $$

  两倍近似的关系就容易得出，S→V的过程将每个边计算两边E

Linear Programming Rounding

• LP rounding

  • simplex method [Dantzig 1947] Can solve LP in practice. 极端下 指数算法，滕少华（平滑度分析）
  • ellipsoid method [Khachian 1979] Can solve LP in (weakly) poly-time.

  ---

  Weight vertex cover → Integer programming formulation + 四舍五入

PTAS 方法

<aside>

Polynomial Time Approximation Scheme

</aside>

knapsack problem 背包问题的近似算法 quasi-polynomial→

• PTAS←(1+\epsilon)-approx.

  • load balancing [Hochbaum-shmoys 1987]

    authorized machine $M_j\subset M$ and each machine can process at most one job at at time.

    job $J$

    load of machine i$L_i=\sum_{j\in J(i)}t_i$

    makespan = $\max l$

    $x_{ij,j\in J,i\in M}=\{0,t_j\}$ 机器要么运行j,要么不运行j ILP整数线性规划⇒LP

    $x_{i\notin M_j,j}=0$ 该机器不能运行j

    ---

    proof

    区分叶子节点和非叶子节点的machine/job, 树可消去圈且不改变机器工作总时间(lp拆分时可以合并)

    2-approx. no3/2-approx.

    ---

    more general problem: 每一个工作在每台机器上被处理时间不同.→ 作业3

  • Euclidean TSP [Arora 1996]

  • Knapsack

    FPTAS→ 比例放缩→ $\epsilon$ 近似

    $$ \bar v=\lceil\frac{v}{\theta}\rceil\theta $$

    近似解 近似度$\epsilon$

    $$ (1+\epsilon)\sum_{i\in S} v_i\ge \sum_{i\in S^*} v_i $$

    取$n\theta=\epsilon v_{max}\le\epsilon\sum _{i\in S}v_i$，即每个点误差至多$\theta$，取为以上不等式的一个放缩因子。

    ⇒ $O(\frac{n^3}{\epsilon})$

Generalized Load Balancing

m machines, n jobs, Job j only run contiguously on an authorized machine in $M_j\subset M$