— Открытое покрытие замкнутого подпространства

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

Действительно, если строго следовать определению вашей открытой обложки, нет даже смысла иметь открытую обложку чего-то, что не является топологическим пространством.Итак, чтобы иметь открытое покрытие подмножества $ Y $ из $ X $, нам нужно понимать $ Y $ как топологическое пространство. В самом деле, мы можем наделить $ Y $ топологией, называемой топологией подпространства. По определению, это множество $ \ {U \ cap Y: U \ substeq X \ text {is open} \} $. Открытое покрытие $ Y $, следовательно, и есть открытое покрытие под этим топологическим пространством с данной топологией.

В качестве альтернативы мы можем сказать, что $ \ mathcal U $ покрывает подмножество $ Y \ substeq X $, если объединение $ \ mathcal U $ содержит $ Y $.Оказывается, это в основном то же самое, что и приведенное выше определение. В самом деле, если $ Y \ substeq \ bigcup U_i $ ($ U_i \ substeq X $ open), то $ Y = \ bigcup U_i \ cap Y $, которые все открыты в топологии подпространств, определенной выше. С другой стороны, пусть $ Y = \ bigcup V_i $ — открытое покрытие со всеми $ V_i $, открытыми в топологии подпространства на $ Y $. Тогда $ V_i = Y \ cap U_i $ для некоторого открытого $ U_i \ substeq X $. Таким образом, $ V_i \ substeq U_i $, значит, $ Y \ substeq \ bigcup U_i $ — открытое покрытие в этом альтернативном смысле.

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

Первое понятие компактности состоит в том, что пространство $ Y $ компактно, если любое открытое покрытие $ Y = \ bigcup V_i $ допускает конечное подпокрытие. Поэтому мы говорим, что подмножество $ Y \ substeq X $ компактно, если $ Y $ компактно в топологии подпространства. В качестве альтернативы мы говорим, что подмножество $ Y \ substeq X $ компактно, если для любого открытого покрытия $ Y \ substeq \ bigcup U_i $ существует конечное подпокрытие $ Y \ substeq U_ {i_1} \ cup \ dots U_ {i_k} $ .Лемма говорит, что $ Y $ компактно в первом смысле тогда и только тогда, когда оно компактно во втором смысле.

— Какие простые примеры, иллюстрирующие определение «покрытия»

Определение . $ X $ — топологическое пространство, $ A \ substeq X $ — подпространство (не обязательно строгое). Открытое покрытие $ A $ в $ X $ — это набор открытых множеств $ \ {\ mathcal {U} _i \} $ в $ X $, таких что $ A \ substeq \ bigcup_i \ mathcal {U} _i $.

Геометрическое значение .1 $.

Важность . Открытые обложки не всегда «красивы». Например, рассмотрим открытое покрытие $ \ {(1 / n, 1) _ {n \ in \ Bbb N} \} $ интервала $ (0, 1) $. Итак, вы можете подумать, что это просто технический термин и не имеет особого смысла. Однако вы просто упускаете из виду суть.

Открытые крышки — это язык, на котором можно перейти от топологической точки зрения к комбинаторной. Точнее, вместо того, чтобы проверять свойства топологического пространства $ X $ вручную, мы пытаемся проверить комбинаторные свойства открытых покрытий $ X $, что иногда оказывается очень простым делом из-за меньшей структуры.2 $. Это определенно не гомеоморфно, скажем, $ [0, 1] $. Очевидный аргумент состоит в том, что первое является чем-то «большим» (гомеоморфным $ \ Bbb R $), а второе — «маленьким». Правильная аналитическая формализация этой идеи — это секвенциальная компактность, т.е. что каждая бесконечная последовательность имеет сходящуюся подпоследовательность. Можно использовать некоторый анализ, чтобы показать, что $ [0, 1] $ последовательно компактно, а $ (0, 1) $ — нет. Однако

$ \ text {Fact} $: В хороших пространствах секвенциальная компактность эквивалентна свойству «каждое счетное покрытие имеет конечное подпокрытие».

