The weighted Fermat-Torricelli problem for tetrahedra and an “inverse” problem

We study the weighted Fermat-Torricelli problem for tetrahedra in R³ and solve an “inverse” problem by introducing a method of differentiation. The solution of the inverse problem is the main result which states that: Given the Fermat-Torricelli point A₀ with the vertices lie on four prescribed rays, find the ratios between every pair of non-negative weights of two corresponding rays such that the sum of the four non-negative weights is a constant number. An application of the inverse weighted Fermat-Torricelli problem is the strong invariance principle of the weighted Fermat-Torricelli point which gives some classes of tetrahedra that could be named “evolutionary tetrahedra”.     

Finiteness of the set of solutions of Plateau's problem for polygonal boundary curves

It is proved that for a simple, closed, extreme polygon  Γ⊂R³$\Gamma \subset {\mathbb{R}}^3$ every immersed, stable minimal surface spanning Γ is an isolated point of the set of all minimal surfaces spanning Γ   w.r.t. the C⁰$C^0$-topology. Since the subset of immersed, stable minimal surfaces spanning Γ is shown to be closed in the compact set of all minimal surfaces spanning Γ, this proves in particular that Γ can bound only finitely many immersed, stable minimal surfaces.     

Conformal upper bounds for the eigenvalues of the Laplacian and Steklov problem

In this paper, we find upper bounds for the eigenvalues of the Laplacian in the conformal class of a compact Riemannian manifold (M,g). These upper bounds depend only on the dimension and a conformal invariant that we call “min-conformal volume”. Asymptotically, these bounds are consistent with the Weyl law and improve previous results by Korevaar and Yang and Yau. The proof relies on the construction of a suitable family of disjoint domains providing supports for a family of test functions. This method is interesting for itself and powerful. As a further application of the method we obtain an upper bound for the eigenvalues of the Steklov problem in a domain with C¹ boundary in a complete Riemannian manifold in terms of the isoperimetric ratio of the domain and the conformal invariant that we introduce.     

A solution of the affine quadratic inverse eigenvalue problem

The quadratic inverse eigenvalue problem (QIEP) is to find the three matrices M,C, and K, given a set of numbers, closed under complex conjugations, such that these numbers become the eigenvalues of the quadratic pencil P(λ)=λ²M+λC+K. The affine inverse quadratic eigenvalue problem (AQIEP) is the QIEP with an additional constraint that the coefficient matrices belong to an affine family, that is, these matrices are linear combinations of substructured matrices. An affine family of matrices very often arise in vibration engineering modeling and analysis. Research on QIEP and AQIEP are still at developing stage. In this paper, we propose three methods and the associated mathematical theories for solving AQIEP: A Newton method, an alternating projections method, and a hybrid method combining the two. Validity of these methods are illustrated with results on numerical experiments on a spring-mass problem and comparisons are made with these three methods amongst themselves and with another Newton method developed by Elhay and Ram (2002) [12]. The results of our experiments show that the hybrid method takes much smaller number of iterations and converges faster than any of these methods.     

Matrix inverse problem and its optimal approximation problem for R-skew symmetric matrices

Let R ∈ C^n×n be a nontrivial involution, i.e., R² = I and R ≠ ±I. A matrix A ∈ C^n×n is called R-skew symmetric if RAR = −A. The least-squares solutions of the matrix inverse problem for R-skew symmetric matrices with R∗ = R are firstly derived, then the solvability conditions and the solutions of the matrix inverse problem for R-skew symmetric matrices with R∗ = R are given. The solutions of the corresponding optimal approximation problem with R∗ = R for R-skew symmetric matrices are also derived. At last an algorithm for the optimal approximation problem is given. It can be seen that we extend our previous results [G.X. Huang, F. Yin, Matrix inverse problem and its optimal approximation problem for R-symmetric matrices, Appl. Math. Comput. 189 (2007) 482-489] and the results proposed by Zhou et al. [F.Z. Zhou, L. Zhang, X.Y. Hu, Least-square solutions for inverse problem of centrosymmetric matrices, Comput. Math. Appl. 45 (2003) 1581-1589].     

Global existence of classical solutions to the Cauchy problem on a semi-bounded initial axis for a nonhomogeneous quasilinear hyperbolic system

