NP-полнота для целочисленной линейной программы

Question

Это проблема домашней работы, поэтому я не хочу решение.Мне нужен намек, проблема, которую нужно уменьшить до следующего и / или как начать на нем.Мы думали о TSP или независимом наборе, но не могли придумать решение.

У нас есть $ i \ ldots j $ Магазины и $ i \ ldots n $ Возможные места дляпостроить новый склад.Стоимость построить новый склад - $ c_j $ .Между каждым магазином и складом является путь стоимости $ d_ {i, j} $ .Каждый магазин должен быть подключен к хотя бы одному складу.

Проблема решения: Есть ли набор складов и путей, так что сумма меньше заданного количества $ K $ .

Answer 1

Это классический Проблема расположения объекта . Эта статья Википедии предполагает, что NP-твердость может быть доказана сокращением от Установите крышку .

---

Поскольку asker теперь заявил, что нашел решение, уменьшая от крышки вершины , я пойду вперед и раскрывающую уменьшение от Set Cover :

Для каждого значения создайте магазин; Для каждого набора создайте склад. Назначьте стоимость каждого склада в 1. Назначьте стоимость маршрута со склада в магазин, чтобы быть произвольно небольшим значением, если этот набор хранилища содержит значение хранения, или произвольно большое значение в противном случае. Затем минимальное затратное решение для задачи объекта создает именно набор складов, соответствующих минимальному набору крышки в исходной задаче.


Значение $ k $ используется для включения проблемы оптимизации (минимизировать наборы / стоимость) в проблему решения (есть ли решение с не более чем $ k $ Наборы / стоимость?). $ K $ из набора экземпляра крышки будет совпадать с $ K $ в задаче объекта Экземпляр, если вам разрешено устанавливать «произвольно маленькие» значения ровно 0 - в противном случае вам, возможно, придется поставить значение на некоторое количество, но менее 1 до тех пор, пока вы выбираете «произвольно маленькие» веса, чтобы быть достаточно маленькими. Вам просто нужна общая сумма каждой «произвольной маленькой» стоимости, чтобы быть менее 1, и каждая «произвольно большая» стоимость будет больше, чем сумма расходов всех складов и всех «произвольно маленьких» маршрутов.
Обратите внимание, что, если в задаче объектов разрешены только целочисленные расходы, вы все равно можете достичь того же результата путем масштабирования всех расходов на их наименее распространенные множественные.