In the article E.R. Gafarov, A.A. Lazarev, F. Werner, Single machine scheduling problems with financial resource constraints: Some complexity results and properties, Mathematical Social Sciences, 62 (2011), 7–13, the following mistake is found in Section 3.2, where the authors consider the problem denoted as 1|NR, dj = d, gj = g|  Tj and claim that it is NP-hard. In the proof, a reduction from the Partition Problem was used which is not polynomial, since M exponentially depends on n. However, it is not difficult to correct this proof. The main idea of using Mn−i+1 was that the processing time of a job belongs to a pair with the smallest number being greater than the total sum of the processing times of all jobs from the pairs with larger numbers, e.g., for the job V2: p2 ≫ n i=2(p2i−1 + p2i). Instead of using p2i = Mn−i+1, where M = (n  bj)n (see the definition of the instance given in (3) on page 11), we can consider, e.g., p2i = 2n · 2n−i+1M, where M = (n  bj). In this case, the reduction will be polynomial in the input length, if we suppose that all digits used are coded in a binary system with approximately 2n zero–one symbols per digit.

In this note, we consider a single machine scheduling problem with generalized total tardiness objective function. A pseudo-polynomial time solution algorithm is proposed for a special case of this problem. Moreover, we present a new graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted number of tardy jobs on a single machine. The latter algorithm improves the complexity of an existing pseudo-polynomial algorithm by Lawler. Computational results are presented for both special cases considered.

Рассмотрена задача статистической линеаризации входо-выходного отображения многомерных систем с гауссовским белошумным входным процессом по теоретико-информационному критерию. В качестве теоретико-вероятностной меры зависимости используется основанная на энтропии по Реньи порядка 2 дивергенция Коши-Шварца, геометрический смысл которой – минус логарифм косинуса угла между двумя плотностями распределения вероятностей, первое из которых – совместная плотность распределения пары случайных величин, а второе – произведение их маргинальных плотностей. Соответствующий теоретико-информационный критерий формулируется как условие совпадения дивергенции Коши-Шварца i-ой компоненты выходного процесса и j-ой компоненты входного процесса системы и i-ой компоненты выходного процесса и j-ой компоненты входного процесса модели. Получены явные выражения для матричнозначных коэффициентов весовой функции линеаризованной модели. Такие выражения основаны на квази-состоятельной по Реньи меры зависимости, получаемой некоторым преобразованием дивергенции Коши-Шварца. При этом под квази-состоятельностью меры зависимости по Реньи подразумевается ее соответствие всем аксиомам Реньи за исключением условия инвариантности относительно монотонных преобразований случайных величин, которое заменяется аналогичным условием относительно аффинных преобразований.

The walk distances in graphs are defined as the result of appropriate transformations of the $\sum_{k=0}^\infty(tA)^k$ proximity measures, where $A$ is the weighted adjacency matrix of a connected weighted graph and $t$ is a sufficiently small positive parameter. The walk distances are graph-geodetic, moreover, they converge to the shortest path distance and to the so-called long walk distance as the parameter $t$ approaches its limiting values. In this paper, simple expressions for the long walk distance are obtained. They involve the generalized inverse, minors, and inverses of submatrices of the symmetric irreducible singular M-matrix ${\cal L}=\rho I-A,$ where $\rho$ is the Perron root of $A.$