• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Найдено 14 публикаций
Сортировка:
по названию
по году
Статья
Malyshev D. Journal of Combinatorial Optimization. 2016. Vol. 32. No. 1. P. 226-243.
Добавлено: 4 апреля 2015
Статья
Larisa Komosko, Mikhail Batsyn, Pablo San Segundo . et al. Journal of Combinatorial Optimization. 2016. No. 4. P. 1665-1677.
Добавлено: 13 июля 2015
Статья
Goldengorin B., Malyshev D., Pardalos P. M. et al. Journal of Combinatorial Optimization. 2015. Vol. 29. No. 2. P. 433-450.

The notion of a tolerance is a helpful tool for designing approximation and exact algorithms for solving combinatorial optimization problems. In this paper we suggest a tolerance-based polynomial heuristic algorithm for the weighted independent set problem. Several computational experiments show that our heuristics works very well on graphs of a small density

Добавлено: 3 октября 2013
Статья
Malyshev D. Journal of Combinatorial Optimization. 2014. Vol. 27. No. 2. P. 345-354.

The notion of a boundary graph class was recently introduced for a classification of hereditary graph classes according to the complexity of a considered problem. Two concrete graph classes are known to be boundary for several graph problems. We formulate a criterion to determine whether these classes are boundary for a given graph problem or not. We also demonstrate that the classes are simultaneously boundary for some continuous set of graph problems and they are not simultaneously boundary for another set of the same cardinality. Both families of problems are constituted by variants of the maximum induced subgraph problem.

Добавлено: 7 февраля 2013
Статья
Kotsireas I. S., Koukouvino C., Pardalos P. M. et al. Journal of Combinatorial Optimization. 2012. Vol. 24. No. 4. P. 508-522.

В этой статье мы демонстрируем, что исследование  взвешивания матрицы, построенной из двух циркулянтов, можно рассматривать как задачу минимизации вместе с двумя компетентными генетическими алгоритмами для поиска оптимума целевой функции. Мотивация для борьбы с беспорядочными  генетическими  алгоритмами (MGA) определяется новаторскими результатами  Голдберга, относительно способности участка MGA поставить жесткие гены вместе в решение, которое прямо указывает на структурные закономерности во взвешивании матриц. Для того, чтобы воспользоваться преимуществом  некоторых свойств двух троичных последовательностей  с нулевой автокорреляцией, мы используем применение быстрого беспорядочного генетического алгоритма  (fmGA), где мы объединяем MGA с передовыми методами. Это преобразование задачи  взвешивания  матрицы в случае задачи комбинаторной оптимизации представляется перспективным, так как мы решили две задачи взвешивания матрицы, которые  перечислены во втором издании «Руководства по комбинаторным разработкам».

Добавлено: 23 января 2013
Статья
Dagaev D., Suzdaltsev A. Journal of Combinatorial Optimization. 2018. Vol. 35. No. 1. P. 170-188.
Добавлено: 1 августа 2017
Статья
Albdaiwi B., Ghosh D., Goldengorin B. I. Journal of Combinatorial Optimization. 2011. Vol. 21. No. 3. P. 348-363.

In this paper, we use a pseudo-Boolean formulation of the p-median problem and using data aggregation, provide a compact representation of p-median problem instances. We provide computational results to demonstrate this compactification in benchmark instances. We then use our representation to explain why some p-median problem instances are more difficult to solve to optimality than other instances of the same size. We also derive a preprocessing rule based on our formulation, and describe equivalent p-median problem instances, which are identical sized instances which are guaranteed to have identical optimal solutions.

Добавлено: 31 июля 2012
Статья
D. V. Gribanov, D.S. Malyshev, P. M. Pardalos et al. Journal of Combinatorial Optimization. 2018. Vol. 35. No. 4. P. 1128-1146.
Добавлено: 19 февраля 2018
Статья
Mikhail Batsyn, Boris Goldengorin, Evgeny Maslov et al. Journal of Combinatorial Optimization. 2014. Vol. 27. No. 2. P. 397-416.

