突破因子 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