论文研究 随机图上布局问题的改进近似

受到Diaz，Petit，Serna和Trevisan的先前工作（随机图上的近似布局问题，DiscreteMathematics，235，2001，245-253）的启发，我们显示了几个众所周知的图布局问题可以在一个因子内任意近似。仅使用基本概率分析从Erdös-Renyi分布绘制的具有适当稀疏条件的随机图的概率接近最优值的1。此外，我们表明，有向无环图上的类似问题具有相同的结果。