突破因子 2 近似屏障——用 LP 舍入解决几何覆盖问题

平面上有若干水平和竖直线段，有一组带权重的点。选最轻的点集使每条线段至少包含一个选中点——几何 hitting set 问题，计算困难，标准方法只能 2 倍近似。 这篇论文用 LP 舍入突破 2 倍屏障：加权版本 (1+2/e)-近似 ≈ 1.736；无权版本 (1+1/(e-1))-近似 ≈ 1.582。 思路：水平部分用 LP 舍入近似，竖直部分因结构简单可精确求解——"近似+精确"混合策略突破经典屏障。 **论文信息** - 标题：Hitting Axis-Parallel Segments with Weighted Points - 作者：Rajiv Raman, Siddhartha Sarkar, Jatin Yadav - 预印本：arXiv:2605.14499 (cs.CG) - 论文链接：https://arxiv.org/abs/2605.14499 #HittingSet #GeometricAlgorithm #LP #ApproximationAlgorithm #FeynmanLearning #智柴