Реклама в Интернете

Введение
Один из самых больших сюрпризов XXI века – способность разнообразных интересных веб-приложений обеспечивать себя за счет рекламы. Самым рентабельным местом для размещения онлайновой рекламы являются результаты поиска, и своей эффективностью реклама во многом обязана модели «ключевых слов» (adwords), позволяющей сопоставлять поисковые запросы с объявлениями.

Возможности рекламы
Интернет предлагает рекламодателю много способов довести свою рекламу до потенциального покупателя. Перечислим основные рекламные площадки.
Некоторые сайты, например eBay, Craig’s List и сайты по продаже автомобилей предлагают размещать рекламные объявления прямо у себя – бесплатно, за деньги или за комиссионные отчисления.
Рекламные места имеются на многих сайтах. Рекламодатель платит фиксированную цену за показы (одно отображение объявления при загрузке страницы пользователем).
В интернет-магазинах типа Amazon показывается много объявлений в разных контекстах. Производители рекламируемых товаров за эти показы не платят, магазин выбирает их, чтобы повысить вероятность того, что посетитель проявит интерес к товару.
Рекламные объявления размещаются вместе с результатами поиска. Рекламодатели торгуются за право показать свое объявление в ответ на некоторый запрос, но платят, только если посетитель щелкнул (кликнул) по объявлению.

Прямое размещение рекламы
В тех случаях, когда рекламодателям разрешено размещать рекламу напрямую, возникает несколько проблем, которые сайту необходимо решить.
Ранжирование объявлений несколько более проблематично, потому что нет ничего похожего на веб-ссылки, говорящие о том, какие объявления более «важны». Одна из возможных стратегий – «сначала недавние». Она справедлива, но уязвима для манипулирования: рекламодатель может вносить небольшие изменения в свои объявления через регулярные промежутки времени.
Другой подход – пытаться измерить привлекательность объявления. При каждом показе объявления запоминается, щелкнул по нему посетитель или нет. Однако при оценке рекламных объявлений следует учитывать несколько факторов.

От положения объявления в списке в большой степени зависит, щелкнут по нему или нет. У первого объявления вероятность максимальная, а дальше экспоненциально спадает.
Привлекательность объявления может зависеть от поисковых термов.
Все объявления заслуживают шанса быть показанными до тех пор, пока не появится возможность более-менее точно оценить вероятность щелчка. Если в самом начале приписать каждому объявлению вероятность щелчка 0, то мы его никогда покажем и потому не узнаем, привлекательно оно или нет.

Акцидентные объявления
Такая форма рекламы в Интернете больше всего напоминает рекламу в традиционных СМИ. Увидят его многие, но большинство увидевших, например, не интересуются покупкой машины, уже купили машину, вообще не водят или еще по какой-то причине не обращают на объявление внимания. Тем не менее, газета, а вместе с ней и рекламодатель уже оплатила печать объявления.
В ответ на такое отсутствие сфокусированности традиционные СМИ издают газеты и журналы по интересам. Однако в Интернете есть возможность настраивать акцидентную рекламу способом, недоступным печатным изданиям: использовать информацию о пользователе для определения того, какое объявление показать, независимо от просматриваемой им страницы.
Однако использование всех этих и многих других методов наталкивается на массу проблем, связанных с конфиденциальностью.

Онлайновые и офлайновые алгоритмы
Типичный алгоритм работает следующим образом. Все необходимые алгоритму данные предоставляются с самого начала. Алгоритм может обращаться к данным в любом порядке. В конце работы алгоритм порождает ответ. Такие алгоритмы называются офлайновыми.
Но бывает так, что алгоритм должен принимать решение, не видя всех данных. В худшем случае мы должны порождать какой-то ответ после поступления каждого элемента потока, т. е. принимать решения, касающиеся элемента, вообще ничего не зная о будущем. Алгоритмы такого вида называются онлайновыми.

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

Коэффициент конкурентоспособности
Онлайновый алгоритм не дает такой же хороший результат, как оптимальный офлайновый алгоритм. Лучшее, на что можно рассчитывать, – что существует некая константа c, меньшая 1, такая, что при любых входных данных результат онлайнового алгоритма оказывается не более чем в c раз хуже результата оптимального офлайнового алгоритма. Такая константа, если она существует, называется коэффициентом конкурентоспособности онлайнового алгоритма.

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

Жадный алгоритм нахождения максимального паросочетания
Офлайновые алгоритмы нахождения максимального паросочетания изучались десятки лет, для графа с n вершинами это можно сделать за время, очень близкое к O(n2 ). Онлайновые алгоритмы решения этой задачи тоже исследовались, именно они нас и будут интересовать. Конкретно, жадный алгоритм нахождения максимального паросочетания работает следующим образом. Рассматриваем ребра в том порядке, в каком они подаются на вход. Ребро (x, y) включается в паросочетание, если ни x, ни y не являются концами какого-нибудь ребра, уже включенного в паросочетание. В противном случае ребро (x, y) пропускается.