DETERMINISTIC ALGORITHMS FOR MATCHING AND PACKING PROBLEMS BASED ON REPRESENTATIVE SETS

In this work, we study the well-known r-DIMENSIONAL k-MATCHING ((r, k)-DM), and r-SET k-PACKING ((r, k)-SP) problems. Given a universe U := U-1 ... U-r and an r-uniform family F subset of U-1 x ... x U-r, the (r, k)-DM problem asks if F admits a collection of k mutually disjoint sets. Given a universe U and an r-uniform family F subset of 2(U), the (r, k)-SP problem asks if F admits a collection of k mutually disjoint sets. We employ techniques based on dynamic programming and representative families. This leads to a deterministic algorithm with running time O(2.851((r-1)k) .vertical bar F vertical bar. n log(2)n . logW) for the weighted version of (r, k)-DM, where W is the maximum weight in the input, and a deterministic algorithm with running time O(2.851((r-0.5501)k).vertical bar F vertical bar.n log(2) n . logW) for the weighted version of (r, k)-SP. Thus, we significantly improve the previous best known deterministic running times for (r, k)-DM and (r, k)-SP and the previous best known running times for their weighted versions. We rely on structural properties of (r, k)-DM and (r, k)-SP to develop algorithms that are faster than those that can be obtained by a standard use of representative sets. Incorporating the principles of iterative expansion, we obtain a better algorithm for (3, k)-DM, running in time O(2.004(3k).vertical bar F vertical bar . n log(2)n). We believe that this algorithm demonstrates an interesting application of representative families in conjunction with more traditional techniques. Furthermore, we present kernels of size O(e(r)r(k-1)(r) logW) for the weighted versions of (r, k)-DM and (r, k)-SP, improving the previous best known kernels of size O(r!r(k-1)(r) logW) for these problems.

Kernelization complexity of possible winner and coalitional manipulation problems in voting

In the POSSIBLE WINNER problem in computational social choice theory, we are given a set of partial preferences and the question is whether a distinguished candidate could be made winner by extending the partial preferences to linear preferences. Previous work has provided, for many common voting rules, fixed parameter tractable algorithms for the POSSIBLE WINNER problem, with number of candidates as the parameter. However, the corresponding kernelization question is still open and in fact, has been mentioned as a key research challenge 10]. In this paper, we settle this open question for many common voting rules. We show that the POSSIBLE WINNER problem for maximin, Copeland, Bucklin, ranked pairs, and a class of scoring rules that includes the Borda voting rule does not admit a polynomial kernel with the number of candidates as the parameter. We show however that the COALITIONAL MANIPULATION problem which is an important special case of the POSSIBLE WINNER problem does admit a polynomial kernel for maximin, Copeland, ranked pairs, and a class of scoring rules that includes the Borda voting rule, when the number of manipulators is polynomial in the number of candidates. A significant conclusion of our work is that the POSSIBLE WINNER problem is harder than the COALITIONAL MANIPULATION problem since the COALITIONAL MANIPULATION problem admits a polynomial kernel whereas the POSSIBLE WINNER problem does not admit a polynomial kernel. (C) 2015 Elsevier B.V. All rights reserved.

Boundary knot method for 2D and 3D Helmholtz and convection-diffusion problems under complicated geometry

The boundary knot method (BKM) of very recent origin is an inherently meshless, integration-free, boundary-type, radial basis function collocation technique for the numerical discretization of general partial differential equation systems. Unlike the method of fundamental solutions, the use of non-singular general solution in the BKM avoids the unnecessary requirement of constructing a controversial artificial boundary outside the physical domain. The purpose of this paper is to extend the BKM to solve 2D Helmholtz and convection-diffusion problems under rather complicated irregular geometry. The method is also first applied to 3D problems. Numerical experiments validate that the BKM can produce highly accurate solutions using a relatively small number of knots. For inhomogeneous cases, some inner knots are found necessary to guarantee accuracy and stability. The stability and convergence of the BKM are numerically illustrated and the completeness issue is also discussed.

The relationship of SIF between plate and plane fracture problems and the effect of the plate thickness on SIF

In the present paper, it is shown that the zero series eigenfunctions of Reissner plate cracks/notches fracture problems are analogous to the eigenfunctions of anti-plane and in-plane. The singularity in the double series expression of plate problems only arises in zero series parts. In view of the relationship with eigen-values of anti-plane and in-plane problem, the solution of eigen-values for Reissner plates consists of two parts: anti-plane problem and in-plane problem. As a result the corresponding eigen-values or the corresponding eigen-value solving programs with respect to the anti-plane and in-plane problems can be employed and many aggressive SIF computed methods of plane problems can be employed in the plate. Based on those, the approximate relationship of SIFs between the plate and the plane fracture problems is figured out, and the effect relationship of the plate thickness on SIF is given.

3D simulation of the micro indentation process and relative problems research

In this paper the finite element method was used to simulate micro-scale indentation process. The several standard indenters were simulated with 3D finite element model. The emphasis of this paper was the differences between 2D axisymmetric cone model and

Interface crack problems with strain gradient effects

