In this paper, we consider some scheduling problems on a single machine, where weighted or unweighted total tardiness has to be maximized in contrast to usual minimization problems. These problems are theoretically important and have also practical interpretations. For the weighted tardiness maximization problem, we present an NP-hardness proof and a pseudo-polynomial solution algorithm. For the unweighted total tardiness maximization problem with release dates, NP-hardness is proven. Complexity results for some other classical objective functions (e.g., the number of tardy jobs, total completion time) and various additional constraints (e.g., deadlines, weights and/or release dates of jobs may be given) are presented as well.

Mechanism Design (MD) is a branch of game theory which deals with conflict situations involving a principal and a set of active agents (usually in the presence of asymmetric information). Mechanism design theory delivers a solution to many management problems in the form of a control mechanism, (i.e., a formalized routine of decision-making). Formal results of MD can change the fundamentals of managerial practice by introducing decision-making mechanisms in organizations, which are efficient and robust with respect to employees’ self-serving behaviour. The proposed book seeks a more intensive application of MD methodology and its formal results in organizations. The main aim of the book is to provide readers with the basics of an MD-based view on managerial problems, so that intra-firm policies can be analysed through the looking glass of employees’ behavioural response. A systematic introduction of the underlying MD methodology is combined with a collection of ready-to-use mechanisms for solving typical management problems. The use of MD by individual managers is facilitated by bringing together mathematical and business literature in a single treatise. This book is not a purely academic monograph as it contains as few formulas as possible, and no formal proofs (references to formal results are provided throughout the text). Courses on MD for managers are not common in business schools now, and our book represents the perfect material for such a course. (Imprint: Nova)

Описываются основные общия проблемы, возникающие при машинном обучении: 1) Есть ли хорошая модель в выбранном классе. 2) Можно ли надеяться, что модель, хорошо работающая на материале обучения, будет хорошо работать и на новых данных. 3)Есть ли эффективный алгоритм выбора подходяшей модели их заданного класса.

Abstract: The walk distances in graphs have no direct interpretation in terms of walk weights, since they are introduced via the logarithms of walk weights. Only in the limiting cases where the logarithms vanish such representations follow straightforwardly. The interpretation proposed in this chapter rests on the identity ln det B = tr ln B applied to the cofactors of the matrix I−tA, where A is the weighted adjacency matrix of a weighted multigraph and t is a sufficiently small positive parameter. In addition, this interpretation is based on the power series expansion of the logarithm of a matrix. Kasteleyn (Graph theory and crystal physics. In: Harary, F. (ed.) Graph Theory and Theoretical Physics Academic, London, 1967) was probably the first to apply the foregoing approach to expanding the determinant of I−A. We show that using a certain linear transformation the same approach can be extended to the cofactors of I−tA, which provides a topological interpretation of the walk distances.