An approximate solution of one-dimensional piston problem

A new theory of shock dynamics has been developed in the form of a finite number of compatibility conditions along shock rays. It has been used to study the growth or decay of shock strength for accelerating or decelerating piston starting with a nonzero piston velocity. The results show good agreement with those obtained by Harten's high resolution TVD scheme.     

An approximation algorithm for the hierarchical median problem

The hierarchical median problem asks for a hierarchical sequence of solutions to the k-median problems of growing cardinality. The best algorithm known for this problem in the general metric case has competitive ratio 20.71. In the paper, the case is under study that the clients and facilities lie on the real line, as well as the case of a Euclidean space. An algorithm is proposed with competitive ratio 8 in the case of the real line, and 8 + 4√2 (approximately 13.66), in the Euclidean case.     

An approximation algorithm for the Euclidean incremental median problem

In the incremental version of the $k$-median problem, we find a sequence of facility sets $F_1\subseteq F_2\subseteq \cdots \subseteq F_n$, where each $F_k$ contains at most $k$ facilities. This sequence is said to be $\delta$-competitive if the cost of each $F_k$ is at most $\delta$ times the optimum cost of $k$ facilities. The best deterministic (randomized) algorithm available for the metric space has a competitive ratio of $8$ ($7.656$). The best one for the one-dimensional problem finds a $5.828$-competitive sequence. We give a $7.076$-competitive solution for the high-dimensional Euclidean space.     

An approximate analytic solution of the Blasius problem

The [4/3] Pade approximant for the derivative is modified so that the resulting expression has the required asymptotic behavior. This gives an analytical result which represents the solution of the classical Blasius problem on the whole domain.     

An approximate solution for spherical and cylindrical piston problem

A new theory of shock dynamics (NTSD) has been derived in the form of a finite number of compatibility conditions along shock rays. It has been used to study the growth and decay of shock strengths for spherical and cylindrical pistons starting from a non-zero velocity. Further a weak shock theory has been derived using a simple perturbation method which admits an exact solution and also agrees with the classical decay laws for weak spherical and cylindrical shocks.     

Finiteε-subgradient algorithm for approximate solution of the parametric programming problem

Translated from Vychislitel'nye Kompleksy i Modelirovanie Slozhnykh Sistem, pp. 111–117, Moscow State University, 1989.     

An algorithm for finding an approximate solution to the Weber problem on a line with forbidden gaps

Under study is the problem of optimal location of interconnected objects on a line with forbidden gaps. The task is to minimize the total cost of links between objects and between objects and zones. The properties of the problem are found that allowed us to reduce the initial continuous problem to a discrete problem. Some algorithm for obtaining an approximate solution is developed, and the results of a computational experiment are given.     

An exact solution approach for the interdiction median problem with fortification

Systematic approaches to security investment decisions are crucial for improved homeland security. We present an optimization modeling approach for allocating protection resources among a system of facilities so that the disruptive effects of possible intentional attacks to the system are minimized. This paper is based upon the p-median service protocol for an operating set of p facilities. The primary objective is to identify the subset of q facilities which, when fortified, provides the best protection against the worst-case loss of r non-fortified facilities. This problem, known as the r-interdiction median problem with fortification (IMF), was first formulated as a mixed-integer program by Church and Scaparra [R.L. Church, M.P. Scaparra, Protecting critical assets: The r-interdiction median problem with fortification, Geographical Analysis 39 (2007) 129–146]. In this paper, we reformulate the IMF as a maximal covering problem with precedence constraints, which is amenable to a new solution approach. This new approach produces good approximations to the best fortification strategies. Furthermore, it provides upper and lower bounds that can be used to reduce the size of the original model. The reduced model can readily be solved to optimality by general-purpose MIP solvers. Computational results on two geographical data sets with different structural characteristics show the effectiveness of the proposed methodology for solving IMF instances of considerable size.     

An approximate solution of two-dimensional convex piston problem

A new theory of shock dynamics (NTSD) has been used to study the propagation of curved shocks originating from the motion of two-dimensional convex piston of various shapes. The results have been compared with those obtained by Whitham's classical shock dynamics and by TVD version of MacCormack's finite difference scheme.     

An efficient heuristic algorithm for the capacitated p-\! median problem