Полная характеристика хороших пространств немного сложна, но метрические пространства являются примерами таких пространств. В любом случае обратите внимание, что открытое покрытие $ (0, 1) $, полученное в приведенном выше ответе, не имеет конечного подпокрытия, в то время как каждое открытое покрытие $ [0, 1] $ имеет конечное подпокрытие (попробуйте это доказать!). Таким образом, мы только что использовали комбинаторное свойство открытых покрытий, чтобы вернуть аналитические свойства всего пространства. В частности, упомянутое выше свойство открытых покрытий называется (счетной) компактностью топологических пространств.

Еще одна интересная вещь об открытых покрытиях — это лемма Лебега о покрытиях, которая утверждает, что для компактного метрического пространства с открытым покрытием существует положительное вещественное число $ \ epsilon $ такое, что каждое открытое множество диаметра не более $ \ epsilon $ подходит внутри открытый набор в крышке. Это очень хорошая теорема, которая, в свою очередь, используется для доказательства упомянутого выше факта. Это также имеет интересные приложения в алгебраической топологии (например, в доказательстве теоремы вырезания для особых гомологий).

— Покрытие первой меры множества замкнутых нулевых множеств

Ответ на первый вопрос — да: всегда верно, что $ \ kappa _ {\ mathcal E} = \ mathrm {cov} (\ mathcal E) $. Ответ на второй вопрос — нет.

Как указывает Петр, отрицательный ответ на второй вопрос означает положительный ответ на первый. [Это потому, что если $ A \ substeq [0,1] $ является множеством меры один, то оно содержит замкнутый $ K \ substeq [0,1] $ положительной меры (действительно, мы можем получить меру $ K $ как можно ближе к $ 1 $).Отрицательный ответ на второй вопрос означает, что требуется не менее $ \ mathrm {cov} (\ mathcal E) $ наборов в $ \ mathcal E $, чтобы покрыть $ K $; поскольку $ K \ substeq A $, требуется как минимум $ \ mathrm {cov} (\ mathcal E) $ наборов в $ \ mathcal E $, чтобы покрыть и $ A $.]

Итак, достаточно показать, что ответ на второй вопрос отрицательный: число $ \ mathcal E $ -покрытие одинаково для любых замкнутых подмножеств $ [0,1] $ положительной меры.

Чтобы убедиться в этом, зафиксируем замкнутый $ K \ substeq [0,1] $ положительной меры $ \ alpha $.Пусть $ \ mathcal F $ — семейство множеств в $ \ mathcal E $, покрывающее $ K $. Наша цель — покрыть $ [0,1] $ семейством множеств в $ \ mathcal E $ размера $ | \ mathcal F | $. Это показывает, что число $ \ mathcal E $ -покрытия для $ [0,1] $ не больше аналогичного числа для $ K $. Очевидно, что число $ \ mathcal E $ -покрытия для $ [0,1] $ не меньше аналогичного числа для $ K $, поскольку любое покрытие $ [0,1] $ множествами в $ \ mathcal E $ также является прикрытием $ K $.

Определите карту $ \ phi: K \ rightarrow [0,1] $ с помощью $$ \ phi (x) = \ frac {1} {\ alpha} \ cdot m (K \ cap [0, x]) $$ для всех $ x \ in K $, где $ m $ обозначает меру Лебега.Используя тот факт, что $ K $ замкнут, можно показать, что $ \ phi $ сюръективен. В частности, $$ \ phi (\ mathcal F) = \ {\ phi [A \ cap K]: A \ in \ mathcal F \} $$ семейство множеств, покрывающее $ [0,1] $. Для завершения доказательства достаточно показать, что отображение $ A \ mapsto \ phi [A \ cap K] $ отправляет множества в $ \ mathcal E $ в множества в $ \ mathcal E $: тогда $ \ phi (\ mathcal F) $ — искомое $ \ mathcal E $ -покрытие $ [0,1] $.

Из определения $ \ phi $ мы видим $$ m (\ phi [(0, b)]) = \ frac {1} {\ alpha} \ cdot m (K \ cap (0, b)) $$ и принимая дополнения мы получаем $$ m (\ phi [(a, 1)]) = \ frac {1} {\ alpha} \ cdot m (K \ cap (a, 1)).$$ и переходя к пересечениям, мы видим, что для любого интервала $ (a, b) \ substeq [0,1] $, $$ m (\ phi [(a, b) \ cap K]) = \ frac {1} {\ alpha} (m ((a, b) \ cap K)). $$ То есть $ \ phi $ может увеличить размер интервала не более чем в $ \ frac {1} {\ alpha} $. После небольшой дополнительной (рутинной) работы это показывает, что карта $ A \ mapsto \ phi [A \ cap K] $ отправляет нулевые множества в пустые множества.

