Friday, November 5, 2010

On the usefulness of news feeds, changedetection, google scholar et al.

Yesterday Ola Svensson published on his web page a new paper "Santa Claus Schedules Jobs on Unrelated Machines". I know that because of changedetection.com, a service, sending me a message everytime the site I subscribed on has changed.

Also yesterday, I got feeds from Terence Tao's blog on "self-defeating object" argument.

Now when I know the title of the new paper by Ola, I can subscribe on it in Google Scholar, and get messages on new papers anytime Scholar has indexed them.

Thus, net provides plenty of possibilities to anyone ready to embark on studying more deeply such subject as mathematics.

What I especially appreciate in studying is that you never know everything in your area (if you do then this area is unnaturaly restricted). Now when I started my third PhD year, it seems to me I started to see what will be in my thesis.

Recently I opened interesting for me relation between graph coloring problems and packing problems. First of all, it concerns the relation between coloring of interval graphs and bin packing.

Friday, October 29, 2010

At last! The opportunity to read the thesis by David Stifler Johnson

This link has made possible for everyone to read very important PhD thesis in combinatorial optimization and worst-case analysis. Namely, the thesis by David Stifler Johnson named "Near-optimal bin packing algorithms". I hope in the near future we'll be able to take a look at such important papers in bin packing theory as:
  1. The performance of a memory allocation algorithm by Jeffrey David Ullman
  2. A Lower Bound for On-Line One-Dimensional Bin Packing Algorithms by Donna J Brown
