“将式(1)交给交换舍入，得到真正的基B并有条件期望E[f(B) xᴸ及其分解]≥F(xᴸ)。分数点的数值保证与某一次随机基的取值不是同一个承诺。”
形式陈述
输入包含基分解，不只是一个分数向量
给有限拟阵M=(E,𝓘)，n个元素、秩r，独立性oracle可查询任一标号子集。输入m≥1组基B₁,…,B_m及正有理权重β₁,…,β_m，满足
x因而位于全部基指标的凸包。重复的基可合并权重，零权项可预先删除。本页执行器要求输入项严格正；不接受“只给x且声称可行”作为已经获得分解。r=0时所有基为空，算法直接输出空基。
交换舍入输出随机基B，保证每次都可行，且
对任意实值子模函数f，令F为其多线性扩张，还有
舍入过程无需调用f；式(2)对同一输出分布中的每个子模f都成立。这里不要求f单调或非负，但有限底集上的各函数值须有限。连续贪心等上游算法的额外假设仍由上游负责。
合并两组基
暂取两项α1_A、β1_B。只要A≠B，选i∈A\B，再找j∈B\A，使
下面证明这种对称基交换必存在。附件按标号选最小i，再按标号枚举j，两侧都通过独立性查询才接受。
一次随机操作为：[1, §3]
- 以概率α/(α+β)，令B←B−j+i，保持A不变
- 以概率β/(α+β)，令A←A−i+j，保持B不变
每个分支都使|A\B|减少1，至多r次后两基相同，记为C。把两项替成(α+β)1_C，继续与下一项合并。总共m−1次基合并，至多r(m−1)次元素交换，最后权重为1，只剩一组基。
两个分支的概率不取决于各基的目标值，也不能都写成1/2。只有α=β时才是公平硬币；不等权例子能立即暴露错误概率。
直觉
可行性来自基交换，平均位置来自概率配比
若独立地决定每个元素是否入选，可能超出配额或在图中形成环。交换舍入始终携带完整的可行基，每次只把一组基改成另一组已验证的基。因此最终可行性不需要“抽坏了再修补”。
改动较轻的那组基，对分数点造成的位移较小，应配较大概率；两种相反位移便在平均中抵消。以当前两项权重α、β为例，改变B使分数点增加β(eᵢ−eⱼ)，改变A使其减少α(eᵢ−eⱼ)。
整个分数点会沿一条交换方向随机移动，而非在每条样本路径上原地不动。保持的是每个坐标的条件期望；坐标间通常具有依赖。
例子与边界
四个分支逐项核对
取分区拟阵：a、b最多选一个，c、d最多选一个。输入
第一次选i=a。j=b使两侧都为基；j=d则会让一侧含a、b或另一侧含c、d，不合法。公平选择：把bd改为ad，或把ac改为bc。随后分别交换c、d，得到
| 最终基 | 概率 | 覆盖价值 |
|---|---|---|
| ac | 1/4 | 3 |
| ad | 1/4 | 4 |
| bc | 1/4 | 5 |
| bd | 1/4 | 4 |
覆盖仍取a={0,1,2}、b={0,3,4}、c={0,1,2}、d={5}。四个结果都符合两组配额，每个元素出现概率均为1/2。平均价值为4，而独立分布的F(x)=31/8，所以式(2)在此严格成立。
若直接按输入权重抽ac或bd，虽然仍每次可行且边缘相同，平均却只有7/2<31/8。任意同边缘可行分布不自动满足子模期望保证。另一方面，交换舍入也可能输出值3的ac，低于31/8；式(2)从未承诺每个分支都不降值。
不等权、相同基与零秩
秩1的两元素拟阵，输入(1/3)1_{a}+(2/3)1_{b}。若改第二组，应以1/3概率把b改成a；否则以2/3概率把第一组a改成b。最终a、b的概率正好1/3、2/3。颠倒两个概率会颠倒边缘。
两基本来相同，不做元素交换，只合并权重。全是loop的拟阵秩为0，唯一基为空；任意合法基分解仍可合并，输出空集。只有一个基时也直接返回，不能把“没有随机交换”误判为输入失败。
从配额迁移到生成树
在四顶点图上编号
图拟阵独立集为森林。输入树012的权重1/3、树034的权重2/3，舍入得到
所有分支都是生成树，边缘为(1,1/3,1/3,2/3,2/3)。这里可交换的边由两棵树的结构决定，不再是“同一配额组内换编号”。附件的森林oracle实际维护连通分量以拒绝成环候选。
缺少交换公理会卡住
只知道可行集向下封闭不足以保证式(3)。两个不同可行极大集的大小可能不同，或者无法进行两侧同时合法的交换。任意背包、多拟阵交、一般匹配约束都不能不加改造地送进本页的单拟阵基接口。
独立性oracle若错误回答，也可能找不到j或接受非法基。执行器会在已观察到的失败处明确拒绝；这不等于它已用有限查询认证了整个oracle满足拟阵公理。
推论与应用
为什么同一对元素可在两侧同时交换
固定i∈A\B。令C为i关于B的基本回路，故i∈C⊆B+i，且对每个j∈C−i，B−j+i都是基。
考虑A−i的闭包H=cl(A−i)。由于A是基，i∉H。若C−i全在H中，由回路依赖有i∈cl(C−i)；再用闭包单调及幂等，得到i∈cl(H)=H，矛盾。因此存在j∈C−i不在H。
该j属于B，又不在A−i，且j≠i，所以j∈B\A。它不在cl(A−i)意味着增加秩1，故A−i+j也是基。这样得到式(3)。这份证明没有把普通的“仅一侧能换”偷换成对称交换。
坐标条件期望怎样保持
条件于此前全部选择、当前基和权重。记当前完整分数点为z，d=eᵢ−eⱼ；其余基项不变。新点是z+βd或z−αd，概率分别为α/(α+β)、β/(α+β)，故
至多r(m−1)步后已结束，可把提前结束的状态用不变步骤补到同一长度。有限次取总体期望便得E1_B=x，即式(1)。不需要诉诸未证明的无限停时结论。
子模价值为何在平均中不下降
多线性扩张沿交换方向是凸函数。上式又表明z是两个可能端点按上述概率加权的凸组合，所以
每个端点仍是基的凸组合，因此仍在单位立方体内，可以使用这份方向凸性。有限次迭代，最终F(1_B)=f(B)，即得到式(2)。若把凸不等式方向写反，便会错误认为舍入应该降低最大化目标。
两类乘积界，不冒充坐标独立
对任意A⊆E，舍入还满足
证明看P_A(z)=∏ᵢ∈Azᵢ沿当前交换直线的形状。若两个改动坐标都在A内，P_A为一个非负常数乘(zᵢ+t)(zⱼ−t)，二次项系数非正，所以凹；只有一个在A内时为仿射，均不在时不变。端点平均为原点，因此E[P_A(z′)|当前状态]≤P_A(z)。有限迭代给第一式；把每个坐标换成1−zᵢ，完全相同的论证给第二式。[1, Lemma4.1]
这些是特定的全包含/全排除事件上界，不能直接声称所有不相交增函数都负相关。四分支例子中a、b永远不会同时出现，而每个边缘均为1/2，已经清楚表明它们不独立。
实现与核验成本
最多r(m−1)次交换。每次枚举至多r个j，各做至多两次独立性查询，故查询数O(mr²)。附件采用不可变标号集合，每个候选的差集、并集和oracle入参校验需O(r+1)；排序候选的O(r log(r+1))也被粗界覆盖。因此含输入校验、权重和集合存储的简单实现时间可写成
其中n项包含附件Matroid入口的单点检查与求秩贪心；若调用者已给可信的秩及初始化对象，可单列这份预处理。按固定字长标号、精确算术及期望常数散列表访问计。空间为O(n+mr+1)个记录，另加oracle工作区和权重位串。r=0仍要读m项输入，这由首项中的m保留。
默认单次随机运行不保留完整轨迹。打开trace后，每次复制前后两基，占O(r)记录，总日志可达O(mr²)；它不是核心常数大小交换记录。正有理权重抽样的随机位及任意长分子分母算术另计。
附件还有枚举全部随机分支的诊断器，用来精确复核边缘、期望与式(4)。它可能有指数多状态，不能算进上述单次采样算法的多项式界。一般调用者也无需先计算F才能舍入。
综合练习把连续贪心的实际基分解送来，再比较“直接抽原基”“独立抽坐标”“交换合并”三份输出，逐一说明可行性、边缘和期望究竟哪项成立。
参考资料
- Chandra Chekuri、Jan Vondrák、Rico Zenklusen，Dependent Randomized Rounding for Matroid Polytopes and Applications，2009长稿，§2 Theorem2.1、§3 MergeBases/SwapRound、§4 Lemma4.1，PDF pp.6–8：对称基交换、权重概率与乘积界。
- 同作者，Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures，FOCS2010，§IV、§VI：基分解舍入与子模目标期望。本文给闭包形式的交换存在证明，例子与全部分支由精确执行器生成。