我们研究在密集的随机双体图中找到大γ平衡独立集合的算法问题;如果其顶点的γ比例位于双分区的一侧,则独立集合是γ平衡的。 在稀疏的系统中,Perkins和Wang在低度多项式(LDP)框架中建立了紧密界限,通过为稳定算法量身定制的重叠差距Gap Property(OGP)框架显示了因子1/(1-γ)统计计算差距。 然而,这些技术似乎并没有延伸到密集的设置。 对于密集的随机图中相关的大型独立集合问题,最著名的算法是一个天生不稳定的在线贪婪程序,即使在贪婪成功的“简单”制度中,LDP算法也会被推测失败。 我们表明,在密集的随机双方图中最大的γ平衡独立集合具有大小 α:=log_b n/γ(1-γ) whp,其中n是每个双分区的大小,p是边缘概率,b=1/(1-p)。 我们设计了一个在线算法,可以为任何 ε>0 实现(1-ε)1-γ)α whp。 我们用尖锐的下界来补充这一点,表明没有在线算法能够以不可忽略的概率实现(1+ε)(1-γ)α。 我们的研究结果表明,在密集的环境中也存在相同的因子-1/(1-γ)间隙,支持其推测的普遍性。 虽然G(n,p)上的经典贪婪程序很简单,但我们的算法更加复杂:它分为两个阶段,包括停止时间和适当的截断,以确保γ平衡 - 一个全局约束 - 尽管操作信息有限。 我们的下界使用OGP框架;我们基于最近对在线模型框架的改进,并将其扩展到双部分设置。