Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms

Properties of several dual characteristics of the multidimensional knapsack problem (such as the probability of existence of-optimal and optimal-feasible Lagrange function generalized saddle points, magnitude of relative duality gap, etc.) are investigated for different probabilistic models. Sufficient conditions of good asymptotic behavior of the dual characteristics are given. A fast statistically efficient approximate algorithm with linear running time complexity for problems with random coefficients is presented.This paper was written when the author was affiliated with Chelyabinsk State Technical University and the Moscow Physical and Technical Institute, Russia.     

Acoustic spectroscopy of fluid saturation effects in carbonate rock

The results of acoustic spectroscopy of a carbonate sedimentary rock in the case of saturation degree variations are given. The data on the elasticity and dissipation tensors within a two-octave range are obtained for one and the same sample using one and the same measurement technique. High accuracy of the measurements allowed distinguishing all three saturation stages, namely, condensation, meniscus creation, and pore filling with a fluid. The observed variations are in good agreement with the results of a standard granulometric analysis. The character of variations in the frequency dependence of attenuation coefficients make it possible to make reasonable assumption concerning the mechanisms responsible for acoustic energy absorption in porous materials.     

Observation of slow dynamics effects in nonconsolidated media under in situ conditions

Reactions of an unconsolidated medium to a strong impact action are considered. A character of medium relaxation was controlled based on changes in the phase velocity of a trial Rayleigh wave. The analysis of the R-wave dispersion and its dependence on the distance to the source allowed for estimating the dimensions of a space region where the impact action was revealed. Seismoacoustic measurements showed that the time dependence of the R-wave is logarithmic.     

Mass Transfer of the Liquid Phase in a Partially Saturated Porous Medium Under the Action of Low-Frequency Elastic Vibrations

We study the model of a partially saturated porous medium comprising a system of identical parallel cylindrical capillaries filled up with equal droplets. The basic features of the liquid-phase drift and the accompanying sound attenuation and droplet coalescence effects are analyzed in the case of external compression.     

A possible mechanism of the acoustic action on partially fluid-saturated porous media

The motion of a liquid drop under the action of acoustic vibration is studied for two limiting cases: the high-frequency case, when the effect of viscous forces can be ignored, and the low-frequency case, when the viscosity is significant. Equations describing the motion of a drop in an axially symmetric capillary with a varying cross section are derived by taking into account the hysteresis of the wetting angle. Numerical calculations are performed for cylindrical, conic, and corrugated capillaries.     

The uncapacitated facility location problem with demand-dependent setup and service costs and customer-choice allocation

We consider a generalization of the uncapacitated facility location problem, where the setup cost for a facility and the price charged for service may depend on the number of customers patronizing the facility. Customers are represented by the nodes of the transportation network, and facilities can be located only at nodes; a customer selects a facility to patronize so as to minimize his (her) expenses (price for service + the part of transportation costs paid by the customer). We assume that transportation costs are paid partially by the service company and partially by customers. The objective is to choose locations for facilities and balanced prices so as to either minimize the expenses of the service company (the sum of the total setup cost and the total part of transportation costs paid by the company), or to maximize the total profit. A polynomial-time dynamic programming algorithm for the problem on a tree network is developed.     

Diagnostics of the acoustic properties of unconsolidated media under natural conditions

Results of experimental studies carried out at the Bezvodnoe test area in 2005 and 2006 are presented. The goal of the studies is to investigate the potentialities of vibration diagnostics of the surface layers of soil under natural conditions. The most attention is given to the problem of measuring the shear modulus of soil and determining the power of seismic acoustic radiation with the help of an impedance method. The results obtained testify to the high sensitivity of the impedance method soil diagnostics and to the possibility of monitoring the variations of soil properties. Sources of nonlinear distortions and the problem of stability of radiation characteristics are also considered. A comparison with theoretical estimates is performed. It confirmed a special role of the contact region as the major source of radiation signal distortions. The results of the study are important for seismoacoustic investigation of the structure of natural media under natural conditions.     

Nonlinear acoustic spectroscopy of carbonate rocks

The paper presents the results of experimental research into the nonlinear acoustic properties of carbonate rocks depending on saturation. The linear acoustic properties of the same sample depending on saturation were presented earlier in Physical Acoustics. The previously obtained data point to the isotropy of the material, which makes it possible to restrict analysis to only two vibration modes. Responses for finite deformations were measured for the longitudinal and shear modes of an isotropic sample, which made it possible to analyze the nonlinear properties of macroscopic deformations with a change in volume and pure displacement. A heretofore unknown feature of the response was revealed for finite deformation values; it is related to the occurrence of a jumplike transition from classical nonlinearity to a hysteresis type of nonlinearity. As well, the deformation amplitude corresponding to the transition depends on fluid saturation. We studied the slow relaxation that occurs after long-term excitation of a sample with a deformation amplitude on the order of 10^?6. Data are presented on relaxation for deformation from pure displacement and deformation with a change in volume, which made it possible to isolate features related to the type of deformation and to compare the obtained data with the earlier published theoretical model. These data are compared with the results of other research groups.