The capacitated $p$ -median problem (CPMP) is one of the well-known facility-location problems. The objective of the problem is to minimize total cost of locating a set of capacitated service points and allocating a set of demand points to the located service points, while the total allocated demand for each service point is not be greater than its capacity limit. This paper presents an efficient heuristic algorithm based on the local branching and relaxation induced neighborhood search methods for the CPMP. The proposed algorithm is a heuristic technique that utilizes a general mixed integer programming solver to explore neighborhoods. The parameters of the proposed algorithm are tuned by design of experiments. The proposed method is tested on a large set of benchmark instances. The results show that the method outperforms the best method found in the literature.     

An approximate algorithm for a high-multiplicity parallel machine scheduling problem

We consider a high-multiplicity parallel machine scheduling problem where the objective is to minimize the weighted sum of completion times. We suggest an approximate algorithm and we prove that it is asymptotically exact. The algorithm exploits a convex quadratic relaxation of the problem to fix a partial schedule, consisting of most jobs, and then assigns the residual jobs following a simple and general rule. The quality of the obtained solution is evidenced by some numerical tests.     

An algorithm for solving the multi-period online fulfillment assignment problem

This paper develops an optimal solution procedure for the multi-period online fulfillment assignment problem to determine how many and which of a retailer/e-tailer’s capacitated regional warehouse locations should be set up to handle online sales over a finite planning horizon. To reduce the number of candidate solutions in each period, dominance rules from the facility location literature are extended to handle the nonlinear holding and backorder cost implications of our problem. Computational results indicate that multi-period considerations can play a major role in determining the optimal set of online fulfillment locations. In 92% of our test problems, the multi-period solution incorporated fewer openings and closings than myopic single period solutions. To illustrate the use of the model under changing demands, the multi-period solution yielded different supply chain configurations than the myopic single period solution in over 37% of the periods.     

An approximate solution of the axisymmetric contact problem for an elastic sphere

An axisymmetric, fractionally non-linear contact problem for an elastic sphere with a priori unknown boundary of the contactarea is considered. An integral equation for determining the density of the contact pressures is constructed taking account of the shear displacements of the boundary points of the elastic body. An approximate solution, which refines the equations of Hertz' theory, is constructed in the case of a small contact area.     

An algorithm for the approximate solution of integral equations of Mellin type

Summary. The cruciform crack problem of elasticity gives rise to an integral equation of the second kind on [0,1] whose kernel has a fixed singularity at (0,0). We introduce a transformation of [0,1] onto itself such that an arbitrary number of derivatives vanish at the end points 0 and 1. If the transformed kernel is dominated near the origin by a Mellin kernel then we have given conditions under which the use of a modified Euler-Maclaurin quadrature rule and the Nystr?m method gives an approximate solution which converges to the exact solution of the original equation. The method is illustrated with a numerical example. Received May 10, 1994     

Exact and approximate methods for a one-dimensional minimax bin-packing problem

One-dimensional bin-packing problems require the assignment of a collection of items to bins with the goal of optimizing some criterion related to the number of bins used or the ‘weights’ of the items assigned to the bins. In many instances, the number of bins is fixed and the goal is to assign the items such that the sums of the item weights for each bin are approximately equal. Among the possible applications of one-dimensional bin-packing in the field of psychology are the assignment of subjects to treatments and the allocation of students to groups. An especially important application in the psychometric literature pertains to splitting of a set of test items to create distinct subtests, each containing the same number of items, such that the maximum sum of item weights across all bins is minimized. In this context, the weights typically correspond to item statistics derived from difficulty and discrimination indices. We present a mixed zero-one integer linear programming (MZOILP) formulation of this one-dimensional minimax bin-packing problem and develop an approximate procedure for its solution that is based on the simulated annealing algorithm. In two comparisons that focused on 34 practically-sized test problems (up to 6000 items and 300 bins), the simulated annealing heuristic generally provided better solutions than were obtained when using a commercial mathematical programming software package to solve the MZOILP formulation directly.     

An approximate analytical solution of one-dimensional phase change problems in a finite domain

In this paper, we present an approximate analytical solution for solving one dimensional two phase Stefan problem. The finite sine transform technique is used to convert the non dimensional form from a space domain to a wave number domain. Inverse finite sine transform is used to obtain the desired solution. The location of moving interface during freezing process in a finite domain is studied and the result thus obtained are discussed graphically. The whole analysis is presented in a non dimensional form.