Journal of the American Planning Association

We consider the problem of constructing a single processor task schedule with minimization of peak resource usage. An example of the resource is the main memory of the target computer. Task set to be scheduled is represented as a directed acyclic graph every node of which is marked with the amount of resource used by the corresponding task. The resource allocated to a task is released on completion of the last (according to the schedule) immediate successor of this task in the graph. Correctness constraint on the schedule is the partial order specified by the task graph. Task duration values are not considered. The formal statement of the problem is provided. To solve the problem, we propose an ant colony algorithm modified so that the pheromone matrix reflects the desirability of pairwise order in the schedule for every pair of tasks, not only for pairs of adjacent tasks. During the schedule construction, for every task the algorithm chooses its position in the schedule, in contrast to existing ant colony scheduling algorithms that construct schedule in increasing order of positions (left-to-right) choosing a task for every next position. Experimental evaluation of the algorithm was conducted on two sets of task graphs. The first set contains graphs generated in such a way that the estimation for the optimum value of the goal function is known a priori. Graphs from the second set are “layered,” and their structure corresponds to the structure of multistage data processing applications. In both sets, the graphs are generated randomly with respect to specified generation parameters and constraints on the graph structure. The experiments indicate high precision and stability of the proposed ant colony algorithm.

The paper studies a model of a planar beam structure described by a fourth-order boundary value problem on a geometric graph. Elastic-hinge joint conditions are posed at the interior vertices of the graph. We study the properties of the spectral points of the corresponding spectral problem, prove upper bounds for the eigenvalue multiplicities, and show that the eigenvalue multiplicities depend on the graph structure (the number of boundary vertices, cycles, etc.). We give an example showing that our estimates are sharp.

The aim of this paper is to study the solvability of inverse problems of determining, together with the solution of the heat equation, its right-hand side or an unknown external influence. The specific feature of the problems studied is that the unknown external influence is determined by two functions of which one depends only on the spatial variable and the other, only on the time variable.

The eternal vertex cover problem is a version of the graph vertex cover problem that can be represented as a dynamic game between two players (the Attacker and the Defender) with an infinite number of steps. At each step, there is an arrangement of guards over the vertices of the graph forming a vertex cover. When the Attacker attacks one of the graph’s edges, the Defender must move the guard along the attacked edge from one vertex to the other. In addition, the Defender can move any number of other guards from their current vertices to some adjacent ones to obtain a new vertex cover. The Attacker wins if the Defender cannot build a new vertex cover after the attack. In this paper, we propose a procedure that allows us to answer the question whether there exists a winning Defender strategy that permits protecting a given vertex cover for a given finite number of steps. To construct the Defender strategy, the problem is represented as a dynamic Stackelberg game in which at each step the interaction of the opposing sides is formalized as a two-level mathematical programming problem. The idea of the procedure is to recursively check the 1-stability of vertex covers obtained as a result of solving lower-level problems and to use some information about the covers already considered.

A system of $$ m $$ Boolean equations can be solved by a sequential sampling method using an $$ m $$ -step algorithm, where at the $$ i $$ th step the values of all variables essential for the first $$ i $$ equations are sampled and false solutions are rejected based on the right-hand sides of the equations, $$ i=1,\dots ,m $$ . The estimate of the complexity of the method depends on the structure of the sets of essential variables of the equations and attains its minimum after some permutation of the system equations. For the optimal permutation of equations we propose an algorithm that minimizes the average computational complexity of the algorithm under natural probabilistic assumptions. In a number of cases, the construction of such a permutation is computationally difficult; in this connection, other permutations are proposed which are computed in a simpler way but may lead to nonoptimal estimates of the complexity of the method. The results imply conditions under which the sequential sampling method degenerates into the exhaustive search method. An example of constructing an optimal permutation is given.

The paper considers a mathematical model of the filtration of two immiscible incompressible fluids in deformable porous media. This model is a generalization of the Musket–Leverett model, in which porosity is a function of the space coordinates. The model under study is based on the equations of conservation of mass of liquids and porous skeleton, Darcy’s law for liquids, accounting for the motion of the porous skeleton, Laplace’s formula for capillary pressure, and a Maxwell-type rheological equation for porosity and the equilibrium condition of the “system as a whole.” In the thin layer approximation, the original problem is reduced to the successive determination of the porosity of the solid skeleton and its speed, and then the elliptic-parabolic system for the “reduced” pressure and saturation of the fluid phase is derived. In view of the degeneracy of equations on the solution, the solution is understood in a weak sense. The proofs of the results are carried out in four stages: regularization of the problem, proof of the maximum principle, construction of Galerkin approximations, and passage to the limit in terms of the regularization parameters based on the compensated compactness principle.