Not on bin packing, however, important and not available on the net paper is
    The Intrinsic Computational Difficulty of Functions by Alan Cobham.

    Saturday, July 24, 2010

    Вопрос о существовании линейного порядка, обеспечивающего порождение оптимума 2

    Пока искал информацию о свойстве реставрации упаковки, нашел следующую очень интересную работу:

    (1) Залюбовский В.В. О представлении перестановками допустимых решений одномерной задачи упаковки в контейнеры // Труды XIII Байкальской школы-семинара. Иркутск. Том 1. 2005. С. 461-468.

    В этой работе на странице 462 ставится вопрос, вынесенный в заголовок этого поста:

    "4. Наилучший элемент в пространстве решений соответствует оптимальному решению
    исходной задачи."

    и на него дается ответ на стр. 463 в духе [1]:

    "Лемма 2. Для любой допустимой упаковки $\mathcal{P}$ множества предметов $L$ существует $NF$-активная упаковка $\mathcal{P}'$ такая что
    \[|\mathcal{P}'|\leq |\mathcal{P}|."\]

    Приведем основные понятия в порядке их упоминания в работе (1) с авторскими комментариями.
    1. Понятие NF-активной упаковки. Собственно говоря, именно для алгоритма Next Fit и доказывается о принадлежности оптимума множеству кодов.
    2. Понятие регулярной перестановки и упаковки. Для регулярной упаковки доказывается лемма, аналогичная Лемме 2.
    3. Понятие максимальной упаковки. Для этой упаковки лемма, аналогична Лемме 2 не приводится, хотя из Теоремы 3 можно сделать вывод, что ее доказательство неявно предполагается.
    Библиография
    1. Giffler J., Thompson G.L., “Algorithms for solving production scheduling problems,” Operations Research, Vol. 8, 1960, pp. 487–503.

    Thursday, July 22, 2010

    Вопрос о существовании линейного порядка, обеспечивающего порождение оптимума

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

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

    Если говорить об одномерной упаковке, то для задачи одномерной упаковки и для алгоритмов Any Fit классики такими вопросами не задавались. Объясняется это тем, что легко доказать, что для Any Fit алгоритмов всегда существует такой порядок.

    В то же время в первой работе об алгоритмах с оценками в худшем случае для упаковки в полосу этот вопрос рассматривался для алгоритма "bottom-up left-justified" (BL) [1], эта же работа и вводит в оборот этот алгоритм. Там было доказано, что существуют примеры, где BL не дает оптимального решения.
    1. BS Baker, EG Coffman and RL Rivest, Orthogonal packings in two dimensions. SIAM Journal on Computing 9/4 (1980), pp. 846–855.

    Wednesday, July 7, 2010

    DOOR-2010

    Сегодня утром мы с моим научным руководителем приехали из России, где были на конференции "Дискретная оптимизация и исследование операций". Было достаточно интересно. Появились новые знакомства.

    Saturday, June 19, 2010

    Идея

    Как я раньше к этому не пришел не понимаю. Идея заключается в том, чтобы Google Scholar  (далее - GS) проиндексировал мой список публикаций. Чтобы GS это сделал необходимо выполнить условия со страницы "Inclusion Guidelines for Webmasters". В данный момент из вышеупомянутого списка публикаций GS находит все-лишь одну статью.

    Friday, June 18, 2010

    Web Based LaTeX Editors

    Чтобы не случилось с исходными текстами на LaTeX (далее тех-файлы) твоих статей в оффлайне, или с твоим техом, при использовании онлайн редакторов и хранении исходников где-нибудь онлайн, ты застрахован от таких неприятностей. Хранить онлайн можно было что-угодно и раньше, только вот не было возможности компилировать онлайн тех-файлы. Теперь же этa возможность имеется и даже как минимум в четырех следующих вариантах:
    http://docs.latexlab.org/ (скомпилировать удалось, но не поддерживается кириллица, пока все бесплатно, )
    http://www.scribtex.com/ (здесь кириллица поддерживается, бесплатно 3 проекта, 1 сотрудник, 50 Мб места, скомпилировать удалось)
    http://www.verbosus.com/ (интерфейс неприятный, есть ограничения на бесплатное пользование сервисом, хотя скомпилировать удалось)
    http://monkeytex.bradcater.webfactional.com/ (скомпилировать у меня здесь не вышло, каких-либо ограничений я не нашел)

      Sunday, May 30, 2010

      Первая защита

      В пятницу, 28 мая, наблюдал за первой защитой. Защита состоялась в том же совете, в котором предстоит защищаться и мне.  Примечательна она была тем, что диссертант был расхвален со всех сторон, включая оппонентов. Кроме того, один из авторитетных членов совета призвал голосовать всех остальных "за", никто, впрочем, и не возражал. Презентации не было. Были плакаты, прикрепленные к деревянным стендам. Буквы на которых не были видны уже с первого ряда. Можно сказать, что все прошло гладко. Единственное место, где будущий кандидат застопорился, это вопрос о сути предлагаемого комплексного метода. Я сразу смоделировал эту ситуация на себя, и получился вопрос о сути эволюционно-фрагментарного метода. Кроме того, был вопрос о правильности работы программы и как она проверялась. Мой руководитель в таком случае посоветовал не выносить на защиту программы. Можно сказать, что это был образец хорошей защиты.

      Wednesday, May 19, 2010

      Любопытная статья

      Нашел сейчас статью под названием "On The Number of Condoms at a Cheap Safe-Sex Orgy". Начал читать, и первый абзац оправдал ожидания:
      "Let M and F be finite sets. A straight orgy is a series of interactions between each pair in $M\times F$ ... We give an exact formula for the minimal number of condoms required to realize such an orgy, up to an additive factor of 1."

      Friday, May 14, 2010

      Ранг частично упорядоченного множества

      Понятие ранга у-множества было введено в [1] и развито в [2]. Оно определяется аналогично размерности Душника-Миллера [3], только вместо мощности наименьшого минимального реализатора нас интересует мощность наибольшего минимального реализатора (= множество линейных расширений у-множества, пересечение которых совпадает с самим у-множеством).

      Тема эта интересна тем, что минимального реализатора всего пространства перестановок достаточно для вывода об избыточности оператора мутации на текущем шаге работы эволюционного алгоритма (рассматривается задача оптимизации, заданная на перестановках).
      1. Maurer S. Large Minimal Realizers of a Partial Order / Stephen B. Maurer, I. Rabinovitch // Proceedings of the American Mathematical Society, Vol. 66, No. 2 (Oct., 1977), pp. 211-216.
      2. Maurer S. Large Minimal Realizers of a Partial Order II / Stephen B. Maurer, I. Rabinovitch, William T. Trotter // Discrete Mathematics. - Vol. 31. - 1980. - P. 297-313.
      3. Dushnik B. Partially Ordered Sets / Ben Dushnik and E. W. Miller // American Journal of Mathematics, Vol. 63, No. 3 (Jul., 1941), pp. 600-610.

      Tuesday, May 11, 2010

      Что может быть включено в диссертацию

      1. Группа результатов по графам линейных расширений
      2. Группа результатов по задаче с периодическим работами
      Что может быть доработано и включено в диссертацию:
      1. Разбиение пермутоэдров графами линейных расширений
      2. Вероятность генерации максимальной популяци
      3. Результаты о сжатии-расширении популяции (псевдовыпуклый поиск по Моральо)

      Saturday, March 13, 2010

      Как издаются диссертации нашими швейцарскими коллегами

      Йоханнес Бадер защитился и издал свою диссертацию. Ничего особенного... Если не учитывать, что издана его диссертация издательством с названием "Йоханнес Бадер". Это значит, Йоханнес воспользовался услугами самиздата, в его случае подразделения Амазон - CreateSpace. Тем, кто интересуется генетическим программированием известно, что "A Field Guide to Genetic Programming" была издана самиздатовской компанией Lulu.com.

      Thursday, March 4, 2010

      Как проводится защита диссертации в Португалии

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

      Thursday, February 11, 2010

      Математическии студии

      Во Львове издается журнал "Математичні студії". Мне он интересен тем, что
      1. входит в список ваковских изданий по физ.-мат. наукам
      2. рецензируемый
      3. издается 6 раз в год
      4. рукописи статей принимаются только в TeX.
      Сегодня отослал свою статью "Regular subgraphs of linear extension graphs" в редакцию. Статья является переработанной версией препринта, который предполагалось отослать в Вестник Киевского университета. Поскольку для того, чтобы получить рецензию в Вестник, необходимо быть знакомым с членом редколлегии, было решено выбрать другой журнал.

      Saturday, February 6, 2010

      Дополнительные экзамены по специальности

      Вчера побывал на заседании совета, в котором предполагается моя защита. Узнал, что дополнительные экзамены по специальности (специальность полученная мной до аспирантуры не математическая, кроме того, специальности "математическое мод-ние и выч. методы" на уровнях до аспирантуры нет, поэтому, наверное и моим коллегам математикам придется сдавать дополнительные экзамены) могут быть назначены только после того, как будет подана диссертация в совет.

      Thursday, January 28, 2010

      3-хслойные посеты

      3-хслойные посеты (авторский перевод термина "3-layer posets") это тот класс частично упорядоченных множеств, которому принадлежат почти все из них [1]. Из чего следует, если вы докажите некоторое свойство об этом классе, значит докажите о почти всех.

      "Графы линейных расширений (ГЛР) инвариантны относительно операции последовательной альтерации на порождающем его посете". Так звучит следствие теоремы, доказанной в [2]. В связи с этим результатом возникает следующие вопросы:
      1. Относительно какой (-их) операции (-ий) остается неизменным данное свойство некоторого класса ГЛР.
      2. Какое (-ие) свойство (-ва) некоторого класса ГЛР инвариантно (-ы) относительно данного набора операций.
      Можно, например, рассмотреть операцию прямой суммы посетов. При этом наиболее простой случай, когда берутся два операнда, один из которых цепь, состоящая из одного элемента.

      1. D. J. Kleitman and B. L. Rothschild, Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc., 205 (1975), pp. 205–220. (114)
      2. Massow MLinear Extension Graphs and Linear Extension Diameter. PhD Dissertation, Technischen Universität Berlin. - Berlin: 2009.

      Wednesday, January 27, 2010

      Две статьи и диссертация

      Где-то в начале этого января удалось узнать о двух статьях, в которых были рассмотрены вопросы, над которыми я тогда работал. Сегодня, благодаря профессору Стефану Фельснеру, удалось получить доступ к их электронным версиям. Дело в том, что это препринты, которые нигде не публиковались. Стефан отсканировал эти препринты и теперь они доступны в сети:
      1. Reuter K. The Comparability Graph and the Graph of Linear Extensions of a Poset. Hamburger Beiträge zur Mathematik, Heft 57 (1996).
      2. Reuter K. Linear Extensions of a Poset as Abstract Convex Sets. Hamburger Beiträge zur Mathematik, Heft 56 (1996).
      Кроме того, стала доступна электронная версия диссертации, которая явлется последним, если так можно выразиться, словом в исследованиях графов линейных расширений:

      Massow MLinear Extension Graphs and Linear Extension Diameter. PhD Dissertation, Technischen Universität Berlin. - Berlin: 2009.

      В данный момент читаю диссертацию, а препринты Ройтера оставил на десерт.

      Наибольший интерес вызвали результаты об операциях на частично упорядоченных множествах (посетах) относительно которых графы линейных расширений (ГЛР) инвариантны. Также интересно было увидеть контрпример гипотезе о том, что ГЛР зависят только от графа сравнимости.

      Интересно заметить, что диссертация защищена 11 декабря прошлого (2009) года, а опубликована при этом на текущую дату одна статья и еще одна статья подана на рассмотрение. Больше статей у автора по теме диссертации нет.

      Tuesday, January 26, 2010

      Перелік наукових фахових видань з фізико-математичних наук

      В Википедии соорудил список ваковских изданий по физ.-мат. наукам.

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

      Со временем, думаю, стоит добавить комментарии и какую-то статистику к этому списку.

      Список является копией оригинала с сайта ВАК Украины, включая все ошибки, которые там содержатся, например: дублирование изданий, неправильные названия.

      Вторая статья

      В номере 2 за 2009 год журнала "Таврический вестник информатики и математики" напечатана статья моего руководителя и вашего покорного слуги. Эта статья была отослана в редакцию год назад.

      Bondarenko O.S., Kozin I.V. Evolutionary fragmentary algorithm for permutation flow shop problem // Таврический вестник информатики и математики. - 2009. - №2. - С. 47-51.

      Friday, January 22, 2010

      Препринт

      В некоторых университетах принято результаты научной работы распространять в виде препринтов. Чтобы это было характерно для украинских ВУЗов, утверждать не готов.

      Удивила одна диссертация 2008 года, написанная в математическом институте им. Стеклова, а именно: список из трех статей, опубликованных по теме диссертации. Две из которых депонированы в ВИНИТИ. Вероятно, результаты работы этого молодого человека достаточно серьёзны, что и с одной публикацией он смог защититься.

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

      Как это следует из оформления статьи, ее планируется отправить в Вестник Киевского университета.

      Бондаренко О.С. Розбиття пермутоедра.

      Wednesday, January 6, 2010

      Теория частичных порядков 2

      В статье [1] упоминается о том, что граф линейных расширений $G(P)$ не является инвариантом сравнимости, при этом дается ссылка на [2].

      Удалось найти работу [3], в которой отыскивается число линейных расширений с минимильным числом скачков.

      В работе [1] приводится интересная теорема о том, что диаметр $G(P)$ равен числу несравнимых пар в минимальном двухмерном расширении $P$.
      1. Felsner S. The Linear-Extension-Diameter of a Poset / S. Felsner, K. Reuter // SIAM Journal on Discrete Mathematics, 1999.
      2. K. Reuter Linear Extensions of a Poset as Abstract Convex Sets, Preprint, Universitaet Hamburg, 1996.
      3. H.C. Jung Counting jump optimal linear extensions of some posets // Recent progress in algebra, AMS, 1999.

      Monday, January 4, 2010

      Теория частичных порядков

      Изучаю последние несколько дней теорию частичных порядков [1] с ударением на следующие вопросы:
      1. Линейные расширения частичных порядков и их число для различных классов порядков.
      2. Инварианты графов сравнимости для соответствующих порядков.
      Число линейных расширений данного линейного порядка является инвариантом графа сравнимости, также как и размерность Душника-Миллера.
      Искал, но пока не нашел какие-либо описания такого параметра множества линейных расширений, как число линейных расширений с числом скачков (jump (setup) number) [2] или числом cтупенек (bump (stair) number) в заданном интервале. Известны задачи о нахождении перестановки с минимальным числом скачков (ступенек). Меня интересует число линейных расширений данного порядка с нулевым числом ступенек.

      Кроме того, не нахожу ничего о выпуклых разбиениях симметрической группы.

      1. Graham R.L. et al. Handbook of combinatorics Vol. 1.
      2. Лозин В.В. E-свободные двудольные графы / Дискретный анализ и исследование операций, 2000.