Competitive ratio ·dualobj≤dual opt≤primal opt=OPT ·primal obj≤(1+2)dual obj ·Combine together,,competitive ratio≤。二Competitive ratio • 𝑑𝑢𝑎𝑙 𝑜𝑏𝑗 ≤ 𝑑𝑢𝑎𝑙 𝑜𝑝𝑡 ≤ 𝑝𝑟𝑖𝑚𝑎𝑙 𝑜𝑝𝑡 = 𝑂𝑃𝑇 • 𝑝𝑟𝑖𝑚𝑎𝑙 𝑜𝑏𝑗 ≤ (1 + 1 𝑐 )𝑑𝑢𝑎𝑙 𝑜𝑏𝑗 • Combine together, competitive ratio ≤ 𝑒 𝑒−1