Sunday, July 17, 2011

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

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.

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 находит все-лишь одну статью.