Complexity of the min-max and min-max regret assignment problems

This paper investigates the complexity of the min-max and min-max regret assignment problems both in the discrete scenario and interval data cases. We show that these problems are strongly NP-hard for an unbounded number of scenarios. We also show that the interval data min-max regret assignment problem is strongly NP-hard.     

Approximation results for a min-max location-routing problem

This paper studies a min-max location-routing problem, which aims to determine both the home depots and the tours for a set of vehicles to service all the customers in a given weighted graph, so that the maximum working time of the vehicles is minimized. The min-max objective is motivated by the needs of balancing or fairness in vehicle routing applications. We have proved that unless NP=P, it is impossible for the problem to have an approximation algorithm that achieves an approximation ratio of less than 4/3. Thus, we have developed the first constant ratio approximation algorithm for the problem. Moreover, we have developed new approximation algorithms for several variants, which improve the existing best approximation ratios in the previous literature.     

Approximation hardness of min-max tree covers

We prove the first inapproximability bounds to study approximation hardness for a min-max k-tree cover problem and its variants. The problem is to find a set of k trees to cover vertices of a given graph with metric edge weights, so as to minimize the maximum total edge weight of any of the k trees. Our technique can also be applied to improve inapproximability bounds for min-max problems that use other covering objectives, such as stars, paths, and tours.     

The duality theorem for min-max functions

The set of min-max functions F : ℝⁿ → ℝⁿ is the least set containing coordinate substitutions and translations and closed under pointwise max, min, and function composition. The Duality Conjecture asserts that the trajectories of a min-max function, considered as a dynamical system, have a linear growth rate (cycle time) and shows how this can be calculated through a representation of F as an infimum of max-plus linear functions. We prove the conjecture using an analogue of Howard's policy improvement scheme, carried out in a lattice ordered group of germs of affine functions at infinity. The methods yield an efficient algorithm for computing cycle times.     

A min-max theorem for complex symmetric matrices

We optimize the form Re x^tTx to obtain the singular values of a complex symmetric matrix T. We prove that for ,

     

A min-max theorem for plane bipartite graphs

We consider a partitioning problem, defined for bipartite and 2-connected plane graphs, where each node should be covered exactly once by either an edge or by a cycle surrounding a face. The objective is to maximize the number of face boundaries in the partition. This problem arises in mathematical chemistry in the computation of the Clar number of hexagonal systems. In this paper we establish that a certain minimum weight covering problem of faces by cuts is a strong dual of the partitioning problem. Our proof relies on network flow and linear programming duality arguments, and settles a conjecture formulated by Hansen and Zheng in the context of hexagonal systems [P. Hansen, M. Zheng, Upper Bounds for the Clar Number of Benzenoid Hydrocarbons, Journal of the Chemical Society, Faraday Transactions 88 (1992) 1621-1625].     

On a Lagrangian Formulation of the Incompressible Euler Equation

In this paper we show that the incompressible Euler equation on the Sobolev space $H^s(\mathbb{R}^n), s › n ⁄ 2+1$, can be expressed in Lagrangian coordinates as a geodesic equation on an infinite dimensional manifold. Moreover the Christoffel map describing the geodesic equation is real analytic. The dynamics in Lagrangian coordinates is described on the group of volume preserving diffeomorphisms, which is an analytic submanifold of the whole diffeomorphism group. Furthermore it is shown that a Sobolev class vector field integrates to a curve on the diffeomorphism group.     

On a Liouville-type theorem and the Fujita blow-up phenomenon

The main purpose of this paper is to obtain the well-known results of H.Fujita and K.Hayakawa on the nonexistence of nontrivial nonnegative global solutions for the Cauchy problem for the equation

with on the half-space as a consequence of a new Liouville theorem of elliptic type for solutions of () on . This new result is in turn a consequence of other new phenomena established for nonlinear evolution problems. In particular, we prove that the inequality

has no nontrivial solutions on when We also show that the inequality

has no nontrivial nonnegative solutions for , and it has no solutions on bounded below by a positive constant for 1.$">

     

Farkas' theorem of nonconvex type and its application to a min-max problem

This note is concerned with the generalization of Farkas' theorem and its application to derive optimality conditions for a mix-max problem. Farkas' theorem is generalized to a system of inequalities described by sup-min type positively homogeneous functions. This generalization allows us to deal with optimization problems consisting of objective and constraint functions whose directional derivatives are not necessarily convex with respect to the directions. As an example of such problems, we formulate a min-max problem and derive its optimality conditions.The author would like to express his sincere thanks to Professors S. Suzuki and T. Asano of Sophia University and Professor K. Shimizu of Keio University for encouragement and suggestions.     

Multidimensional local central limit theorem of some non-uniformly hyperbolic systems

We consider Young＇s nonuniformly hyperbolic system （X, T, u） where u is the SRB measure corresponding to the system （X, T）, and show that if the components of a Holder observable f ： X → R^d are cohomologously independent, then f satisfies the multidimensional central limit theorem. Moreover if f is aperiodic, then f satisfies the local multidimensional central limit theorem.     

A generalization of the Fujisawa-Kuh global inversion theorem

We discuss the problem of global invertibility of nonlinear maps defined on the finite dimensional Euclidean space via differential tests. We provide a generalization of the Fujisawa-Kuh global inversion theorem and introduce a generalized ratio condition which detects when the pre-image of a certain class of linear manifolds is non-empty and connected. In particular, we provide conditions that also detect global injectivity.     

On a singular differential system arising from a min-max control problem

The feedback law for a control problem with a nondifferentiable cost functional is characterized by an initial-value problem for a differential system with singular right-hand side. This system is characteristic for a partial differential equation formally satisfied by the feedback law. A regularization of the differential system and the partial differential equation is given, and the feedback laws for the smoothed problems are shown to converge to the original feedback law.This work was supported by the Gruppo Nazionale per l'Analisi Funzionale e le sue Applicazioni of the Consiglio Nazionale delle Ricerche.     

Global inversion theorem to unique solvability of Dirichlet problems

Banach-Mazur-Caccioppoli global inversion theorem is applied to obtain a generalization of a result due to Ambrosetti and Prodi concerning unique solvability of a Dirichlet problem for a second-order differential equation.     

On a density theorem

Translated from Matematichskie Zametki, Vol. 51, No. 6, pp. 32–40, June, 1992.     

On a Kleinecke-Shirokov theorem

Czechoslovak Mathematical Journal - We prove that for normal operators N1, $${N_2} \in {\cal L}({\cal H})$$ , the generalized commutator [N1, N2; X] approaches zero when [N1, N2; [N1, N2; X]] tends...