精确和启发式算法：在线算法都是启发式算法

主启发规则(primal heuristic)找到一个可行解I，对偶启发规则找到最优解的下界 $b\leq c(I_{opt})\leq c(I)$

最优间隙(optimality gap)： $c(I)/c(I_{opt})$

对偶间隙(duality gap)： $c(I)/b$

最小化问题的k近似算法找到一个可行解I满足 $c(I)\leq k\cdot c(I_{opt}), k\geq 1$

对一个最小化问题，一个在线算法ALG是c-竞争性的如果ALG对任意请求序列 $\sigma$ 找到一个可行解 $ALG(\sigma)$ 满足 $ALG(\sigma)\leq c\cdot OPT(\sigma), c\geq 1$ ，ALG的竞争性系数(competitive ratio)是保证ALG是c竞争性的所有c的下确界

定理 Olariu1991：当 $\mathcal G(\mathcal I)$ 的节点按左端点升序排序后，贪心算法找到一个区间图(interval graph) $\mathcal G(\mathcal I)$ 的 $\omega(\mathcal G(\mathcal I))$ -染色

定理：旅馆预订问题的在线贪心染色算法是T竞争性的，其中T是总天数

度量任务系统(Metric task system）：一个度量任务系统是一个二元组 $(M,T)$ ，其中 $M=(X,d)$ 是一个度量空间， $T=(\tau_1,\cdots,\tau_n)$ 是任务集合。一个任务 $\tau_i$ 是一个访问特定点 $x_i\in X$ 的请求，或从起点 $x_s\in X$ 到终点 $x_d\in X$ 运输物体的请求。服务器 $server(s)$ 要处理任务集，目标是最小化走过的距离。

TSP是NP-hard问题，有启发规则2-OPT augmentation

定理(Sahni&Gonzalez1976)：设 $H_A$ 为A在 $(K_n,w)$ 中找到的TSP圈。若存在一个多项式的TSP启发规则A和一个常数 $1\leq\alpha<\infty$ 使得对任意TSP实例，有 $w(H_A)\leq \alpha w(H_{opt})$ ，则P=NP

定理(Ausiello 1998)：不存在在线TSP问题的确定性在线算法可以使竞争性系数c<2

定理：在线算法IGNORE和REPLAN在一般度量空间中对在线TSP问题是5/2-竞争性的

定理：存在在线算法在一般度量空间中对在线TSP问题有c=2的竞争性系数

定理(Manasse, McGeoch and Sleator1998)：对任意度量空间，在线kSP的竞争性系数至少为k

定理(Bsaybes, Quilliot, Wagler2018)：出租车问题(紧时间窗口，服务器容量为1的DARP)可以在多项式时间解决

推论：不存在在线PDP(Pickup & delivery)问题的确定性在线算法可以在一般度量空间上使竞争性系数c<2

定理(Ascheuer, Krumke, Rambau1998)：在线算法IGNORE和REPLAN对服务器容量C=1的在线PDP问题是5/2-竞争性的

定理：存在在线算法对服务器容量C=1的在线PDP问题有c=2的竞争性系数

定理(Bsaybes, Quilliot, Wagler2018)：对在线出租车问题，不存在竞争性的在线算法

带重分配的最大接收(Max-Accept Relocation Problem)问题：

  • 边a的权重 $w_a$ 即司机沿a移动的消耗，节点v的权重 $c_v$ 即车站的容量。 $x^t\in \mathbb Z^n$ 表示在 $t\in[0,T]$ 时刻每个车站的负载状况
  • 输入：由加权图G=(V,E,c,w)诱导的度量空间M=(V,d)和G中的一个计算旅行时间的最短路径度量d。初始状态每个车站 $v\in V$ 的汽车和司机个数 $x_v^0$ 。司机总数k，车队最多汽车数C(可拖车)。顾客预订的请求序列 $\sigma=(r_1,\cdots,r_h)$ ，接收请求 $r_i$ 的利润 $p_i$ 。
  • 输出：是否拒绝 $\sigma$ 中的请求，一个重分配汽车的计划
  • 目标：最大化利润，最小化重分配汽车的消耗

离线带重分配的最大接收问题对应一个时间展开重分配网络(time-expanded relocation network) $N_{rel}(\sigma)=(V,A)$ ，$V=s^+\cup\{(v,t):v\in V,t\in [0,T]\}\cup s^-$ ， $A=A_+\cup A_P \cup A_\sigma \cup A_L \cup A_-$ ，其中源边(source arc) $(s^+\to (v,0))\in A_+,\forall v\in V$ ，停车边(park arc) $((v,t)\to (v,t+1))\in A_P, \forall v\in V,t\in [0,T)$ ，请求边(request arc) $((v^{pick}_i,t^{pick}_t)\to(v^{drop}_i,t^{drop}_i))\in A_\sigma,\forall r_i\in\sigma$ ， 重分配边(relocation arc)$若 d(v,v')=t'-t, ((v,t)\to(v',t'))\in A_L$ 表示所有重分配车队的移动，漏边(sink arc) $((v,T)\to s^-)\in A_-,\forall v\in V$

因此离线带重分配的最大接收问题被转化为了此网络上汽车流f和司机流F的耦合最大流(coupled flows)问题，得到ILP：

$\max \sum_{a\in A_\sigma} p_a f_a - \sum_{a\in A}w_a F_a\\ s.t.\ \sum_{a\in \delta^+(s^+)} f_a=x^0_v, \sum_{a\in \delta^+(s^+)} F_a=x^0_v\\ \sum_{a\in \delta^-(v,t)} f_a=\sum_{a\in \delta^+(v,t)} f_a,\sum_{a\in \delta^-(v,t)} F_a=\sum_{a\in \delta^+(v,t)} F_a,\forall(v,t)\\ f_a\leq c_v,\forall a\in A_P\\ f_a\leq 1, F_a\leq 0, \forall a\in A_\sigma\\ f_a\leq CF_a,\forall a\in A_L\\ f_a\in \mathbb Z_+,F_a\in\mathbb Z_+,\forall a\in A$

推论：无重分配(relocation)的离线最大接收问题(Max-Accept Problem)可在多项式时间内解决

推论：有重分配的离线最大接收问题是NP-hard问题

定理(KARP1972)：判断一个给定的图G是否有一个使用k个颜色的涂色是NPC问题

定理(Chudnovsky2004)：一个图是完美(perfect)的当且仅当它不包含奇数洞(odd holes) $C_{2k+1}$ 或奇数逆洞(odd antiholes)$\bar C_{2k+1}$， $k\geq 2$ 作为诱导(induced)子图。

引理：对任意图G，有 $\chi(G)\leq\Delta(G)+1$ ，其中 $\Delta(G)$ 是G的最大度数

定理(Brooks1941)：如果G不是一个团(clique)或无弦的奇环路(chordless odd cycle)，则 $\chi(G)\leq \Delta(G)$

区间颜色数(Interval chromatic number)：给定节点加权的图G=(V,E,w)，和一个区间染色 $\mathcal I$，此区间染色的长度(span)定义为 $s(\mathcal I)=\max\{ r(v): v\in V\}-\min\{ l(v): v\in V\}$ 。所有区间染色的最小长度是它的颜色数，记为$\chi_\mathcal I (G,w)$

区间染色问题(Interval coloring problem)：给定节点加权的图G=(V,E,w)，找到一个区间染色(interval coloring) $\mathcal I$ 使长度为 $\chi_\mathcal I (G,w)$

定理(Kubale)：判断一个图是否有一个长度为k的区间染色是NPC问题

加权团数(weighted clique number)：考虑一个加权的图G=(V,E,w)，则加权团数是 $\omega(G,w)=\max\{w(Q):Q\subseteq G\ clique\}\leq\chi_{\mathcal I}(G,w)$ ，它是图G的区间颜色数(chromatic number)的下界

超完美图(super-perfect graph)：若图G=(V,E,w)的任意诱导子图 $G'\subseteq G$ 和任意整数权重w，都有 $\omega(G',w)=\chi_{\mathcal I}(G',w)$

结论：频率分配问题(Frequency allocation problem)是一个特殊的区间染色问题

引理(Marenco, Wagler2007)：频率分配问题存在DegreeGreedy，DemandGreedy，CombinGreedy，RandomGreedy等启发规则和ENUMERATOR的精确解

标签: none

评论已关闭