Расслабление

У меня есть вопрос о целесообразности, который можно сформулировать следующим образом. Мне дана точка в d- мерном векторном пространстве, и я хочу найти ближайшую точку q к p, которая удовлетворяет набору « ℓ 0 ограничений» вида$p$$d$$q$$p$$\ell_0$

Для данного множества не более одного из { q j , j ∈ S } может быть ненулевым.$S \in [1\ldots d]$$\{q_j, j \in S\}$

Понятие близости меняется, но сейчас достаточно , чтобы принять удобное расстояние , как .$\ell_2^2$

Есть ли известные ослабления линейных ограничений, которые являются «хорошими» в смысле предоставления «достаточно близкого» многогранника для аппроксимации исходных ограничений, где я также довольно гибок в определении «достаточно близкого»

Я не уверен , если я понимаю проблему правильно, но , как написано, проблема , кажется, допускают несколько упрощений, и , в частности , проблема в л ₂ ² случая эквивалентно минимального веса крышки вершины , если я не ошибаюсь.

1. Без ограничения общности можно предположить, что | S | = 2 в каждом ограничении, потому что ограничение с | S |> 2 эквивалентно множеству ограничений , где S пробегает все пары элементов исходного множества S . Поэтому ограничения ℓ ₀ можно представить в виде графа G с d вершинами. Использование графа G , ограничения могут быть пересчитаны следующим образом : множество вершин , соответствующие координатам я с д _я = 0 должна быть вершиной крышкой G .
2. $$q'_i = \begin{cases} p_i, & q_i \ne 0, \\ 0, & q_i = 0, \end{cases}$$ , В частности, если расстояние является суммой покоординатного расстояния (как и в случае л ₂ ² расстояния), проблема заключается в точности такой же , как минимальный вес крышка вершины.

Что касается LP-релаксации задачи покрытия вершин, быстрый поиск приводит, например, к лекционным заметкам (лекция 9) Уриэля Фейджа .