整数线性程序的NP完整性

Question

这是一个家庭作业问题，所以我不想要解决方案。我需要一个暗示哪些问题来减少到以下和/或如何开始。我们正在考虑TSP或独立的集合，但不能提出解决方案。

我们有 $ i \ ldots j $ 商店和 $ i \ ldots n $ 可能的地方建一个新的仓库。构建一个新仓库的成本是<跨度类=“math-container”> $ c_j $ 。每个商店和仓库之间是一个成本 $ d_ {i，j} $ 之间的路径。每个商店都需要连接到至少一个仓库。

决策问题是：有一组仓库和路径，使得总和小于给定的数字 $ k $ 。

Answer 1

这是一个经典的设施位置问题。维基百科文章表明，通过设置封面

---

由于提问者现在已经阐述了通过从顶点封面的减少来找到解决方案，我将继续并揭示从 SET封面的减少：

对于每个值，创建一个商店;对于每个设置，创建仓库。将每个仓库的成本分配给1.如果仓库的集合包含该商店的值或否则任意大值，则将路由从仓库中的路由从仓库分配到商店的成本。然后，设施问题的最低成本解决方案正是构建了与原始问题中最小集合对应的一组仓库。

$ k $ 值用于将优化问题（最小化设置/成本最小化）变为决策问题（是否有一个不超过 $ k $ 设置/成本？）。 $ k $ 从集合封面实例与设施问题中的 $ k $ 相同实例如果允许将“任意小”值设置为恰好0 - 否则您可能不得不将值置于数量，但只要您选择“任意小”权重足够小。你只需要每一个“任意小的”成本的总和小于1，每一个“任意大的”成本要大于所有仓库的成本和所有“任意小”路线的总和。

注意，如果设施问题只允许整数成本，则仍然可以通过最小常见多个成本缩放所有成本来实现相同的结果。