In this paper we present improvements to one of the most recent and fastest branch-and-bound algorithm for the maximum clique problem—MCS algorithm by Tomita et al. (Proceedings of the 4th international conference on Algorithms and Computation, WALCOM’10, pp. 191–203, 2010). The suggested improvements include: incorporating of an efficient heuristic returning a high-quality initial solution, fast detection of clique vertices in a set of candidates, better initial colouring, and avoiding dynamic memory allocation. Our computational study shows some impressive results, mainly we have solved p_hat1000-3 benchmark instance which is intractable for MCS algorithm and got speedups of 7, 3000, and 13000 times for gen400_p0.9_55, gen400_p0.9_65, and gen400_p0.9_75 instances correspondingly.

Добавлено: 17 февраля 2013
Статья
Babenko M. A., Karzanov A. V. Journal of Combinatorial Optimization. 2012. Vol. 24. No. 3. P. 202-228.

Рассмотрим неориентированный граф $G = (VG, EG)$, в котором выделено множество терминалов $T \subseteq VG$, и заданы неотрицательные пропускные способности $c(v)$, а также стоимости $a(v)$ для всех вершин $v\in VG$. Путь в $G$ называется $T$-путем, если его концы представляют собой различные терминалы. Мультипотоком называется функция $F$, приписывающую каждому $T$-пути $P$ неотрицательный рациональный вес $F(P)$. Мультипоток называется допустимым, если сумма весов $T$-путей, проходящих через каждую вершину $v$, не превышает $c(v)$. Величиной $F$ называется сумма весов $F(P)$, а стоимостью $F$ называется сумма  (по всем $T$-путям $P$) произведений $F(P)$ на стоимости путей $P$ относительно функции $a$. В данной работе мы обобщаем известные результаты, касающиеся мультипотоков с ограничениями пропускных способностей на ребрах, и доказываем, что задача нахождения мультипотока минимальной стоимости среди мультипотоков, имеющих максимальную величину всегда имеет полуцелое прямое и двойственное решения. Более того, мы описываем сильнополиномиальный алгоритм, строящий такие решения.

Добавлено: 27 января 2013
Статья
Li J., Li Y., Pardalos P. M. Journal of Combinatorial Optimization. 2016. Vol. 31. No. 2. P. 515-532.

A new variant of multi-depot vehicle routing problem with time windows is studied. In the new variant, the depot where the vehicle ends is flexible, namely, it is not entirely the same as the depot that it starts from. An integer programming model is formulated with the minimum total traveling cost under the constrains of time window, capacity and route duration of the vehicle, the fleet size and the number of parking spaces of each depot. As the problem is an NP-Hard problem, a hybrid genetic algorithm with adaptive local search is proposed to solve it. Finally, the computational results show that the proposed method is competitive in terms of solution quality. Compared with the classic MDVRPTW, allowing flexible choice of the stop depot can further reduce total traveling cost.

Добавлено: 26 января 2016
Статья
Granata D., Behdani B., Pardalos P. M. Journal of Combinatorial Optimization. 2012. Vol. 24. No. 4. P. 459-467.

Мы описываем класс  сложности нескольких проблем по поиску траектории  в хроматическом  направленном графе. Хроматический граф  определяется как граф G, множество вершин которого разбивается на X(G) стабильные множества, где  X(G) обозначает  хроматическое число G. Мы показываем, что нахождение простой траектории, которая соответствует всем хромам в хроматическом направленном графе, NP – сложное, так же как и задачи по поиску самой короткой и самой длинной траектории между  двумя определенными точками пересечения.

Добавлено: 24 января 2013
Статья
Malyshev D. Journal of Combinatorial Optimization. 2017. Vol. 33. No. 3. P. 809-813.
Добавлено: 17 марта 2016
Статья
Malyshev D. Journal of Combinatorial Optimization. 2016. Vol. 31. No. 2. P. 833-845.
Добавлено: 18 сентября 2014