• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Найдено 18 публикаций
Сортировка:
по названию
по году
Статья
Boros E., Elbassioni K., Gurvich V. et al. Optimization Letters. 2017. Vol. 11. No. 8. P. 1499-1512.

We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph (Formula presented.), with local rewards (Formula presented.), and three types of positions: black (Formula presented.), white (Formula presented.), and random (Formula presented.) forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, even when (Formula presented.). In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this short note, we show that BWR-games can be solved via convex programming in pseudo-polynomial time if the number of random positions is a constant. 

Добавлено: 18 мая 2017
Статья
Mokeev D. B., Malyshev D. Optimization Letters. 2019. P. 1-6.
Добавлено: 4 сентября 2019
Статья
Savchenko A. Optimization Letters. 2017. Vol. 11. No. 2. P. 329-341.

This paper addresses the problem of insufficient performance of statistical classification with the medium-sized database (thousands of classes). Each object is represented as a sequence of independent segments. Each segment is defined as a random sample of independent features with the distribution of multivariate exponential type. To increase the speed of the optimal Kullback-Leibler minimum information discrimination principle, we apply the clustering of the training set and an approximate nearest neighbor search of the input object in a set of cluster medoids. By using the asymptotic properties of the Kullback-Leibler divergence, we propose the maximal likelihood search procedure. In this method the medoid to check is selected from the cluster with the maximal joint density (likelihood) of the distances to the previously checked medoids. Experimental results in image recognition with artificially generated dataset and Essex facial database prove that the proposed approach is much more effective, than an exhaustive search and the known approximate nearest neighbor methods from FLANN and NonMetricSpace libraries.

Добавлено: 10 сентября 2015
Статья
Malyshev D., Pardalos P. M. Optimization Letters. 2016. Vol. 10. No. 8. P. 1593-1612.
Добавлено: 18 декабря 2015
Статья
Ilya Bychkov, Mikhail Batsyn, Panos M. Pardalos. Optimization Letters. 2014. Vol. 8. No. 8. P. 2203-2210.
Добавлено: 21 сентября 2013
Статья
Nikolaev A., Mladenovic N., Todosijevic R. Optimization Letters. 2017. Vol. 11. No. 2. P. 359-376.
Добавлено: 24 декабря 2015
Статья
Gribanov D., Veselov S. Optimization Letters. 2016. Vol. 10. No. 6. P. 1169-1177.
Добавлено: 12 октября 2015
Статья
Tong G., Wu W., Pardalos P. M. et al. Optimization Letters. 2017. Vol. 11. No. 2. P. 419-427.

Consider a graph G = (V, E) and a vertex subset A ⊆ V. A vertex v is positive-influence dominated by A if either v is in A or at least half the number of neighbors of v belong to A. For a target vertex subset S ⊆ V, a vertex subset A is a positive-influence target-dominating set for target set S if every vertex in S is positive-influence dominated by A. Given a graph G and a target vertex subset S, the positive-influence target-dominating set (PITD) problem is to find the minimum positive-influence dominating set for target S. In this paper, we show two results: (1) The PITD problem has a polynomial-time (1+log[3/2*Delta])-approximation in general graphs where Delta is the maximum vertex-degree of the input graph. (2) For target set S with |S| = OMEGA(|V|), the PITD problem has a polynomial-time O(1)-approximation in power-law graphs.

Добавлено: 9 сентября 2015
Статья
Alexander P. Afanas’ev, Sergei M. D., Pchelintsev A. N. et al. Optimization Letters. 2018. Vol. V.12. P. 1-11.
Добавлено: 14 февраля 2019
Статья
Pardalos P. M., Kalyagin V. A. Optimization Letters. 2017. Vol. 11. No. 2. P. 247-247.

Clustering and search techniques are essential to a wide spectrum of applications. Network clustering techniques are becoming common in the analysis of massive data sets arising in various branches of science, engineering, government and industry. In particular, network clustering and search techniques emerge as an important tool in large-scale networks.

This special issue of Optimization Letters contains refereed selected papers presented at the workshop on clustering and search techniques in large scale networks that took place on November 3–8, 2014 at the Laboratory of Algorithms and Technologies for Networks Analysis (LATNA), Higher School of Economics, in Nizhny Novgorod, Russia. The workshop was supported by the Russian Science Foundation Grant RSF 14-41-00039.

This workshop provided a forum for leading as well as beginning researchers and students to discuss recent advances and identify current and future challenges arising in research concerning clustering and search problems in large networks. The papers of this special issue reflect some the problems discussed at the workshop.

