The isoperimetric problem on surfaces of revolution of decreasing Gauss curvature

We prove that the least-perimeter way to enclose prescribed area in the plane with smooth, rotationally symmetric, complete metric of nonincreasing Gauss curvature consists of one or two circles, bounding a disc, the complement of a disc, or an annulus. We also provide a new isoperimetric inequality in general surfaces with boundary.

     

Examples of max-flow and min-cut problems with duality gaps in continuous networks

Strang (Mathematical Programming 26, 1983) gave a method to establish a max-flow min-cut theorem in a domain of a Euclidean space. The method can be applied also to max-flow min-cut problems defined by Iri (Survey of Mathematical Programming, North-Holland, 1979) whenever the capacity functions of max-flow problems are bounded and continuous. This paper deals with max-flow min-cut problems of Strang and Iri with unbounded or noncontinuous capacity functions. It is proved that, in such problems, max-flow min-cut theorems may fail to hold.     

Partition identities and the coin exchange problem

The number of partitions of n into parts divisible by a or b equals the number of partitions of n in which each part and each difference of two parts is expressible as a non-negative integer combination of a and b. This generalizes identities of MacMahon and Andrews. The analogous identities for three or more integers (in place of a,b) hold in certain cases.     

The next step of the word problem over monoids

It is known that a group presentation P can be regarded as a 2-complex with a single 0-cell. Thus we can consider a 3-complex with a single 0-cell which is known as a 3-presentation. Similarly, we can also consider 3-presentations for monoids. In this paper, by using spherical monoid pictures, we show that there exists a finite 3-monoid-presentation which has unsolvable “generalized identity problem” that can be thought as the next step (or one-dimension higher) of the word problem for monoids. We note that the method used in this paper has chemical and physical applications.     

Local existence of energy class solutions for the dirac—klein—gordon equations

Abstract

We show a method to eliminate a type of mixed asymptotics in certain free boundary problems, and give two examples of its application. It appears that these problems cannot be handled by the monotonicity formula of Alt et al. [Alt, H. W., Caffarelli, L. A., Friedman, A. (1984). Variational problems with two phases and their free boundaries. Trans. Am. Math. Soc. 282(2):431–461] or by the more recent monotonicity formula of Caffarelli et al. [Caffarelli, L. A., Jerison, D., Kenig, C. E. (2002). Some new monotonicity theorems with applications to free boundary problems. Ann. Math. (2) 155(2):369–404].     

The Solution of a Free Boundary Problem Related to Environmental Management Systems

Abstract

Explicit solutions of free boundary problems are notoriously difficult to find. In this article, we consider two log-normal diffusions. One represents the level of pollution, or degradation, in some environmental area. The second models the social, political, or financial cost of the pollution. A single control parameter is considered that reduces the rate of pollution. The optimal time to implement the change in the parameter is found by explicitly solving a free boundary problem. The novelty is that the smooth pasting conditions, which are difficult to justify, are not used in the derivation.     

LSQR iterative common symmetric solutions to matrix equations AXB = E and CXD = F

A new matrix based iterative method is presented to compute common symmetric solution or common symmetric least-squares solution of the pair of matrix equations AXB = E and CXD = F. By this iterative method, for any initial matrix X₀, a solution X^∗ can be obtained within finite iteration steps if exact arithmetic was used, and the solution X^∗ with the minimum Frobenius norm can be obtained by choosing a special kind of initial matrix. In addition, the unique nearest common symmetric solution or common symmetric least-squares solution to given matrix in Frobenius norm can be obtained by first finding the minimum Frobenius norm common symmetric solution or common symmetric least-squares solution of the new pair of matrix equations. The given numerical examples show that the matrix based iterative method proposed in this paper has faster convergence than the iterative methods proposed in [1] and [2] to solve the same problems.     

On the principal eigenvalue of a Robin problem with a large parameter

We study the asymptotic behaviour of the principal eigenvalue of a Robin (or generalised Neumann) problem with a large parameter in the boundary condition for the Laplacian in a piecewise smooth domain. We show that the leading asymptotic term depends only on the singularities of the boundary of the domain, and give either explicit expressions or two‐sided estimates for this term in a variety of situations. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Optimization and optimality test for the Max-Cut Problem

We show that the following two problems are polynomially equivalent:

Boundary integral equations with the generalized Neumann kernel for Laplace’s equation in multiply connected regions

This paper presents a new boundary integral method for the solution of Laplace’s equation on both bounded and unbounded multiply connected regions, with either the Dirichlet boundary condition or the Neumann boundary condition. The method is based on two uniquely solvable Fredholm integral equations of the second kind with the generalized Neumann kernel. Numerical results are presented to illustrate the efficiency of the proposed method.     

On the Multiplicity Problem and the Isomorphism Problem for the Four Subspace Algebra

