Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья, 2003
Издание:
Discrete Mathematics,vol.266, no.1, 293-309
Авторы: Левенштейн В.И.
A universal bound for a covering in regular posets and its application to pool testing
Аннотация:
Пусть V(n) - множество всех 2n подмножеств Nn={1,2,...,n} и Vi(n)={x∈V(n):|x|=i}. При фиксированном i=1,...,n, рассмотрим оператор покрытия F : Vi(n)→ V(n) такой, что x⊆ F(x) для любого x∈Vi(n). Пусть C={F(x):x∈Vi(n)}. С помощью усреднения и линейного программирования найдена верхняя граница для среднего значения величины |F(x)| по всем x∈Vi(n) которая достигается тогда и только тогда, когда C образует систему Штейнера S(i,{k,k+1},n) с определенным распределением весов кодовых слов. Приводится обобщение этого результата на регулярные слева частично упорядоченные множества с n элементами. Одним из мотивирующих приложений является задача восстановления неизвестного двоичного вектора x длины n с помощью группового тестирования при условии, что векторы x рапределены с вероятностями p|x|(1-p)n-|x|, где x∈V(n) задает места единиц (активных объектов) в x. Полученная граница улучшает теоретико-информационную границу для минимального среднего числа E(n,p) тестов для восстановления неизвестного вектора x с помощью двухуровнего группового тестирования и позволяет определить с точностью до константы асимптотическое поведение E(n,p) при некоторых ограничениях на p=p(n), когда n → ∞.
Ключевые слова:
покрытие, частично упорядоченные множества, групповое тестирование, системы Штейнера, универсальная граница.
Язык публикации: английский
Направление исследований:
Математические вопросы и теория численных методов
Полный текст на английском языке:
Список цитирующих публикаций:
Экспорт ссылки на публикацию в формате:   RIS    BibTeX
Сведения об авторах:
  • Левенштейн Владимир Иосифович,  ИПМ им. М.В. Келдыша РАН