Что известно о следующей проблеме?
Для набора функций : f : { 0 , 1 } n → { 0 , 1 } найдите наибольшую подгруппу S ⊆ C с учетом ограничения VC-Dimension ( S ) ≤ k для некоторого целого числа k .
Существуют ли алгоритмы аппроксимации или результаты твердости для этой задачи?
Ответы:
Редактирование : исходная задача -Жесткого аппроксимировать , когда к = 1 , где п обозначает число наборов.n1−ϵ k=1 n
Двойной гиперграф получаются путем обмена вершин с ребрами, и сохранением числа случаев. Проще понять проблему, когда мы заметим, что гиперграф имеет VC-размерность 1, если его двойник является кросс-свободным (для всех в A хотя бы один из P ∩ Q , P ∖ Q , Q ∖ P , ( P ∪ Q ) c пусто).P,Q A P∩Q,P∖Q,Q∖P,(P∪Q)c
В силу двойственности исходная задача (для ) эквивалентна тому, что с учетом гиперграфа ( V , S ) найти максимальный размер U ⊆ V с ( U , { S ∩ U ∣ S ∈ S } ) кросс-свободным.k=1 (V,S) U⊆V (U,{S∩U∣S∈S})
Оригинальный ответ
Но для первоначальной (первичной) проблемы, кажется, нужно еще немного подумать ... выглядит интересно!
источник
Некоторая соответствующая связанная с этим работа: Оценка самого измерения VC (не говоря уже о нахождении большого подколлекции с ограниченным измерением VC) в вашем представлении является завершением LOGNP (LOGNP - это NP, ограниченная записью n битов недетерминизма). Есть также немного связанной работы по оценке и аппроксимации VC-измерения, когда представление пространства диапазонов является более компактным (см. Также ссылки внутри)
источник