高级算法之对偶规划
The Primal-Dual Schema1 对偶线性规划例子
一般形式
弱对偶性任意可行解$x$和对偶解$y$, 有
y^\top b\le c^\top x证明:
y^\top b\le y^\top Ax\le c^\top x强对偶性原LP问题有有限最优解$x^{*}$当且仅当对偶问
...
组合数学之极值集合
Posted on
极值集合1 太阳花集合系统(集族)$\mathcal F\in 2^{[n]}$, ground set $[n]$
sunflowers:$\mathcal F$是一个以$C$为中心的大小为$r$的太阳花, 即 $|\mathcal F|=r$, $\forall S,T\in \mathcal
...
组合数学之极值图论
Posted on
极值图论1 Fobidden Cliques研究问题: 如果$G$满足某些性质, 那么$G$至多有多少条边?
1.1 Mantel’s theorem定理(Mantel 1907):
假设$G(V,E)$ 是无三角形的$n$点图, 那么 $|E|\le n^2/4$.
证明1(鸽笼原理):对$n
...
组合数学之概率法
Posted on
概率法1 The Probabilistic Method概率法的两种基本方法:
对于概率空间$\Omega$和事件$P$, 如果$\Pr_x[P(x)]>0 =>\exists x\in\Omega$ 满足性质$P$.
对于随机变量$X$, 存在$x\le \mathbb E[X]$
...
计算机网络之Ch5网络层:控制平面
Posted on
5 网络层: 控制平面5.1 概述
计算维护和安装转发表和流表
两种可能方法:
每路由器控制: 每台路由器运行一种路由选择算法
逻辑集中式控制: 需要控制代理CA和控制器通信并且按控制器命令行事, CA不能直接相互交互, 也不主动参与计算转发表
5.2 路由选择算法
路由选择算法的目的是从发送
...
高级算法之LP
Posted on
Rounding Linear Programs1 Vertex Cover问题表示整数线性规划:
\begin{aligned}
{\text{minimize}}
&&&\sum_{v\in V}x_{v}\\
{\text{subject to}}
...
高级算法之贪心
Posted on
Greedy and local search1 set coverSet Cover Problem输入: 给定$m$个集合$S_1,S_2,\cdots,S_m\subseteq U$, $|U|=n$;输出: 最小的$C\subseteq \{1,2,\cdots,m\}$, 满足$U=\cu
...
组合数学之存在性问题
Posted on
存在性问题1 Existence by counting1.1 Shannon’s circuit lower bound布尔电路问题: $f:\{0,1\}^n\to \{0,1\}$, 三种门: AND, OR, NOT. 电路复杂度: 门的个数.
定理(Shannon):
存在布尔函数$f:\
...
计算机网络之Ch7无线网
Posted on
7 无线网络和移动网络7.1 概述
无线网络中的元素
无线主机
基站: 向与之关联的无线主机发送数据和从主机接收数据 (有线网中无)
无线链路
切换handoff: 一台移动主机的移动超出一个基站的覆盖范围而到达另一个基站的覆盖范围后, 它将改变其接入到更大网络的连接点, 这一过程称为切换.
...
组合数学之Cayley公式
Posted on
Cayley’s formula1 Cayley’s Formula$n$个不同的点可以构成$n^{n-2}$棵不同的树(labeled tree).
1.1 Proof of Cayley’s formula by double counting
记$n$个不同的点构成的不同的树的数量为$T_n$
...