Заметим, что $ \ phi $ непрерывно (прообраз открытого интервала в $ [0,1] $ — открытый интервал в $ K $). Следовательно, $ \ phi $ отображает компактные множества в компактные множества.Следовательно, отображение $ A \ mapsto \ phi [A \ cap K] $ переводит компакты в компакты. Поскольку $ [0,1] $ компактно, это означает, что он также отправляет наборы $ F_ \ sigma $ в наборы $ F_ \ sigma $. Итак, мы показали, что карта $ A \ mapsto \ phi [A \ cap K] $ отправляет нулевые наборы $ F_ \ sigma $ в нулевые наборы $ F_ \ sigma $, и все готово.

Страница конкурса | CodeChef

CodeChef — платформа для начинающих программистов

CodeChef был создан как платформа, чтобы помочь программистам добиться успеха в мире алгоритмы , компьютерное программирование и программирование конкурсы .В CodeChef мы упорно работаем, чтобы оживить в вас гика, проводя программирование конкурс в начале месяца и два небольших задания по программированию в средний и конец месяца. Мы также стремимся проводить тренинги и обсуждения, связанные с алгоритмы , бинарный поиск , технические особенности, такие как массив размер и им подобные.Помимо предоставления платформы для программирования соревнования , CodeChef также имеет различные учебные пособия по алгоритмам и форум обсуждения помогать для тех, кто плохо знаком с миром компьютерного программирования .

Практическая секция — Место для оттачивания вашего компьютерного программирования Навыков

Попробуйте свои силы в одной из наших многочисленных практических задач и представьте свое решение на языке из ваш выбор.Наш конкурс по программированию Судья принимает решения в более чем 55+ программирование языков. Подготовка к соревнованиям по программированию никогда не была такой веселой! Получайте очки и двигайтесь вверх через в рейтинге CodeChef. Воспользуйтесь нашим разделом практики, чтобы лучше подготовиться к множеству программирование вызовы , которые проходят в течение месяца на CodeChef.

Compete — ежемесячные соревнования по программированию, готовка и обед

Здесь вы можете продемонстрировать свои навыки программирования на компьютере . Принять участие в наши 10 Ежемесячный конкурс кодирования на несколько дней и кодирование в более коротком формате Cook-off and Lunchtime конкурсы . Поднимитесь на признание и выиграйте отличные призы. Наш программирование конкурсы имеют призы на сумму до 20 000 индийских рупий (для индийского сообщества), 700 долларов США (для Глобальный Сообщество) и многие другие полезности CodeChef.

«Задачи с несколькими покрытиями и их варианты» Сантану Бховмик

Название степени

кандидат философских наук

Абстрактные

В комбинаторной оптимизации покрывающие проблемы — это те проблемы, в которых для заданного основного набора и семейства подмножеств основного набора цель состоит в том, чтобы найти набор подмножеств с минимальной стоимостью, объединение которых содержит основной набор. Мы рассматриваем покрывающие проблемы в контексте вычислительной геометрии, которая является подразделом компьютерных наук, который занимается проблемами, связанными с геометрическими объектами, такими как точки, линии, диски, многоугольники и т. Д.В частности, геометрическое покрытие является активной областью исследований, где основной набор и семейство подмножеств индуцируются геометрическими объектами. Решение задач комбинаторной оптимизации часто имеет геометрический аналог, который возникает естественным образом, и хотя такие проблемы остаются NP-трудными, часто можно использовать геометрические свойства системы множеств для получения лучших алгоритмов аппроксимации.

В этой работе основной проблемой, которую мы рассматриваем, является обобщение геометрического покрытия, где каждый элемент в основном наборе может нуждаться в покрытии более чем одним подмножеством.Чтобы быть точным, задача определяется следующим образом: для заданных двух наборов точек X, Y и функции покрытия κ: X → Z + ∪ {0} построить шары с центрами в точках Y так, чтобы каждая точка в X была покрыта не менее κ (x) различных шаров. Цель этой задачи — минимизировать общую стоимость, которая является функцией радиусов шариков. Эта проблема называется метрической проблемой множественного покрытия (MMC).