It is proven that if the leftmost eigenvalue is weakly linearly degenerate, then the Cauchy problem for a class of nonhomogeneous quasilinear hyperbolic systems with small and decaying initial data given on a semi-bounded axis admits a unique global C¹ solution on the domain , where x=xn(t) is the fastest forward characteristic emanating from the origin. As an application of our result, we prove the existence of global classical, C¹ solutions of the flow equations of a model class of fluids with viscosity induced by fading memory with small smooth initial data given on a semi-bounded axis.     

Estimates of initial conditions of parabolic equations and inequalities in infinite domains via lateral Cauchy data

A parabolic equation/inequality in an infinite domain is considered. The lateral Cauchy data are given at an arbitrary C²-smooth lateral surface. The inverse problem of the interest of this paper consists in an estimate of the unknown initial condition via these Cauchy data.     

The tricriterion shortest path problem with at least two bottleneck objective functions

The focus of this paper is on the tricriterion shortest path problem where two objective functions are of the bottleneck type, for example MinMax or MaxMin. The third objective function may be of the same kind or we may consider, for example, MinSum or MaxProd. Let p(n) be the complexity of a classical single objective algorithm responsible for this third function, where n is the number of nodes and m be the number of arcs of the graph. An O(m²p(n)) algorithm is presented that can generate the minimal complete set of Pareto-optimal solutions. Finding the maximal complete set is also possible. Optimality proofs are given and extensions for several special cases are presented. Computational experience for a set of randomly generated problems is reported.     

Polynomial cases of graph decomposition: A complete solution of Holyer’s problem

Let H be a fixed graph. A graph G has an H-decomposition if the edge set of G can be partitioned into subsets inducing graphs isomorphic to H. Let P_H denote the following decision problem: “Does an instance graph G admit H-decomposition?” In this paper we prove that the problem P_H is polynomial time solvable if H is a graph whose every component has at most 2 edges. This way we complete a solution of Holyer’s problem which is the problem of classifying the problems P_H according to their computational complexities.     

The two-dimensional Prouhet-Tarry-Escott problem

In this paper we generalize the Prouhet-Tarry-Escott problem (PTE) to any dimension. The one-dimensional PTE problem is the classical PTE problem. We concentrate on the two-dimensional version which asks, given parameters n,k∈N, for two different multi-sets {(x₁,y₁),…,(xn,yn)}, of points from Z² such that for all d,j∈{0,…,k} with j?d. We present parametric solutions for n∈{2,3,4,6} with optimal size, i.e., with k=n−1. We show that these solutions come from convex 2n-gons with all vertices in Z² such that every line parallel to a side contains an even number of vertices and prove that such convex 2n-gons do not exist for other values of n. Furthermore we show that solutions to the two-dimensional PTE problem yield solutions to the one-dimensional PTE problem. Finally, we address the PTE problem over the Gaussian integers.     

Solutions of the Cheeger problem via torsion functions

The Cheeger problem for a bounded domain Ω⊂RN, N>1 consists in minimizing the quotients |∂E|/|E| among all smooth subdomains E⊂Ω and the Cheeger constant h(Ω) is the minimum of these quotients. Let be the p-torsion function, that is, the solution of torsional creep problem −Δp?p=1 in Ω, ?p=0 on ∂Ω, where Δpu:=div(|∇u|^p−2∇u) is the p-Laplacian operator, p>1. The paper emphasizes the connection between these problems. We prove that . Moreover, we deduce the relation limp→¹⁺‖?p_‖L¹(Ω)?CNlimp→¹⁺‖?p_‖L^∞(Ω) where CN is a constant depending only of N and h(Ω), explicitely given in the paper. An eigenfunction u∈BV(Ω)∩L^∞(Ω) of the Dirichlet 1-Laplacian is obtained as the strong L¹ limit, as p→¹⁺, of a subsequence of the family {?p/‖?p_‖L¹(Ω)}_p>1. Almost all t-level sets Et of u are Cheeger sets and our estimates of u on the Cheeger set |E₀| yield |B₁|hN(B₁)?|E₀|hN(Ω), where B₁ is the unit ball in RN. For Ω convex we obtain u=|E₀|⁻¹χE₀.     

