一些動態幾何問題的流式演算法

本文為 STOC'04 Algorithms for Dynamic Geometric Problems over Data Streams 的閱讀筆記，

論文作者 Piotr Indyk， 研究領域：高維幾何問題, 流式演算法，摘要資料結構維護, 稀疏傅立葉變換，

1 近似演算法

在假設 \(\text{P}\neq\text{NP}\) 的情況下，近似演算法一般針對 NP 最優化問題(NPO)，有兩點要求

• 演算法 \(M\) 是確定性或者隨機的多項式演算法，

• 演算法近似界限 \(r\) 要盡可能低，

  \[r(n)=\sup_{x\in X,|x|=n}\left\{\max\left\{\frac{M(x)}{M'(x)},\frac{M'(x)}{M(x)}\right\}\right\} \]

  其中 \(M'\) 為最優解演算法，\(X\in\text{NPO}\)，

通過 \(r(n)\) 可以定義一系列近似復雜度類，例如 \(f(n)\text{-APX}\) 表示存在近似演算法 \(M\) 使得 \(r(n)\in O(f(n))\) 的問題集合，

一般來說 \(O(1)\text{-APX}\)(可以簡寫為 \(\text{APX}\)) 演算法比較常見，

• \(\texttt{MAX-3SAT}\) 問題有一個 \(r=\frac{8}{7}\) 的演算法，并且在 Some Optimal Inapproximability Results(1999) 這篇論文中指出，如果存在 \(\epsilon>0\)，\(r=\frac{8}{7}-\epsilon\) 的多項式演算法，則 \(\text{P}=\text{NP}\)，

還有一些問題問題，存在演算法可以無限逼近最優解，但是越逼近時空開銷越大，所以有 \(\text{PTAS}\subset \text{APX}\)，若對于任意 \(\epsilon>0\), \(\exists\) 時間復雜度為 \(O(f(n,1/\epsilon))\) 的演算法，\(f\) 是 \(n\) 的多項式，\(r<1+\epsilon\)，若 \(f\) 為 \(n\) 和 \(1/\epsilon\) 的二元多項式，則為 \(\text{FPTAS}\)，

有時候，若得到的概率分布滿足為

\[P\left(\frac{|M(x)-M'(x)|}{M'(x)}>\epsilon\right)\le \delta \]

近似演算法的演算法復雜度可能涉及三個引數 \(n\), \(1/\epsilon\), \(1/\delta\)，

一般來說常見的近似演算法是貪心等基本的組合演算法，另一類常見的演算法是規約到線性規劃然后采用隨機擾動(rounding)，原始對偶，線性松弛等，

另一類研究的比較少的近似演算法，是針對 \(\sharp P\) 計數問題，常用的方法是馬爾可夫鏈蒙特卡洛方法，

2 流式演算法

流式演算法適用的問題一般比 \(\text{NPO}\) 簡單，大多數是 \(\text{PO}\) 內，但是空間不足以存下之前的輸入或者要求強制在線，需要維護一個摘要或者采樣的演算法，所以很難得到精確解，同樣需要借用用近似演算法的評價標準，

早期流式演算法研 究為一些簡單的統計量的維護：

1. 中位數. 普遍情況是求第 \(k\) 小，
   流式演算法最早研究 Selection and sorting with limited storage（1978），

   文中介紹了一個隨機資料下空間復雜度為 \(\theta(n ^{1/2})\) 錯誤率極低的流式隨機演算法，
   文章還嚴格證明了 \(p\) 次重復讀入的確定性演算法空間復雜度上下界 \(\Omega(n^{1/p})\) 和 \(O(n^{1/p}\log^{2-2/p} n)\)，

2. 不同元素個數 \(F_0\)，普遍地有 k 階頻率矩 \(F_k=\sum\limits_x f(x)^k\).
   The space complexity of approximating the frequency moments(1996)

   文章證明了 \(F_0, F_1, F_2\) 存在 \(O(\log n)\) 空間的逼近演算法，用通信復雜度證明了 \(F_k(k\ge 6)\) 則需要 \(n^{\Omega(1)}\) 的空間，
   文章用到了均勻采樣，隨機變數，切比雪夫不等式，切爾諾夫界等概率論工具，以及通信復雜度，將流式隨機演算法的研究形式化，并且將這些工具廣開來成為現在的主流研究方法，可以算這個領域的開山之作，
   文章構造了 \(2\log(1/\delta)\) 個隨機變數 \(Y_i\)，\(E(F_k)=E(\overline{Y_i})\)，然后 \(Y_i=\overline{X_{ij}}\) 為 \(8kn^{1-1/k}/\epsilon^2\) 個隨機變數的均值，\(X\) 為互相獨立的均勻采樣集生成的隨機變數，方法為 \(X=m(r^k-(r-1)^k)\), \(r=|\{q|q\ge p,a_p=a_p\}|\)，其中 \(p\) 為隨機抽樣的下標，維護這樣的 \(X\) 和 \(Y\) 空間復雜度為 \(O\left(\frac{k\log(1/\delta)}{\epsilon^2}n^{1-1/k}(\log n+\log m)\right)\)，
   文中用切比雪夫不等式證明了單個 \(Y_i\) 相對誤差大于 \(\epsilon\) 的概率小于 \(\frac{1}{8}\)，根據切爾諾夫界，可以的到 \(2\log(1/\delta)\) 個 \(Y_i\) 的平均值的越界概率小于 \(\delta\)，文章針對 \(F_2\) 設計了專門的隨機變數，得到了更優的結果，

   隨機變數估計的一個另一個更早的例子是，Probabilistic counting(FOCS,1983) 中提出演算法，\(E(\log F_0)=E(\max(\text{lowbit}(\text{hash}(x))))\)，將統計量 \(F_0\) 用 \(\max(\text{lowbit}(\text{hash}(x)))\) 進行無偏估計，然后用一些概率論的技巧計算出其錯誤率，然后用 Median trick 可以降低錯誤率，

在后續的研究中有人引入和穩態分布和隨機投影，

2.1 采樣

采樣最早是從統計學和資料科學中發展來的方法，看起來很簡單，但是合理的采樣方法可以在流式演算法中起到出乎意料的作用，

• 用蒙特卡羅方法計算復雜函式的積分或期望，利用均勻分布或其他簡單分布生成隨機變數，然后用樣本均值近似真實值，
• 用接受-拒絕抽樣或重要性抽樣方法生成難以直接采樣的分布的樣本，利用一個容易采樣的分布作為提議分布，然后根據一定的準則接受或拒絕樣本，或者給樣本賦予不同的權重，
• 用馬爾可夫鏈蒙特卡羅方法生成難以直接采樣的分布的樣本，利用一個馬爾可夫鏈逐步逼近目標分布的穩態分布，然后從穩態分布中采樣，

2.2 隨機投影

隨機投影是高維問題中經常使用的方法，The Johnson-Lindenstrauss 引理指出高維空間中的一小部分點可以以點之間的距離幾乎被保留的方式嵌入到低維空間中，

通常的方法是把一些高維的范數分解成多個一維和二維的穩態分布來近似，

3 流式問題復雜度上下界證明

3.1 通信復雜度

通信復雜度研究的是，將一個問題的輸入劃分到兩個或多個圖靈機，假設所有圖靈機有無窮的計算能力且彼此互信，協議相同，求解決問題需要傳輸的最小位元量與輸入規模之間的關系，

一個經典的協議是，兩臺圖靈機可以在傳遞 \(O(\log n)\) 個位元的情況下，計算出輸入的中位數，

通信復雜度在很多領域例如計算復雜性理論，量子淺層析
的采樣復雜度下界，電路復雜度下界等領域有重要的作用，

在資料結構空間下界和流式演算法空間下界中的應用方法一般是

一種方法是將流式問題轉化為分布式問題，即將資料流分配給多個參與者，讓他們各自處理自己的資料，并且在必要時進行通信，最后輸出結果，這樣，流式問題的記憶體空間限制就變成了分布式問題的通信限制，
另一種方法是使用資訊論的工具，即將資料流看作是隨機變數，利用熵、互資訊等概念來量化流式問題中所需的資訊量，從而得到通信復雜度的下界，

3.2 可壓縮性分析

可壓縮性分析的核心思想是將流式演算法與有限狀態自動機(DFA) 建立關系，利用 Myhill–Nerode 定理來尋找輸入的等價類數目，確定 DFA 可壓縮的下界從而刻畫出流式演算法空間復雜度的下界，

Stanford University CS154 的 Note 中使用這種方法重新將頻率矩 \(F_k\) 下界復雜度的結論證明了一遍，

3.3 規約

規約是在計算復雜性理論和精細復雜度領域常用的非常技巧，

4 動態幾何問題

4.1 離散高維度量空間

本文研究的問題是在離散 \(d\) 維度量空間 \(D=\{1\cdots\Delta\}^d\) 中動態加點或刪點，維護點集的一個函式，其中中點之間的距離被定義為閔可夫斯基范數 \(d(x,y)=\left(\sum\limits_{i=1}^d|x_i-y_i|^p\right)^{1/p}\)，其中 \(\Delta\) 表示不同元素的個數，

這類問題首先在論文 The Geometry of Graphs and Some of its Algorithmic Applications(1994) 中被探討，文章提出了一些高效演算法，在低維度量空間中以很小的失真嵌入圖，將一些圖上難解的問題例如直徑，最小割問題轉化為幾何問題，使用更高效的近似演算法來解決，

Probabilistic approximation of metric spaces and its algorithmic applications(1996) ，這篇文章提出了任何度量空間都可以分層良分樹(HST)以 polylog 失真概率近似，

在 Approximating a finite metric by a small number of tree metrics(1998)，這篇文章中使用了線性規劃這種確定性演算法構造了大小為 \(O(n\log n )\) 的 HST，使得每條邊期望失真不超過 \(O(\log n \log \log n)\)，

本文同樣使用了 HST，介紹了幾個高維度量空間問題的流式演算法，

4.2 最小生成樹問題

Approximating the minimum spanning tree weight in sublinear time(2001) 文中給出了圖上最小生成樹的亞線性任意近似演算法，時間復雜度為 \(O(\frac{dw}{\epsilon^2}\log\frac{d}{\epsilon})\)，接近下界 \(\Omega(\frac{dw}{\epsilon^2})\)，其中 \(d\) 為點的平均度數，\(w\) 為邊權集合的大小，

The sensor spectrum: technology, trends, and requirements(SIGMOD, 2003) 中對傳感器網路通信代價的研究揭示了高維幾何中最小生成樹問題的實用意義亞線性任意近似演算法，時間復雜度為 \(O(\mathrm{polylog}(n/\epsilon^{O(1)}))\).

同年 Estimating the Weight of Metric Minimum Spanning Trees in Sublinear-Time(2003) 文中的到了高維幾何(度量空間)中中最小生成樹問題的

基于前面文章的作業，在 Estimating the weight of euclidean minimum spanning trees in data streams(2004) 中提出了只支持插入情況下，最小生成樹問題的任意逼近流式演算法，

本文對這個問題得到了在同時支持插入和洗掉操作的情況下以 \(r=O(d\log \Delta)\) 逼近，空間為 \(O(d\log^2\Delta)\) 的流式演算法，

Chen, Jayaram, Levi, Waingarten 將這個問題改進到 \(r\le 1.10\)，空間為 \(\Omega(\sqrt{n})\)，

4.3 匹配問題

空間中匹配問題分為兩種

• 無色匹配(Minimum Weight Matching)
• 雙色匹配(Minimum Bi-chromatic Matching)

本文作者指出 Similarity estimation techniques from rounding(1996) 這篇文章的方法足以解決雙色匹配問題，

本文給出了無色匹配的 \(r=O(d\log \Delta)\)，空間為 \(O(d\log^2\Delta\log\log\Delta)\) 的演算法，

文中提到，經過仔細分析，可以做到 \(r=1+\epsilon\)，且空間復雜度只乘上 \(O(1/\epsilon^2)\) 因子的演算法，但是沒有在本文列出，

4.4 工廠選址問題

這類問題由在鐵路上的傳感器通信問題發展而來，

本文給出了一個 \(r=O(d\log^2\Delta)\)，空間為 \(O(d^2\log^2\Delta)\) 的演算法，

在 Streaming Facility Location in High Dimension via New Geometric Hashing(2022) 中，提出了一種基于重要性采樣的演算法，改進到了雙次掃描 \(r=O(1)\)，空間為 \((d\log \Delta)^{O(1)}\)，單次掃描 \(r=O(d/\log d)\)，同時這篇文章給出了一種空間為 \(O(n^{1/\epsilon})\) 的任意近似演算法，

4.5 k-聚類問題

k-聚類問題是幾何問題中非常經典的 NPO 問題，在機器學習等眾多領域有著很重要的作用，已經有眾多有效的啟發式演算法和近似演算法，

在作者所在的時間，已經提出了 \(r=3+\epsilon\)，時間為 \(O(n^{1/2\epsilon})\) 的非流式演算法，目前最優的逼近比是 \(r=2.406\)，由 Improved approximations for Euclidean k-means and k-median, via nested quasi-independent sets(2022) 文中提出，

本文使用了多種工具和演算法例如互斥計數，中點成本估計，本地搜索，貪心等，分別做到了不同的復雜度，

在 The Power of Uniform Sampling for k-Median(2023) 中，作者分析了樸素的均勻采樣的方法，如果要達到 \(r=O(1)\)，則采樣率至少為 \(\Omega(1/\beta)\)，\(\beta\) 為均勻度，如果要達到任意近似，則至少達到 \(O(\mathrm{poly}(k/\epsilon\beta))\) 采樣率，

5 科技

5.1 嵌入分層良分樹(HST)

如果一個有根樹 \(T\) 是 k-HST，則滿足

• 每個節點到所有子節點的距離相等
• 從根到葉子節點的路徑上，邊權至少以 \(k>1\) 的比例持續減少，

一個 HST 上的度量空間可以定義為其上所有葉節點，而度量為葉節點之間的最短路，

本文參考了前人的結論，任意 \(\{1\cdots\Delta\}^d\) 的子集 \(P\) 上的度量可以被嵌入一系列 2-HST 度量的概率組合，且失真率小于 \(O(d\log\Delta)\)，

文中以該隨機演算法構建 2-HST

首先對 \(P\) 中所有點增加一個隨機偏移 \(\Delta p\in [0,\Delta]^d\)
樹分為 \(\log\Delta +2\) 層 \(G_0,\cdots, G_{\log\Delta+1}\)，

• \(G_0\) 為 \(P\) 中的點為葉節點，\(G_{\Delta +1}\) 表示根節點，
• \(G_i\) 表示包含了 \(P\) 中點的大小為 \(2^{i-1}\) 的網格，
• \(G_i\) 與 \(G_{i+1}\) 之間按包含關系連邊，邊權為 \(2^i\)，

5.2 規約到高維向量統計問題

這是本文創新提出的方法，令統計量 \(\pi_S(c)\) 表示點集 \(S\) 落在網格 \(c\) 中的數量，這種統計量前人已經研究的很多了，本文用這個統計量的組合來逼近要求的問題，將近似最優化問題轉化為 \(\log\Delta\) 個近似計數問題，

• 最小雙色匹配近似為 \(\sum\limits_{i=1}^{\log\Delta}2^i\left(\sum\limits_{c\in G_i}|\pi_R(c)-\pi_B(c)|\right)\)，其中 R, B 為兩種顏色的點集，
• 最小生成樹近似為 \(\sum\limits_{i=1}^{\log\Delta}2^i\left(\sum\limits_{c\in G_i}[\pi_P(c)>0]\right)=\sum\limits_{i=1}^{\log\Delta}2^i|G_i|\)，
• 最小匹配近似為 \(\sum\limits_{i=1}^{\log\Delta}2^i\left(\sum\limits_{c\in G_i}[\pi_P(c)\equiv 1\pmod 2]\right)\)，
• 工廠選址問題最小代價近似為 \(\sum\limits_{i=1}^{\log\Delta}\left(\sum\limits_{c\in G_i}\min\{2^i\times\pi_P(c),f\}\right)\)，\(f\) 是每個工廠自身的代價，
• 給定方案的 k-聚類問題的代價近似為 \(\sum\limits_{i=-i_0}^{\log\Delta}(r_{i}-r_{i-1})\left(\sum\limits_{c_i\cap B(Q,r_i)=\emptyset}\pi_P(c_i)\right)\)，其中 \(r_i=(1+\epsilon)^i\)，\(c_i\) 的直徑為 \(\epsilon/\sqrt{2}\times(1+\epsilon)^i\)，\(i_0=O(\log(1/\epsilon)/\epsilon)\)，\(B(Q,r)\) 表示 \(Q\) 中所有點為中心，半徑為 \(r\) 的高維球區域，

6 演算法

6.1 MST

由 Lemma7.1 可以把問題轉化為求 \(w(T)\)，通過定義和恒等變換，很容易得到 5.2 中的式子，

考慮統計每個 \(|G_i|\)，發現可以等價為統計不同元素的個數 \(F_0\)，根據前人的結論可以做到 \(O(\log(n+\Delta^d))=O(d\log\Delta)\) 空間，于是總的空間為 \(O(d\log^2\Delta)\)，

6.2 MWM

根據 Lemma7.2 可以把問題轉化為 \(\log\Delta\) 個 Odd Count 問題，

維護長度為 \((\frac{\Delta}{2^i})^d\) 的陣列 \(x_i\)

• \(\text{Update}(i,c)\) : \(x_i\leftarrow x_i+c,(c\in\{1,-1\})\)
• \(\text{OddCount}\) : return \(\sum [x_i\equiv 1\pmod 2]\)

文中提出了一種 \(r=O(1)\)，空間復雜度為 \(O(\log\Delta)\) 的演算法，有常數概率出錯，如果將演算法并行運行 \(O(\log\log\Delta)\) 取均值，可以做到超出界限的概率無限減小變為 \(\frac{1}{2\log\Delta}\)，

文章首先構造了一個概率判定演算法

M="On input \(OC,T\)，\(OC\) 是一個流式 Odd Count 問題，\(T\) 是引數

1. 初始以 \(1/T\) 的等價概率選取 \(x\) 下標的一個子集 \(R\)， \(s\leftarrow 0\)，
2. \(\text{Update}(i, c)\)，如果 \(c\in R\), \(s\leftarrow 2 -s\)，
3. \(\text{OddCount}\) : 輸出 \(s\) 是否為 \(1\)，

這個演算法滿足（證明見 Lemma7.3）

• 如果真實 \(OC>T\) 則以不小于 \(1/3\) 的概率輸出 YES，
• 如果真實 \(OC<T/10\) 則以不大于 \(1/10\) 的概率輸出 YES，

通過作者本人之前的文章 pseudorandom generators, embeddings and data stream computation(2000) 中給出的方法，可以用偽亂數生成器以 \(O(d\log \Delta)\) 的空間存盤這個隨機集合，

本文后續沒有介紹如何通過判定問題近似演算法推出計數問題的演算法，推測是等比構造了 \(\log \Delta\) 個 \(T\) 將近似比約束在 \(O(1)\) 的范圍內，然后偽亂數可以在不同的并行運算中復用，
總空間復雜度為 \(O(d\log^2\Delta\log\log\Delta)\)，近似度為規約到 HST 的 \(O(d\log\Delta)\)，

6.3 工廠選址

根據 Lemma7.4，工廠選址問題可以以 \(O(d\log^2\Delta)\) 的近似度規約到 \(\log\Delta\) 個 Bounded Count 問題

維護 \((\frac{\Delta}{2^i})^d\) 個點集 \(S_x\)，

• \(\text{Add}(x,p)\): \(s_x\leftarrow s_x\cup\{p\}\)，
• \(\text{Delete}(x,p)\): \(s_x\leftarrow s_x/\{p\}\)，
• \(\text{BoundedCount}\): return \(\sum\limits_{x}\min\{|S_x|,T\}\)，\(T\) 是引數，

文章對 Bounded Count 給出的演算法是用偽亂數生成器構造了一個值域為 \(T\) 的哈希函式 \(h\)，然后從用這個哈希函式從流中等價采樣了 \(1/T\) 種不同的值，一旦任意一個值落入某個集合，則這個集合按滿的答案 \(T\) 算，這樣問題便轉化為了求不同元素 \(F_0\)，這種轉化可以保證失真在 \(O(1)\) 內，證明見 Lemma7.5，

在作者自己之前的論文中指出，生成隨機哈希函式的偽亂數生成器需要消耗 \(O(\log^2 M)\)，在 \(\log\Delta\) 個并行運算中這些可以復用，總空間復雜度為 \(O(d^2\log^2\Delta)\)，

6.4 k-聚類的搜索演算法

根據 Lemma7.6，存在 \(r=(1+\epsilon)\) 的近似演算法，針對給定的中心點求出 k-median 的代價，

區域搜索也稱為爬山法，是一種很常見的啟發式演算法，缺點是容易陷入區域最優解，

本文參考了 Local search heuristics for k-median and facility location problems(2002) 中的結論證明了在 k-median 問題上區域搜索可以做到 \(r=5\)，

再引入計算代價的失真，總體可以做到 \(r=5+\epsilon\)，空間復雜度 \(O(k\cdot\mathrm{polylog}(\Delta))\)，

如果換成全域搜索可以做到 \(r=1+\epsilon\)，

6.5 k-聚類的貪心演算法

貪心法的思路很簡單，初始讓集合為空，每次選擇使得代價減少最多的點，

文中為了降低復雜度，對貪心做了一些優化，

7 證明

Lemma7.1

若 MST 為 \(\mathcal{T}\)，生成的 HST 為 \(T\), \(\frac{w(T)}{w(\mathcal{T})}\le O(d\log\Delta)\)，

因為 HST 的兩點距離不大于原來兩點距離的 \(O(d\log\Delta)\) 倍

\[w(T)\le\sum_{u,v\in\mathcal{T}}d_T(u,v)\le O(D\log\Delta)w(\mathcal{T}) \]

Lemma7.2

HST 上最小匹配等于 \(n+\sum\limits_i^{\log\Delta}2^im_i\)，\(m_i\) 為 \(G_i\) 的 odd count.

考慮 HST 上每個節點到父節點的邊經過的次數，容易發現，如果經過次數大于 \(1\) 次可以將這兩組匹配交叉使得答案更優，所以最多經過一次，且僅當子樹葉子節點數量為奇數時才需要，

Lemma7.3

6.2 中的判定性問題滿足其中提到的概率條件，

本文參考了 Efficient search for approximate nearest neighbor in high dimensional spaces 中的 Lemma2.1 證明方法，表示兩者相似，

Lemma7.4

如果 HST 上工廠選址問題最優代價是 \(C\)， \(Q=\sum\limits_{i=1}^{\log\Delta}\left(\sum\limits_{c\in G_i}\min\{2^i\times\pi_P(c),f\}\right)\) 是 \(C\) 的一個 \(O(\log\Delta)\) 近似，滿足

\[C\le Q+f\le C\log\Delta+f \]

首先，構造一個代價為 \(Q+f\) 的方案，在根節點放一個工廠，然后對所有 \(2^i\times\pi_P(c)\ge f\) 的節點放置一個工廠，這樣的代價為 \(C'\)，\(C\le C'<Q+f\)，
對于等式的另一邊，容易知道對于每一層 \(\sum\limits_{c\in G_i}\min\{2^i\times\pi_P(c),f\}\le C\)，所以總共 \(\log\Delta\) 層加起來小于 \(C\log\Delta\)，

Lemma7.5

6.3 中的演算法是 Bounded Count 的 \(O(1)\) 近似演算法，

若 \(K\) 表示有最終統計出的不同元素個數，\(p(k)=1-(1-1/T)^k\) 表示某個集合有 \(k\) 元素且沒有全部被哈希函式篩出的概率，

\[E(K)=\sum_i p(|S_i|) \]

\[\text{Var}(K)=\sum_i p(|S_i|)-p^2(|S_i|)\le E(K) \]

根據切比雪夫不等式

\[P(|K-E(K)|\ge \epsilon E(K))\le \frac{\text{Var}(K)}{\epsilon^2E(x)^2}\le \frac{1}{\epsilon^2} \]

Lemma7.6

設給定 k-中心點 \(Q\)，k-聚類代價為 \(C(Q,P)\)，

設 \(R_i(Q)=|P-B(Q,r_i)|\)，\(R_i(Q)\) 可以用本文提出的 Exclusive Count 演算法以 \(r=(1+\epsilon)\)，\(\delta=\frac{1}{2}\)，空間為 \(\Omega(k)\) 得到近似 \(\hat{R_i}(Q)\)，滿足

\[R_{i+1}(Q)\le \hat{R_i}(Q) \le R_i(Q) \]

文章使用 \(\hat{C}(P,Q)=(r_i-r_{i-1})\hat{R}_i(Q)\) 近似 \(C(P,Q)\)，

\[\begin{align*} C(Q,P)&=\int_0^{+\infty}|P-B(Q,r)|\mathrm{d}r\\ &\le O(1+\epsilon)\sum_{i=-i_0}^{\log\Delta}R_{i+1}(Q)(r_{i+2}-r_{i+1})\\ &\le O(1+\epsilon)\sum_{i=-i_0}^{\log\Delta}\hat{R}_i(Q)(r_{i}-r_{i-1})\\ &= O(1+\epsilon)\hat{C}(Q,P) \end{align*} \]

\[\begin{align*} C(Q,P)&\ge O(1+\epsilon)\sum_{i=-i_0}^{\log\Delta}|P-B(Q,r_i)|(r_{i}-r_{i-1}) \\ &\ge O(1+\epsilon)\sum_{i=-i_0}^{\log\Delta}\hat{R_i}(r_i-r_{i-1})\\ &= O(1+\epsilon)\hat{C}(Q,P) \end{align*} \]

所以 \(\hat{C}(Q,P)\) 是 \(C(Q,P)\) 的一個 \((1+\epsilon)\) 近似，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/554587.html

標籤：其他

上一篇：一分鐘了解自動化測驗

下一篇：返回列表