Planarity and duality of finite and infinite graphs

We present a short proof of the following theorems simultaneously: Kuratowski's theorem, Fary's theorem, and the theorem of Tutte that every 3-connected planar graph has a convex representation. We stress the importance of Kuratowski's theorem by showing how it implies a result of Tutte on planar representations with prescribed vertices on the same facial cycle as well as the planarity criteria of Whitney, MacLane, Tutte, and Fournier (in the case of Whitney's theorem and MacLane's theorem this has already been done by Tutte). In connection with Tutte's planarity criterion in terms of non-separating cycles we give a short proof of the result of Tutte that the induced non-separating cycles in a 3-connected graph generate the cycle space. We consider each of the above-mentioned planarity criteria for infinite graphs. Specifically, we prove that Tutte's condition in terms of overlap graphs is equivalent to Kuratowski's condition, we characterize completely the infinite graphs satisfying MacLane's condition and we prove that the 3-connected locally finite ones have convex representations. We investigate when an infinite graph has a dual graph and we settle this problem completely in the locally finite case. We show by examples that Tutte's criterion involving non-separating cycles has no immediate extension to infinite graphs, but we present some analogues of that criterion for special classes of infinite graphs.     

An algorithm for the quadratic assignment problem using Bender's decomposition

A well known method used for solving quadratic assignment problems proceeds by the construction of an equivalent much larger linear assignment problem with many side constraints. The disadvantage of this method lies in the weakness of the bounds obtained by solving the linear problem. An alternate linearization has been suggested using a general method of Glover. In this paper the mixed integer program obtained by Glover's method is discussed and a solution using Bender's decomposition is proposed.     

Optimal and canonical solutions of the change making problem

Given a set of different coin-types, the change-making problem consists in assembling a changes c so as to minimize the number of coins utilized; this problem can arise in practice in some classes of uni-dimensional cargo-loading and cutting-stock problems. The paper presents a depth-first branch and bound algorithm, which makes use of a new dominance criterion; the superiority of this algorithm over Chang-Gill's and Wright's is shown through extensive computational comparisons. Moreover the performance and the applicability of a heuristic algorithm are analyzed.     

Iterative algorithms for large partitioned linear systems,with applications to image reconstruction

We present a unifying framework for a wide class of iterative methods in numerical linear algebra. In particular, the class of algorithms contains Kaczmarz's and Richardson's methods for the regularized weighted least squares problem with weighted norm. The convergence theory for this class of algorithms yields as corollaries the usual convergence conditions for Kaczmarz's and Richardson's methods. The algorithms in the class may be characterized as being group-iterative, and incorporate relaxation matrices, as opposed to a single relaxation parameter. We show that some well-known iterative methods of image reconstruction fall into the class of algorithms under consideration, and are thus covered by the convergence theory. We also describe a novel application to truly three-dimensional image reconstruction.     

Mersenne's solution for Galileo's problem of the rotating earth

More than twenty years before Huygens and Newton developed formulas for centrifugal acceleration, Mersenne contrived a statisfactory solution for Galileo's problem of the extrusion of bodies from the earth as a result of its daily rotation. Mersenne was able to overcome an error in Galileo's approach without the use either of an explicit notion of infinitesimals or of any clear concept of force. His solution depends on comparing the lengths of two lines, a technique that several historians have claimed to be inadequate for this problem.     

Arrow's theorem is not a surprising result

Arrow's theorem asserts that it is impossible to find a procedure which aggregates n given complete preorders into one complete preorder and which has ‘rational’ properties.Some authors have proposed to solve this problem in building what could be called ‘preaggregation methods’. The purpose of this paper is to study the Arrow's problematic in this context.The obtained results lead to an interpretation of Arrow's theorem which shows that it is rather natural, although many authors present it as a surprising result or even as a paradox.The last section compares the structures of the sets of decisive sets associated to aggregation and preaggregation procedures.     

On the optimization of constrained functions: comparison of sequential gradient-restoration algorithm and gradient-projection algorithm

The problem of minimizing a function fnof(x) subject to the nonlinear constraint ?(x) = 0 is considered, where fnof is a scalar, x is an n-vector, and ? is a q-vector, with q < n. The sequential gradient-restoration algorithm (SGRA: Miele, [1, 2]) and the gradient-projection algorithm (GPA: Rosen, [3, 4]) are considered. These algorithms have one common characteristic: they are all composed of the alternate succession of gradient phases and restoration phases. However, they are different in several aspects, namely, (a) problem formulation, (b) structure of the gradient phase, and (c) structure of the restoration phase. First, a critical summary of SGRA and GPA is presented. Then, a comparison is undertaken by considering the speed of convergence and, above all, robustness (that is, the capacity of an algorithm to converge to a solution). The comparison is done through 16 numerical examples. In order to understand the separate effects of characteristics (a), (b), (c), six new experimental algorithms are generated by combining parts of Miele's algorithm with parts of Rosen's algorithm. Thus, the total number of algorithms investigated is eight. The numerical results show that Miele's method is on the average faster than Rosen's method. More importantly, regarding robustness, Miele's method compares favorably with Rosen's method. Through the examples, it is shown that Miele's advantage in robustness is more prominent as the curvature of the constraint increases. While this advantage is due to the combined effect of characteristics (a), (b), (c), it is characteristic (c) that plays the dominant role. Indeed, Miele's restoration provides a better search direction as well as better step-size control than Rosen's restoration.     

Properly efficient and efficient solutions for vector maximization problems in euclidean space