Сначала рассмотрим вариант задачи MMC, где κ (x) = 1 для всех клиентов, т.е.е. случай 1-покрытия. Известные результаты, которые дают приближение постоянного множителя для этой проблемы, являются вариациями основанного на LP алгоритма прямого двойственного действия. Мы используем модифицированную технику локального поиска, мотивированную геометрической идеей, чтобы получить простую аппроксимацию с постоянным множителем для этой проблемы в главе 2.

Затем мы рассмотрим задачу MMC, в которой точечные множества X, Y находятся на евклидовой плоскости, и каждый клиент x ∈ X должен быть покрыт по крайней мере κ (x) различными дисками с центрами в точках Y.В главе 4 мы даем первое приближение полиномиального коэффициента постоянной времени для этой задачи, в котором постоянная не зависит от функции покрытия κ. Наше решение также имеет свойство приращения, которое позволяет алгоритму обрабатывать увеличение требований к покрытию за счет увеличения радиусов текущих серверных дисков, не влияя на коэффициент приближения.

В следующей задаче мы переходим от евклидовой плоскости к произвольным метрическим пространствам, где мы рассматриваем равномерную задачу MMC.В этой задаче у каждого клиента x есть потребность κ (x) = k, где k> 0 — целое число. Мы даем первое приближение постоянного множителя (не зависящее от k) для этой задачи. Ключевым вкладом, который привел к этому результату, является формулировка схемы разделения серверов в единой задаче MMC, которая сводит единую задачу MMC к k экземплярам задачи 1-покрытия, сохраняя при этом оптимальность решения до постоянного мультипликативного фактор. Мы представляем схему разбиения как независимый результат в главе 5, который затем используем для решения однородной задачи MMC в главе 6.

Затем проблема MMC с произвольной функцией покрытия κ рассматривается в главе 7. Ключевая проблема, которую представляет неоднородная версия, заключается в том, что симметрия схемы разделения сервера нарушается, поскольку потребности клиентов в покрытии не зависят друг от друга. Мы представляем алгоритм постоянного коэффициента для этой проблемы в главе 7.

Последняя проблема, которую мы рассматриваем, — это проблема t-MMC, которая представляет собой ограниченную версию однородной проблемы MMC. Задача состоит в том, чтобы вычислить покрытие, в котором каждый клиент покрыт по крайней мере k отдельными дисками сервера, используя в сумме не более t дисков сервера.Эта проблема является обобщением проблемы кластеризации (где k = 1), и, насколько нам известно, это обобщение рассматривается впервые. Мы даем приближение постоянного множителя для этой задачи в главе 8.

Публичная аннотация

В этой диссертации мы исследуем метрическую задачу множественного покрытия (MMC) и ее варианты. Нам даны два набора точек X (клиенты) и Y (серверы) в метрическом пространстве и неотрицательное целое число k. Цель состоит в том, чтобы найти такое распределение радиусов для серверов, чтобы каждый клиент был охвачен как минимум k дисками, сосредоточенными на серверах, при минимизации общей площади дисков.Проблема MMC возникает при проектировании сетей беспроводных датчиков, в которых каждый датчик имеет ограниченный источник энергии. Потребляемая энергия считается линейной в области покрытия каждого датчика. Некоторым приложениям может потребоваться несколько датчиков, контролирующих область для обнаружения событий, тогда как в других приложениях требования безопасности или отказоустойчивости могут требовать множественного покрытия клиентов. В предыдущих работах описывались алгоритмы, которые давали O (k) приближение к проблеме, то есть стоимость полученных решений линейно возрастала с k, что делало их непрактичными для высоких значений k.

В этой работе мы выводим приближения постоянного фактора для задачи MMC, в которой гарантия постоянного фактора не зависит от спроса k. Мы распространяем ту же гарантию приближения на некоторые варианты проблемы MMC, которые включают версию, имеющую неоднородные требования к покрытию клиентов, и версию, в которой есть ограничение на количество серверов, которые могут использоваться. Мы также даем простую геометрическую аппроксимацию постоянного множителя для регулярного покрытия, чтобы облегчить более глубокое понимание проблем метрического покрытия.