In this paper, the strain gradient theory proposed by Chen and Wang (2001 a, 2002b) is used to analyze an interface crack tip field at micron scales. Numerical results show that at a distance much larger than the dislocation spacing the classical continuum plasticity is applicable; but the stress level with the strain gradient effect is significantly higher than that in classical plasticity immediately ahead of the crack tip. The singularity of stresses in the strain gradient theory is higher than that in HRR field and it slightly exceeds or equals to the square root singularity and has no relation with the material hardening exponents. Several kinds of interface crack fields are calculated and compared. The interface crack tip field between an elastic-plastic material and a rigid substrate is different from that between two elastic-plastic solids. This study provides explanations for the crack growth in materials by decohesion at the atomic scale.

Crack problems of piezoelectric materials

This paper presents an analysis of crack problems in homogeneous piezoelectrics or on the interfaces between two dissimilar piezoelectric materials based on the continuity of normal electric displacement and electric potential across the crack faces. The explicit analytic solutions are obtained for a single crack in piezoelectrics or on the interfaces of piezoelectric bimaterials. A class of boundary problems involving many cracks is also solved. For homogeneous materials it is found that the normal electric displacement D-2 induced by the crack is constant along the crack faces which depends only on the applied remote stress field. Within the crack slit, the electric fields induced by the crack are also constant and not affected by the applied electric field. For the bimaterials with real H, the normal electric displacement D-2 is constant along the crack faces and electric field E-2 has the singularity ahead of the crack tip and a jump across the interface.

Closed form solutions of T-stress in plane elasticity crack problems

The T-stress is considered as an important parameter in linear elastic fracture mechanics. In this paper, several closed form solutions of T-stress in plane elasticity crack problems in an infinite plate are investigated using the complex potential theory. In the line crack case, if the applied loading is the remote stress or the concentrated forces, the T-stress can be derived from the basic field. Here, the basic field is defined as the field caused by the applied loading in the infinite plate without the crack. For the circular are crack, the T-stress can be abstracted from a known solution. For the cusp crack problems, the T-stress can be separated from the obtained stress solution for which the conformal mapping technique is used.

Some advances in study of crack identification problems

In the present paper, the crack identification problems are investigated. This kind of problems belong to the scope of inverse problems and are usually ill-posed on their solutions. The paper includes two parts: (1) Based on the dynamic BIEM and the optimization method and using the measured dynamic information on outer boundary, the identification of crack in a finite domain is investigated and a method for choosing the high sensitive frequency region is proposed successfully to improve the precision. (2) Based on 3-D static BIEM and hypersingular integral equation theory, the penny crack identification in a finite body is reduced to an optimization problem. The investigation gives us some initial understanding on the 3-D inverse problems.

Las Prophetiae Merlini de Geoffrey de Monmouth en los Baladros castellanos: estado de la cuestión

Resumen: La Historia regum Britanniae (circa 1139) del obispo galés Geoffrey de Monmouth, texto destacado en el corpus latino medieval a causa de sus proyecciones tanto historiográficas como ficcionales, tiene como objeto referir los actos de todos los monarcas célticos de la Gran Bretaña anteriores a la conquista germánica. En este propósito, sus capítulos 112 a 117 obran como una mise en abîme puesto que las Prophetiae Merlini que allí se leen, atribuidas al famoso mago pero inspiradas en la literatura apocalíptica vétero y neotestamentaria, reproducen proféticamente las grandes líneas de contenido de la propia crónica, e incluso anticipan la restauración definitiva de los celtas derrotados. Aunque Wace, Chrétien de Troyes y la tradición romancística francesa posterior, deudora de la Historia en muchos puntos, desecharon el texto a causa de su agudo hermetismo, el mismo sí se difundió por el continente y reapareció asombrosamente interpolado, en versión castellana, dentro de dos tardíos ejemplares del género caballeresco hispánico, el Baladro del sabio Merlín con sus profecías (Burgos, 1498) y la primera parte de la Demanda del santo Grial (Sevilla, 1535). La presente comunicación tiene como objetivos reseñar los actuales conocimientos de la crítica acerca de esta versión castellana de las Prophetiae y señalar los problemas aún pendientes de resolución; serán consideradas las contribuciones fundamentales relativas al original latino y, también, a las versiones francesas conservadas, dada la posibilidad de que nuestra traducción tenga una fuente gala

Parkes problems revisited - Application of response number

Response number R-n(n), proposed in [3, 4], is an important independent dimensionless number for the dynamic response of structures [2]. In this paper, the response number is applied to the dynamic plastic response of the well-known Parkes' problem, i.e., beams struck by concentrated mass.

Modeling, numerical methods, and simulation for particle-fluid two-phase flow problems

In this paper, we study the issues of modeling, numerical methods, and simulation with comparison to experimental data for the particle-fluid two-phase flow problem involving a solid-liquid mixed medium. The physical situation being considered is a pulsed liquid fluidized bed. The mathematical model is based on the assumption of one-dimensional flows, incompressible in both particle and fluid phases, equal particle diameters, and the wall friction force on both phases being ignored. The model consists of a set of coupled differential equations describing the conservation of mass and momentum in both phases with coupling and interaction between the two phases. We demonstrate conditions under which the system is either mathematically well posed or ill posed. We consider the general model with additional physical viscosities and/or additional virtual mass forces, both of which stabilize the system. Two numerical methods, one of them is first-order accurate and the other fifth-order accurate, are used to solve the models. A change of variable technique effectively handles the changing domain and boundary conditions. The numerical methods are demonstrated to be stable and convergent through careful numerical experiments. Simulation results for realistic pulsed liquid fluidized bed are provided and compared with experimental data. (C) 2004 Elsevier Ltd. All rights reserved.