An equivalence to the Gleason problem

In this article we study the Gleason problem locally. A new method for solving the Gleason A problem is presented. This is done by showing an equivalent statement to the Gleason A problem. In order to prove this statement, necessary and a sufficient conditions for a bounded domain to have the Gleason A property are found. Also an example of a bounded but not smoothly-bounded domain in Cn is given, which satisfies the sufficient condition at the origin, and hence has the Gleason A property there.     

The Hamiltonian problem on distance-hereditary graphs

In this paper, we first present an O(n+m)-time sequential algorithm to solve the Hamiltonian problem on a distance-hereditary graph G, where n and m are the number of vertices and edges of G, respectively. This algorithm is faster than the previous best known algorithm for the problem which takes O(n²) time. We also give an efficient parallel implementation of our sequential algorithm. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(logn) time using O((n+m)/logn) processors on an EREW PRAM.     

On Poincaré's isoperimetric problem for simple closed geodesics

We show in the context of integral currents that Poincaré's isoperimetric variational problem for simple closed geodesics on ovaloids has a smooth extremal C without self-intersection. Provided the smooth Riemannian metric on the ovaloid M in question does not deviate too far from constant curvature, we further show that (i) this extremal C is connected and so is the desired non-trivial geodesic of shortest length on M and (ii) C is close (in the sense of Hausdorff distance) to a great circle.     

The 1-median and 1-highway problem

In this paper we study a facility location problem in the plane in which a single point (median) and a rapid transit line (highway) are simultaneously located in order to minimize the total travel time of the clients to the facility, using the L₁ or Manhattan metric. The highway is an alternative transportation system that can be used by the clients to reduce their travel time to the facility. We represent the highway by a line segment with fixed length and arbitrary orientation. This problem was introduced in [Computers & Operations Research 38(2) (2011) 525–538]. They gave both a characterization of the optimal solutions and an algorithm running in O(n³logn) time, where n represents the number of clients. In this paper we show that the previous characterization does not work in general. Moreover, we provide a complete characterization of the solutions and give an algorithm solving the problem in O(n³) time.     

Classical verigin problem as a limit case of verigin problem with surface tension at free boundary

In this psper we consider Verigin problem with surface tension st free     

The minimum speed for a blocking problem on the half plane

We consider a blocking problem: fire propagates on a half plane with unit speed in all directions. To block it, a barrier can be constructed in real time, at speed σ. We prove that the fire can be entirely blocked by the wall, in finite time, if and only if σ>1. The proof relies on a geometric lemma of independent interest. Namely, let K⊂R² be a compact, simply connected set with smooth boundary. We define dK(x,y) as the minimum length among all paths connecting x with y and remaining inside K. Then dK attains its maximum at a pair of points both on the boundary of K.     

An adaptive <Emphasis Type="Italic">C</Emphasis><Superscript>0</Superscript>IPG method for the Helmholtz transmission eigenvalue problem

The interior penalty methods using C⁰ Lagrange elements (C⁰IPG) developed in the recent decade for the fourth order problems are an interesting topic in academia at present. In this paper, we discuss the adaptive fashion of C⁰IPG method for the Helmholtz transmission eigenvalue problem. We give the a posteriori error indicators for primal and dual eigenfunctions, and prove their reliability and efficiency. We also give the a posteriori error indicator for eigenvalues and design a C⁰IPG adaptive algorithm. Numerical experiments show that this algorithm is efficient and can get the optimal convergence rate.     

A new algorithm for minimizing makespan, <Emphasis Type="Italic">C</Emphasis><Subscript>max</Subscript>, in blocking flow-shop problem through slowing down the operations

In this paper, a new algorithm with complexity O(nm²) is presented, which finds the optimal makespan, C_max, for a blocking flow-shop problem by slowing down the operations of a no-wait flow-shop problem, F _m ∣no-wait∣C_max, for a given sequence where restriction on the slowing down is committed. However, the problem with performance measure makespan, C_max, in a non-cyclic environment, is a special case of cyclic problem with cycle time, C _t , as its performance measure. This new algorithm is much faster than the previously developed algorithms for cyclical scheduling problems.