We would like to thank the valuable work of authors and reviewers for making this issue possible.

Добавлено: 12 сентября 2016
Статья
Pardalos P. M., Maslov E. V., Lu Z. et al. Optimization Letters. 2012. P. 1-10.
In wireless networks, Connected Dominating Sets (CDSs) are widely used as virtual backbones for communications. On one hand, reducing the backbone size will reduce the maintenance overhead. So how to minimize the CDS size is a critical issue. On the other hand, when evaluating the performance of a wireless network, the hop distance between two communication nodes, which reflect the energy consumption and response delay, is of great importance. Hence how to minimize the routing cost is also a key problem for constructing the network virtual backbone. In this paper, we study the problem of constructing applicable CDS in wireless networks in terms of size and routing cost. We formulate a wireless network as a Disk-Containment Graph (DCG), which is a generalization of the Unit-Disk Graph (UDG), and we develop an efficient algorithm to construct CDS in such kind of graphs. The algorithm contains two parts and is flexible to balance the performance between the two metrics. We also analyze the algorithm theoretically. It is shown that our algorithm has provable performance in minimizing the CDS size and reducing the communication distance for routing.
Добавлено: 11 февраля 2013
Статья
Lazarev A. A., Arkhipov D., Werner F. Optimization Letters. 2016. P. 1-13.

The following special case of the classical NP-hard scheduling problem (Formula presented.) is considered. There is a set of jobs (Formula presented.) with identical processing times (Formula presented.) for all jobs (Formula presented.). All jobs have to be processed on a single machine. The optimization criterion is the minimization of maximum lateness (Formula presented.). We analyze algorithms for the makespan problem (Formula presented.), presented by Garey et al. (SIAM J Comput 10(2):256–269, 1981), Simons (A fast algorithm for single processor scheduling. In: 19th Annual symposium on foundations of computer science (Ann Arbor, Mich., 1978, 1978) and Benson’s algorithm (J Glob Optim 13(1):1–24, 1998) and give two polynomial algorithms to solve the problem under consideration and to construct the Pareto set with respect to the criteria (Formula presented.) and (Formula presented.). The complexity of the presented algorithms is (Formula presented.) and (Formula presented.), respectively, where (Formula presented.) is the accuracy of the input-output parameters. © 2016 Springer-Verlag Berlin Heidelberg

Добавлено: 13 апреля 2016
Статья
Pei J., Liu X., Pardalos P. M. et al. Optimization Letters. 2015. Vol. 9. No. 1. P. 91-104.

This paper investigates the scheduling problems of a single serial-batching machine with independent setup time and deteriorating job processing times. With the assumption of deteriorating jobs, the job processing times are described by an increasing function of their starting times. All the jobs are first partitioned into serial batches and then processed on a single serial-batching machine. Before each batch is processed, an independent constant setup time is required. Two optimization algorithms are proposed to solve the problems of minimizing the makespan and the total number of tardy jobs, respectively. Specifically, for the problem of minimizing the total completion time, two special cases with the smallest and the largest number of batches are studied, and an optimization algorithm is also presented for the special case without setup time.

Добавлено: 14 января 2015
Статья
Buchanan A., Walteros J. L., Butenko S. et al. Optimization Letters. 2014. Vol. 8. No. 5. P. 1611-1617.
Добавлено: 6 июня 2014
Статья
Malyshev D., Pardalos P. M. Optimization Letters. 2015. Vol. 9. No. 5. P. 839-843.

The quadratic programming problem is known to be NP-hard for Hessian matrices with only one negative eigenvalue, but it is tractable for convex instances. These facts yield to consider the number of negative eigenvalues as a complexity measure of quadratic programs. We prove here that the clique problem is tractable for two variants of its Motzkin-Strauss quadratic formulation with a fixed number of negative eigenvalues (with multiplicities).

Добавлено: 26 сентября 2014
Статья
Malyshev D. Optimization Letters. 2014. Vol. 8. No. 8. P. 2261-2270.

The coloring problem is studied in the paper for graph classes defined by two small forbidden induced subgraphs. We prove some sufficient conditions for effective solvability of the problem in such classes. As their corollary we determine the computational complexity for all sets of two connected forbidden induced subgraphs with at most five vertices except 13 explicitly enumerated cases.

Добавлено: 6 марта 2014
Статья
Gribanov D., Chirkov A. Optimization Letters. 2016. Vol. 10. No. 6. P. 1179-1189.
Добавлено: 12 сентября 2016