The paper considers the following problem. Given a set of Euclidean vectors, find several clusters with a restriction on the maximum scatter of each cluster so that the size of the minimum cluster would be maximum. Here the scatter is the sum of squared distances from the cluster elements to its centroid. The NP-hardness of this problem is proved in the case where the dimension of the space is part of the input.

The aim of this paper is to acquaint applied mathematicians interested in the possibilities of applying methods for solving inverse problems in mathematical modeling in natural sciences and engineering to economic problems with our papers in this field. These papers refer to the problem of verifying the market demand theory, developed by the first author based on the revision of the unrealistic axiomatic neoclassical theory of individual demand within the framework of general scientific methodology. At the same time, the artificial object of individual theory—a rational and independent individual who maximizes his/her utility function—was replaced by a “statistical ensemble of consumers” of the market under study, and the postulates of individual theory became scientific hypotheses of the new theory. The verification of this theory consists in elucidating the question of rationalizing the statistical market demand by the collective utility function. This problem refers to the inverse problems of mathematical theories of real phenomena, which are usually ill posed and have many solutions. The solution of such problems consists in their regularization with involvement of additional information about the desired solution. Our method for verifying the market demand theory is a development of the nonparametric Afriat–Varian demand analysis with using “economic indices” of market demand as additional information, which allows obtaining solutions with various substantive properties.

We consider a sequence of block-separable convex programming problems describing the resource allocation in multiagent systems. We construct several iterative algorithms for setting the resource prices. Under various assumptions about the utility functions and resource constraints, we obtain estimates for the average deviation (regret) of the objective function from the optimal value and the constraint residuals. Here the average is understood as the expectation for independent identically distributed data and as the time average in the online optimization problem. The analysis of the problem is carried out by online optimization methods and duality theory. The algorithms considered use the information concerning the difference between the total demand and supply that is generated by agents’ reactions to prices and corresponds to the constraint residuals.

The three-dimensional flow of a system of a viscous heat-conducting fluid and a binary mixture with a common interface in a layer bounded by solid walls is studied. A radial time-varying temperature distribution is specified on the lower substrate; the upper wall is assumed to be thermally insulated. Assuming a small Marangoni number, the structure of a steady-state flow is described depending on the layer thickness ratio and taking into account the influence of mass forces. The solution of the nonstationary problem is determined in Laplace transforms by quadratures. It is shown that if the given temperature on the lower substrate stabilizes over time, then with increasing time the solution reaches the resulting steady-state mode only under certain conditions on the initial distribution of concentrations in the mixture.

The problem of identifying Volterra kernels is an important stage in the construction of integral models of nonlinear dynamical systems based on the tool of Volterra series. The paper considers a new class of two-dimensional integral equations that arise when recovering nonsymmetric kernels in a Volterra polynomial of the second degree, where $$ x(t) $$ is the input vector function of time. The strategy for choosing test signals used to solve this problem is based on applying piecewise linear functions (with a rising edge). An explicit inversion formula is constructed for the selected type of Volterra equations of the first kind with variable integration limits. The questions of existence and uniqueness of solutions of the corresponding equations in the class $$ C_{[0,T]} $$ are studied.

This paper is devoted to the construction of a time-optimal method for measuring the maximum permissible (critical) value of the supply voltage (as well as other parameters) of the device on which the cryptographic algorithm is performed. Knowledge of these values is necessary for successful conduct of error injection, as part of a fault attack. The method is based on dynamic programming.

A general method for the enumeration of various classes of chord diagrams with even and odd numbers of chord intersections is considered. The method is based on the calculation of the Pfaffian and Hafnian of the constraint matrix characterizing a class of diagrams.

The paper examines the problem of the distribution of public space. We use the methods of cooperative game theory to solve this problem. Players are districts, while the value of the characteristic function is the total number of people interested in a particular type of public space in the areas under consideration. The axioms that are characteristic of the problem of division are compiled. A special value of the cooperative game is derived that depends on the weights of the players. It is shown how to choose the weights by optimization methods.

This paper proposes a new approach to improving image quality in pulsed X-ray tomography. The method is based on establishing a functional dependence of the reconstructed images on the duration of the probing pulses and applying an extrapolation procedure. The numerical experiments demonstrated that the developed algorithm effectively suppresses the influence of scattered radiation and significantly increases image contrast. The proposed alternative approach allows substantially increasing the stability of the method even for media containing strong scattering inhomogeneities and with a significant level of noise in the projection data. In addition, the algorithm has greater stability to errors in the source data caused by an increase in the duration of the probing pulses. The numerical experiments confirmed the high efficiency of the extrapolation tomography algorithm for recovering the internal structure of the test object.