Let Λ be the four subspace algebra. We show that for any Λ-module M there exists an algorithm (up to the problem of finding roots of the so-called characteristic polynomial of M) with relatively low polynomial complexity of determining multiplicities of all direct summands of M. Moreover, we give a fully algorithmic criterion for deciding if two Λ-modules M and N are isomorphic.     

A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments

The linear ordering problem consists in finding a linear order at minimum remoteness from a weighted tournament T, the remoteness being the sum of the weights of the arcs that we must reverse in T to transform it into a linear order. This problem, also known as the search of a median order, or of a maximum acyclic subdigraph, or of a maximum consistent set, or of a minimum feedback arc set, is NP-hard; when all the weights of T are equal to 1, the linear ordering problem is the same as Slater's problem. In this paper, we describe the principles and the results of an exact method designed to solve the linear ordering problem for any weighted tournament. This method, of which the corresponding software is freely available at the URL address http://www.enst.fr/~charon/tournament/median.html, is based upon a branch-and-bound search with a Lagrangean relaxation as the evaluation function and a noising method for computing the initial bound. Other components are designed to reduce the BB-search-tree.     

Valuations and Busemann–Petty type problems

Projection and intersection bodies define continuous and GL(n) contravariant valuations. They played a critical role in the solution of the Shephard problem for projections of convex bodies and its dual version for sections, the Busemann–Petty problem. We consider the question whether ΦKΦL implies V(K)V(L), where Φ is a homogeneous, continuous operator on convex or star bodies which is an SO(n) equivariant valuation. Important previous results for projection and intersection bodies are extended to a large class of valuations.     

Eigenvalue Characterization and Computation for the Laplacian on General 2-D Domains

In this paper, we address the problem of determining and efficiently computing an approximation to the eigenvalues of the negative Laplacian ? ? on a general domain Ω ? ?² subject to homogeneous Dirichlet or Neumann boundary conditions. The basic idea is to look for eigenfunctions as the superposition of generalized eigenfunctions of the corresponding free space operator, in the spirit of the classical method of particular solutions (MPS). The main novelties of the proposed approach are the possibility of targeting each eigenvalue independently without the need for extensive scanning of the positive real axis and the use of small matrices. This is made possible by iterative inclusion of more basis functions in the expansions and a projection idea that transforms the minimization problem associated with MPS and its variants into a relatively simple zero-finding problem, even for expansions with very few basis functions.     

A simple Marquardt algorithm for the nonlinear least-squares problem

A new implementation of the Marquardt method for the nonlinear least-squares problem is presented. The algorithm is very simple but its performance with nine test functions is at least comparable with either Davidon-Fletcher-Powell's method or Moré's adaptive Marquardt method.     

Scheduling with few changes

In this work we consider scheduling problems where a sequence of assignments from products to machines – or from tasks to operators, or from workers to resources – has to be determined, with the goal of minimizing the costs (=money, manpower, and/or time) that are incurred by the interplay between those assignments. To account for the different practical requirements (e.g. few changes between different products/tasks on the same machine/operator, few production disruptions, or few changes of the same worker between different resources), we employ different objective functions that are all based on elementary combinatorial properties of the schedule matrix. We propose simple and efficient algorithms to solve the corresponding optimization problems, and provide hardness results where such algorithms most likely do not exist.     

On the existence of bubble-type solutions of nonlinear singular problems

Considered in this paper is a class of singular boundary value problem, arising in hydrodynamics and nonlinear field theory, when centrally bubble-type solutions are sought: \((p(t)u0)0 = c(t)p(t)f(u); u0(0) = 0; u(+1) = L > 0\) in the half-line \([0;+1)\), where \(p(0) = 0\). We are interested in strictly increasing solutions of this problem in \([0;1)\) having just one zero in \((0;+1) \)and finite limit at zero, which has great importance in applications or pure and applied mathematics. Su±cient conditions of the existence of such solutions are obtained by applying the critical point theory and by using shooting argument [9,10] to better analysis the properties of certain solutions associated with the singular di®erential equation. To the authors' knowledge, for the first time, the above problem is dealt with when f satis¯es non-Lipschitz condition. Recent results in the literature are generalized and signi¯cantly improved.     

On randomized algorithms for the majority problem

In the majority problem, we are given n balls coloured black or white and we are allowed to query whether two balls have the same colour or not. The goal is to find a ball of majority colour in the minimum number of queries. The answer is known to be n−B(n) where B(n) is the number of 1’s in the binary representation of n. In this paper we study randomized algorithms for determining majority, which are allowed to err with probability at most ε. We show that any such algorithm must have expected running time at least . Moreover, we provide a randomized algorithm which shows that this result is best possible. These extend a result of De Marco and Pelc [G. De Marco, A. Pelc, Randomized algorithms for determining the majority on graphs, Combin. Probab. Comput. 15 (2006) 823-834].