PhD Project blog

NP-complete problem which is neither NP-complete in the strong sense nor solvable by pseudopolynomial algorithms?

noreply@blogger.com (Oleksandr) — Sun, 17 Jul 2011 07:38:00 +0000

Recently I've posted on cstheory a question that is described in the title of this post. Since then I've received only one comment and one answer. I think the possible answer to it can be a list of NP-complete problems in the ordinary sense such that no pseudopolynomial algorithm is known for them.

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

noreply@blogger.com (Oleksandr) — Fri, 05 Nov 2010 18:02:00 +0000

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.

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

noreply@blogger.com (buenasdiaz) — Fri, 29 Oct 2010 18:27:00 +0000

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:

The performance of a memory allocation algorithm by Jeffrey David Ullman
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.

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

noreply@blogger.com (buenasdiaz) — Fri, 23 Jul 2010 23:02:00 +0000

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

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

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

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

исходной задачи."

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

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

\[|\mathcal{P}'|\leq |\mathcal{P}|."\]

Приведем основные понятия в порядке их упоминания в работе (1) с авторскими комментариями.

Понятие NF-активной упаковки. Собственно говоря, именно для алгоритма Next Fit и доказывается о принадлежности оптимума множеству кодов.
Понятие регулярной перестановки и упаковки. Для регулярной упаковки доказывается лемма, аналогичная Лемме 2.
Понятие максимальной упаковки. Для этой упаковки лемма, аналогична Лемме 2 не приводится, хотя из Теоремы 3 можно сделать вывод, что ее доказательство неявно предполагается.

Библиография

Giffler J., Thompson G.L., “Algorithms for solving production scheduling problems,” Operations Research, Vol. 8, 1960, pp. 487–503.

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

noreply@blogger.com (buenasdiaz) — Thu, 22 Jul 2010 20:31:00 +0000

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

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

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

В то же время в первой работе об алгоритмах с оценками в худшем случае для упаковки в полосу этот вопрос рассматривался для алгоритма "bottom-up left-justified" (BL) [1], эта же работа и вводит в оборот этот алгоритм. Там было доказано, что существуют примеры, где BL не дает оптимального решения.

BS Baker, EG Coffman and RL Rivest, Orthogonal packings in two dimensions. SIAM Journal on Computing 9/4 (1980), pp. 846–855.

DOOR-2010

noreply@blogger.com (buenasdiaz) — Wed, 07 Jul 2010 17:20:00 +0000

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

Идея

noreply@blogger.com (buenasdiaz) — Fri, 18 Jun 2010 23:41:00 +0000

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

Web Based LaTeX Editors

noreply@blogger.com (buenasdiaz) — Fri, 18 Jun 2010 10:01:00 +0000

Чтобы не случилось с исходными текстами на LaTeX (далее тех-файлы) твоих статей в оффлайне, или с твоим техом, при использовании онлайн редакторов и хранении исходников где-нибудь онлайн, ты застрахован от таких неприятностей. Хранить онлайн можно было что-угодно и раньше, только вот не было возможности компилировать онлайн тех-файлы. Теперь же этa возможность имеется и даже как минимум в четырех следующих вариантах:

http://docs.latexlab.org/ (скомпилировать удалось, но не поддерживается кириллица, пока все бесплатно, )
http://www.scribtex.com/ (здесь кириллица поддерживается, бесплатно 3 проекта, 1 сотрудник, 50 Мб места, скомпилировать удалось)

http://www.verbosus.com/ (интерфейс неприятный, есть ограничения на бесплатное пользование сервисом, хотя скомпилировать удалось)
http://monkeytex.bradcater.webfactional.com/ (скомпилировать у меня здесь не вышло, каких-либо ограничений я не нашел)

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

noreply@blogger.com (buenasdiaz) — Sun, 30 May 2010 10:45:00 +0000

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

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

noreply@blogger.com (buenasdiaz) — Wed, 19 May 2010 13:38:00 +0000

Нашел сейчас статью под названием "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."

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

noreply@blogger.com (buenasdiaz) — Fri, 14 May 2010 18:34:00 +0000

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

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

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.
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.
Dushnik B. Partially Ordered Sets / Ben Dushnik and E. W. Miller // American Journal of Mathematics, Vol. 63, No. 3 (Jul., 1941), pp. 600-610.

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

noreply@blogger.com (buenasdiaz) — Tue, 11 May 2010 19:34:00 +0000

Группа результатов по графам линейных расширений
Группа результатов по задаче с периодическим работами

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

Разбиение пермутоэдров графами линейных расширений
Вероятность генерации максимальной популяци
Результаты о сжатии-расширении популяции (псевдовыпуклый поиск по Моральо)

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

noreply@blogger.com (buenasdiaz) — Sat, 13 Mar 2010 21:22:00 +0000

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

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

noreply@blogger.com (buenasdiaz) — Wed, 03 Mar 2010 23:14:00 +0000

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

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

noreply@blogger.com (buenasdiaz) — Thu, 11 Feb 2010 20:53:00 +0000

Во Львове издается журнал "Математичні студії". Мне он интересен тем, что

входит в список ваковских изданий по физ.-мат. наукам
рецензируемый
издается 6 раз в год
рукописи статей принимаются только в TeX.

Сегодня отослал свою статью "Regular subgraphs of linear extension graphs" в редакцию. Статья является переработанной версией препринта, который предполагалось отослать в Вестник Киевского университета. Поскольку для того, чтобы получить рецензию в Вестник, необходимо быть знакомым с членом редколлегии, было решено выбрать другой журнал.

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

noreply@blogger.com (buenasdiaz) — Sat, 06 Feb 2010 09:33:00 +0000

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

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

noreply@blogger.com (buenasdiaz) — Thu, 28 Jan 2010 17:37:00 +0000

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

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

Относительно какой (-их) операции (-ий) остается неизменным данное свойство некоторого класса ГЛР.
Какое (-ие) свойство (-ва) некоторого класса ГЛР инвариантно (-ы) относительно данного набора операций.

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

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

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

noreply@blogger.com (buenasdiaz) — Wed, 27 Jan 2010 17:06:00 +0000

Где-то в начале этого января удалось узнать о двух статьях, в которых были рассмотрены вопросы, над которыми я тогда работал. Сегодня, благодаря профессору Стефану Фельснеру, удалось получить доступ к их электронным версиям. Дело в том, что это препринты, которые нигде не публиковались. Стефан отсканировал эти препринты и теперь они доступны в сети:

Reuter K. The Comparability Graph and the Graph of Linear Extensions of a Poset. Hamburger Beiträge zur Mathematik, Heft 57 (1996).
Reuter K. Linear Extensions of a Poset as Abstract Convex Sets. Hamburger Beiträge zur Mathematik, Heft 56 (1996).

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

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

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

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

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

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

noreply@blogger.com (buenasdiaz) — Tue, 26 Jan 2010 17:32:00 +0000

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

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

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

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

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

noreply@blogger.com (buenasdiaz) — Tue, 26 Jan 2010 15:37:00 +0000

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

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

Препринт

noreply@blogger.com (buenasdiaz) — Fri, 22 Jan 2010 16:55:00 +0000

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

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

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

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

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

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

noreply@blogger.com (buenasdiaz) — Wed, 06 Jan 2010 09:22:00 +0000

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

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

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

Felsner S. The Linear-Extension-Diameter of a Poset / S. Felsner, K. Reuter // SIAM Journal on Discrete Mathematics, 1999.
K. Reuter Linear Extensions of a Poset as Abstract Convex Sets, Preprint, Universitaet Hamburg, 1996.
H.C. Jung Counting jump optimal linear extensions of some posets // Recent progress in algebra, AMS, 1999.

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

noreply@blogger.com (buenasdiaz) — Mon, 04 Jan 2010 20:26:00 +0000

Изучаю последние несколько дней теорию частичных порядков [1] с ударением на следующие вопросы:

Линейные расширения частичных порядков и их число для различных классов порядков.
Инварианты графов сравнимости для соответствующих порядков.

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

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

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

LaTeX,WordPress и "Theory of Convex Structures"

noreply@blogger.com (buenasdiaz) — Fri, 18 Dec 2009 17:35:00 +0000

Установил на этом блоге скрипт, который позволяет писать на LaTeX прямо в тексте поста, что очень облегчает набор формул. Оказалась, что проблема с выравниванием относительно базовой линии не только у меня, но и других пользователей.

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

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

Удалось заполучить основной труд современности по аксиоматической выпуклости "Theory of Convex Structures" Марселя Л. Й. ван де Веля (M.L.J. van de Vel).

Второй раздел диссертации

noreply@blogger.com (buenasdiaz) — Thu, 10 Dec 2009 12:31:00 +0000

Вчера мне научный руководитель озвучил задание: начать писать второй раздел диссертации.
Говоря о том, что должно войти в этот раздел, сразу же приходит идея о требованиях ВАК. В соответствующем документе "Основні вимоги до дисертацій та авторефератів дисертацій" в пункте 3.5 требуется следующее:

У другому розділі, як правило, обґрунтовують вибір напряму досліджень, наводять методи вирішення задач і їх порівняльні оцінки, розробляють загальну методику проведення дисертаційних досліджень. В теоретичних роботах розкривають методи розрахунків, гіпотези, що розглядають, в експериментальних — принципи дії і характеристики розробленої апаратури, оцінки похибок вимірювання.

Таким образом, во второй раздел должно войти описание методов, используемых при проведении исследования.
Исходя из вышесказанного, могу набор методов, используемых в своей работе, разделить на две широкие группы:

Теоретические. Здесь исследуется несколько упрощенная модель генетического алгоритма, для которой делаются выводы. Использовались понятия и результаты метрической теории графов, включая понятие выпуклости на графах, а также методы теории вероятностей.
Экспериментальные. Здесь тестируется программная реализация генетического алгоритма, другими словами, реализуется вычислительный эксперимент. Для оценки результатов проводится сравнение со случайным поиском, другими эвристиками и метаэвристиками, а также с уже известными оптимальными решениями. Кроме того, вычислительный эксперимент используется для подтверждения или опровержения теоретических гипотез.

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

План раздела может быть следующий.

2. Основные теоретические сведения и методы исследования

2.1 Методика разбиения пространства

2.1.1 История

2.1.2 Теория форм и теория геометрического кроссовера

2.2 Методы теоретических исследований

2.2.1 Некоторые понятия из теории метрической выпуклости

2.2.2 Методы теории вероятностей

2.3 Методы экспериментальных исследований

2.3.1 Вычислительный эксперимент

2.3.2 Способы оценки результатов эксперимента

2.3.3 Методы математической статистики

2.4 Выводы ко второму разделу