Optimal Control in Heterogeneous Domain Decomposition Methods for Advection-Diffusion Equations

New domain decomposition methods (DDM) based on optimal control approach are introduced for the coupling of first and second order equations on overlapping subdomains. Several cost functionals and control functions are proposed. Uniqueness and existence results are proved for the coupled problem, and the convergence of iterative processes is analyzed. The work was supported by the Russian Foundation for Basic Research (04-01-00615) and it was partly carried out while the first author was visiting the IACS at EPFL.     

Long-time dynamics of von Karman semi-flows with non-linear boundary/interior damping

We study von Karman evolution equations with non-linear dissipation and with partially clamped and partially free boundary conditions. Two distinctive mechanisms of dissipation are considered: (i) internal dissipation generated by non-linear operator, and (ii) boundary dissipation generated by shear forces friction acting on a free part of the boundary. The main emphasis is given to the effects of boundary dissipation. Under suitable hypotheses we prove existence of a compact global attractor and finiteness of its fractal dimension. We also show that any solution is stabilized to an equilibrium and estimate the rate of the convergence which, in turn, depends on the behaviour at the origin of the functions describing the dissipation.     

Resolvability properties via independent families

The authors give a consistent affirmative response to a question of Juhász, Soukup and Szentmiklóssy: If GCH fails, there are (many) extraresolvable, not maximally resolvable Tychonoff spaces. They show also in ZFC that for ω<λ?κ, no maximal λ-independent family of λ-partitions of κ is ω-resolvable. In topological language, that theorem translates to this: A dense, ω-resolvable subset of a space of the form (DI(λ)) is λ-resolvable.     

On Gittins’ index theorem in continuous time

We give a new and comparably short proof of Gittins’ index theorem for dynamic allocation problems of the multi-armed bandit type in continuous time under minimal assumptions. This proof gives a complete characterization of optimal allocation strategies as those policies which follow the current leader among the Gittins indices while ensuring that a Gittins index is at an all-time low whenever the associated project is not worked on exclusively. The main tool is a representation property of Gittins index processes which allows us to show that these processes can be chosen to be pathwise lower semi-continuous from the right and quasi-lower semi-continuous from the left. Both regularity properties turn out to be crucial for our characterization and the construction of optimal allocation policies.     

The problem of Dirichlet for anisotropic quasilinear degenerate elliptic equations

We consider the Dirichlet problem for a class of anisotropic degenerate elliptic equations. New a priori estimates for solutions and for the gradient of solutions are established. Based on these estimates sufficient conditions guaranteeing the solvability of the problem are formulated. The results are new even in the semilinear case when the principal part is the Laplace operator.     

无K1,r图中的哈密顿圈（英文）

本文借助对图的本质独立集和图的部分平方图的独立集的研究，对于K1,r图中哈密顿圈的存在性给出了八个充分条件。我们将利用T－插点技术对这八个充分条件给出统一的证明，本文的结果从本质上改进了C－Q.Zhang于1988年利用次形条件给出的k-连通无爪图是哈密顿图的次型充分条件，同时。G.Chen和R.H.Schelp在1995年利用次型条件给出的关于k-连通无K1，4图是哈密顿图的充分条件也被我们的结果改进并推广到无K1,r图。     

On the maximum cardinality search lower bound for treewidth

The Maximum Cardinality Search (MCS) algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbours becomes visited. A maximum cardinality search ordering (MCS-ordering) of a graph is an ordering of the vertices that can be generated by the MCS algorithm. The visited degree of a vertex v in an MCS-ordering is the number of neighbours of v that are before v in the ordering. The visited degree of an MCS-ordering ψ of G is the maximum visited degree over all vertices v in ψ. The maximum visited degree over all MCS-orderings of graph G is called its maximum visited degree. Lucena [A new lower bound for tree-width using maximum cardinality search, SIAM J. Discrete Math. 16 (2003) 345-353] showed that the treewidth of a graph G is at least its maximum visited degree.We show that the maximum visited degree is of size O(logn) for planar graphs, and give examples of planar graphs G with maximum visited degree k with O(k!) vertices, for all k∈N. Given a graph G, it is NP-complete to determine if its maximum visited degree is at least k, for any fixed k?7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete.In this paper, we also propose some heuristics for the problem, and report on an experimental analysis of them. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.     

Large Discrepancy In Homogenous Quasi-Arithmetic Progressions

We prove that the class of homogeneous quasi-arithmetic progressions has unbounded discrepancy. That is, we show that given any 2-coloring of the natural numbers and any positive integer D, one can find a real number α≥1 and a set of natural numbers of the form {0, [α], [2α], [3α], . . . , [kα]} so that one color appears at least D times more than the other color. This was already proved by Beck in 1983, but the proof given here is somewhat simpler and gives a better bound on the discrepancy.     

Euler configurations and quasi-polynomial systems

Consider the problem of three point vortices (also called Helmholtz’ vortices) on a plane, with arbitrarily given vorticities. The interaction between vortices is proportional to 1/r, where r is the distance between two vortices. The problem has 2 equilateral and at most 3 collinear normalized relative equilibria. This 3 is the optimal upper bound. Our main result is that the above standard statements remain unchanged if we consider an interaction proportional to r ^b, for any b < 0. For 0 < b < 1, the optimal upper bound becomes 5. For positive vorticities and any b < 1, there are exactly 3 collinear normalized relative equilibria. The case b = −2 of this last statement is the well-known theorem due to Euler: in the Newtonian 3-body problem, for any choice of the 3 masses, there are 3 Euler configurations (also known as the 3 Euler points). These small upper bounds strengthen the belief of Kushnirenko and Khovanskii [18]: real varieties defined by simple systems should have a simple topology. We indicate some hard conjectures about the configurations of relative equilibrium and suggest they could be attacked within the quasi-polynomial framework.     

Positive solutions and eigenvalue regions of two-delay singular systems with a twin parameter

The paper is concerned with a two-delay singular differential system with a twin parameter. Applying fixed-point index theory, we show the relationship between the asymptotic behaviors of nonlinearities (at zero and infinity) and the open regions (eigenvalue regions) of parameters, which are correlated with delays, such that the system has zero, one and two positive solution(s).