Recently Benson proposed a definition for extending Geoffrion's concept of proper efficiency to the vector maximization problem in which the domination cone K is any nontrivial, closed convex cone. We give an equivalent definition of his notion of proper efficiency. Our definition, by means of perturbation of the cone K, seems to offer another justification of Benson's choice above Borwein's extension of Geoffrion's concept. Our result enables one to prove some other theorems concerning properly efficient and efficient points. Among these is a connectedness result.     

A remark on Hilbert's matrix

We exhibit a Jacobi matrix T which has simple spectrum and integer entries, and 0 commutes with Hilbert's matrix. As an application we replace the computation of the eigenvectors of Hilbert's matrix (a very ill-conditioned problem) by the computation of the eigenvectors of T (a nicely stable numerical problem).     

On the limiting behavior of Burger's equation

The limiting behavior as the viscosity goes to zero of the solution of the first boundary value problem for Burger's equation is considered. The method consists in identifying the solution of Burger's equation with the optimal control of an appropriate stochastic control problem.     

A maximum principle for nonsmooth optimal-control problems with state constraints

Optimality conditions are derived in the form of a maximum principle governing solutions to an optimal control problem which involves state constraints. The conditions, which apply in the absence of differentiability assumptions on the data, are stated in terms of Clarke's generalized Jacobians. Although not the most general available, the conditions are derived by a novel method: this involves removal of the state constraints by introduction of a penalty term and application of Ekeland's variational principle.     

Exponential asymptotics and adiabatic invariance of a simple oscillator

An alternative proof is provided for Littlewood's asymptotic expression arising from Lorentz's problem (1911) on the adiabatic invariance of a simple pendulum. Our approach is based on a standard WKB approximation. Our proof is simpler than those of both Littlewood (1963) and Wasow (1973). If the coefficient function in their differential equation is analytic, then Littlewood's asymptotic expression can even be replaced by an exponentially small term. To cite this article: C.H. Ou, R. Wong, C. R. Acad. Sci. Paris, Ser. I 343 (2006).     

Interactive multiobjective complex search

An interactive procedure based on Box's complex search is used to solve the vector maximization problem. This method has the advantage that the decision maker's underlying value function need not be explicitly specified. Also, the problem may have nonlinear objective functions and nonlinear constraints. Several example problems are presented.     

Singular integrals and a problem on mixing flows

We prove a result related to Bressan's mixing problem. We establish an inequality for the change of Bianchini semi-norms of characteristic functions under the flow generated by a divergence free time dependent vector field. The approach leads to a bilinear singular integral operator for which we prove bounds on Hardy spaces. We include additional observations about the approach and a discrete toy version of Bressan's problem.     

A variant of Nitsche's method

We present a method that aims to reconcile Nitsche's method with the traditional finite element method ('weak' versus 'strong implementation' of essential boundary conditions). We retain the original idea of a variational formulation based on an extended energy, but replace the original boundary terms by domain terms involving weak derivatives. The solution of the proposed method coincides, for the Poisson problem, with the one of the traditional method, which in particular shows monotonicity under the standard angle condition for the Courant element. For more general second-order problems, it allows for the weighting of boundary terms inherent to Nitsche's method. This is of particular interest for singularly perturbed problems.     

On the optimal level of a small country's strategic petroleum reserve

Decisions relating to a country's strategic petroleum reserve must take into account the level of risk inherent in its petroleum imports, the cost resulting from any shortfall in the import level, the cost of storage, and finally the effects of stockpiling transactions on the sensitive spot oil markets. Of course, small countries need not take into account their effect on the global market, a fact that drastically simplifies their decision problem. We present such a simple decision model for a small country's petroleum reserve which in addition to the above factors take into account the uncertainty of the country's refining capacity. A complete analytical treatment is feasible for this model, and a specific numerical example is presented for the case of Greece.     

On the Routh-Hurwitz-Fujiwara and the Schur-Cohn-Fujiwara theorems for the root-separation problem

In this paper, we give simple and elementary proofs of the two classical results of Fujiwara on the solution of the well-known Routh-Hurwitz and Schur-Cohn problems. We show that the Fujiwara matrix in each case satisfies a Lyapunov-type equation and then obtain Fujiwara's results by applying to this matrix equation some recent results on the inertia of matrices. These alternative proofs of Fujiwara's results thus establish a link between two apparently different approaches to the solution of the root-separation problem: the classical method of solution via quadratic forms, and the solution via matrix equations.     

Application of operations research in Israel's water sector

Israel's water sector has moved from a period of development, which ended in the mid-1960's, to an era of scarcity. Over 95% of the natural water potential is already being utilized, and there is severe competition for this scarce resource between economic sectors and geographic regions. Management of development, design and operation of the water systems is therefore an acute problem, with implications ranging from national policy to efficiency in daily operation. Operations research methodologies have been developed and applied quite extensively over the last 15 years in Israel's water sector, dealing with the full range of its problems. The paper is a survey of these applications, aimed at providing a realistic assessment of their value, from which water resources systems analysts in other countries may derive some guidelines for their own work.     

Simulating hospital emergency departments queuing systems: (GI/G/m(t)) : (IHFF/N/∞)

The queuing system to be considered in this paper is a real case study with the following characteristics: (1) general independent interarrival distribution, (2) general service-time distribution, (3) limited waiting room, (4) patient's priorities increase up to a certain number, (5) time-dependent number of servers (doctors), (6) infinite patient population, (7) each server meets the system only once within a certain period of time, while the total number of the available servers is known. The system to be considered is a hospital's Emergency Department and a general simulation algorithm is presented as well as the system's operating characteristics. This algorithm, implemented on a mini-computer or an inexpensive microcomputer solved a sophisticated operations research problem.