Degeneracy graphs: theory and application an updated survey

A survey of various aspects of the theory and application of degeneracy graphs (DGs for short) is given. The notion and some basic properties of DGs are introduced, cycling of the simplex method is discussed, the neighborhood problem is tackled, and the application of the so-called optimum DGs to particular problems which are connected with optimal degenerate solutions of a linear programming problem is presented. The impact of weakly redundant constraints on various postoptimal analyses under degeneracy is briefly described.     

The Tricomi and Frankl problems for generalized Chaplygin equations in multiply connected domains

The present paper deals with Tricomi and Frankl problems for generalized Chaplygin equations in multiply connected domains. We first give the representation of solutions of the Tricomi problem for the equations, and then prove the uniqueness and existence of solutions for the problem by a new method, i.e. the complex functions in the elliptic domain and the hyperbolic complex functions in hyperbolic domain are used. Finally we discuss the Frankl problem for generalized Chaplygin equations in multiply connected domains.     

Combinatorial analysis (matrix problems,order theory)

The survey is devoted to certain current problems in general combinatorial mathematics. The contemporary state-of-the-art of the theory of permanents, questions on the existence and the enumeration of matrices with nonnegative elements, and a number of problems connected with latin rectangles (enumeration, problem of completing a latin square, equidistant arrays) are examined. The main directions in combinatorial theory in connection with selection problems also are analyzed: matroid theory, transversals, extremal problems (coverings, depth of a matrix, Sperner families). Principal attention is paid to the papers reviewed in Referativnyi Zhurnal “Matematika” during 1975–1979.     

Nonlinear Riemann - Hilbert Problems without Transversality

Nonlinear Riemann - Hilbert problems (RHP) generalize two fundamental classical problems for complex analytic functions, namely: 1. the conformal mapping problem, and 2. the linear Riemann - Hilbert problem. This paper presents new results on global existence for the nonlinear (RHP) in doubly connected domains with nonclosed restriction curves for the boundary data. More precisely, our nonlinear (RHP) is required to become ?at infinity”?, i.e., for solutions having large moduli, a linear (RHP) with variable coefficients. Global existence for q-connected domains was already obtained in [9] for the special case that the restriction curves for the boundary data ?at infinity”? coincide with straight lines corresponding to linear (RHP)-s with special so-called constant - coefficient transversality boundary conditions. In this paper, the boundary conditions are much more general including highly nonlinear conditions for bounded solutions in the context of nontransversality. In order to prove global existence, we reduce the problem to nonlinear singular integral equations which can be treated by a degree theory of Fredholm - quasiruled mappings specifically constructed for mappings defined by nonlinar pseudodifferential operators.     

Balayage and Convergence of Rational Interpolants

We investigate the following problem: For which open simply connected domains do there exist interpolation schemes (a set of interpolation points) such that for any analytic function defined in the domain the corresponding interpolating polynomials converge to the function when the degree of the polynomials tends to infinity? We also study similar problems for rational interpolants. These problems are connected to the balayage (sweeping out) problems of measures.     

A Domain Embedding Method Using the Optimal Distributed Control and a Fast Algorithm

We propose a domain embedding method to solve second order elliptic problems in arbitrary two-dimensional domains. The method is based on formulating the problem as an optimal distributed control problem inside a disc in which the arbitrary domain is embedded. The optimal distributed control problem inside the disc is solved rapidly using a fast algorithm developed by Daripa et al. [3,7,10–12]. The arbitrary domains can be simply or multiply connected and the proposed method can be applied, in principle, to a large number of elliptic problems. Numerical results obtained for Dirichlet problems associated with the Poisson equation in simply and multiply connected domains are presented. The computed solutions are found to be in good agreement with the exact solutions with moderate number of grid points in the domain.     

The Generic Stability and Existence of Essentially Connected Components of Solutions for Nonlinear Complementarity Problems

The aim of this paper is to develop the general generic stability theory for nonlinear complementarity problems in the setting of infinite dimensional Banach spaces. We first show that each nonlinear complementarity problem can be approximated arbitrarily by a nonlinear complementarity problem which is stable in the sense that the small change of the objective function results in the small change of its solution set; and thus we say that almost all complementarity problems are stable from viewpoint of Baire category. Secondly, we show that each nonlinear complementarity problem has, at least, one connected component of its solutions which is stable, though in general its solution set may not have good behaviour (i.e., not stable). Our results show that if a complementarity problem has only one connected solution set, it is then always stable without the assumption that the functions are either Lipschitz or differentiable.     

Paths, trees and matchings under disjunctive constraints

We study the minimum spanning tree problem, the maximum matching problem and the shortest path problem subject to binary disjunctive constraints: A negative disjunctive constraint states that a certain pair of edges cannot be contained simultaneously in a feasible solution. It is convenient to represent these negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the edges of the underlying graph, and whose edges encode the constraints.We prove that the minimum spanning tree problem is strongly NP-hard, even if every connected component of the conflict graph is a path of length two. On the positive side, this problem is polynomially solvable if every connected component is a single edge (that is, a path of length one). The maximum matching problem is NP-hard for conflict graphs where every connected component is a single edge.Furthermore we will also investigate these graph problems under positive disjunctive constraints: In this setting for certain pairs of edges, a feasible solution must contain at least one edge from every pair. We establish a number of complexity results for these variants including APX-hardness for the shortest path problem.     

Security and efficiency data sharing scheme for cloud storage

With the adoption and diffusion of data sharing paradigm in cloud storage, there have been increasing demands and concerns for shared data security. Ciphertext Policy Attribute-Based Encryption (CP-ABE) is becoming a promising cryptographic solution to the security problem of shared data in cloud storage. However due to key escrow, backward security and inefficiency problems, existing CP-ABE schemes cannot be directly applied to cloud storage system. In this paper, an effective and secure access control scheme for shared data is proposed to solve those problems. The proposed scheme refines the security of existing CP-ABE based schemes. Specifically, key escrow and conclusion problem are addressed by dividing key generation center into several distributed semi-trusted parts. Moreover, secrecy revocation algorithm is proposed to address not only back secrecy but efficient problem in existing CP-ABE based scheme. Furthermore, security and performance analyses indicate that the proposed scheme is both secure and efficient for cloud storage.     

2-InterConnected Facility Location: Specification,Complexity, and Exact Solutions

Connected facility location combines cost-efficient facility placement and the requirement to connect the facilities among each other. Such problems arise, e.g., in telecommunication applications where networks consist of a central core and local clients connected to it. Reliability of the core is a central issue, and we may hence require the core to be at least 2-connected.We establish the problem class of 2-interConnected Facility Location (2-iCFL), categorize its central variants, and prove that they are hard to approximate. However, our computational results show that our orientation-based ILPs allow us to effectively solve such problems to optimality for hundreds of nodes. We also establish constructive characterizations for feasible problem instances, to be used for algorithmic feasibility checks, preprocessing, and heuristics.     

The Riemann–Hilbert problem and the generalized Neumann kernel on multiply connected regions

This paper presents and studies Fredholm integral equations associated with the linear Riemann–Hilbert problems on multiply connected regions with smooth boundary curves. The kernel of these integral equations is the generalized Neumann kernel. The approach is similar to that for simply connected regions (see [R. Wegmann, A.H.M. Murid, M.M.S. Nasser, The Riemann–Hilbert problem and the generalized Neumann kernel, J. Comput. Appl. Math. 182 (2005) 388–415]). There are, however, several characteristic differences, which are mainly due to the fact, that the complement of a multiply connected region has a quite different topological structure. This implies that there is no longer perfect duality between the interior and exterior problems.     

On some balanced, totally balanced and submodular delivery games

This paper studies a class of delivery problems associated with the Chinese postman problem and a corresponding class of delivery games. A delivery problem in this class is determined by a connected graph, a cost function defined on its edges and a special chosen vertex in that graph which will be referred to as the post office. It is assumed that the edges in the graph are owned by different individuals and the delivery game is concerned with the allocation of the traveling costs incurred by the server, who starts at the post office and is expected to traverse all edges in the graph before returning to the post office. A graph G is called Chinese postman-submodular, or, for short, CP-submodular (CP-totally balanced, CP-balanced, respectively) if for each delivery problem in which G is the underlying graph the associated delivery game is submodular (totally balanced, balanced, respectively). For undirected graphs we prove that CP-submodular graphs and CP-totally balanced graphs are weakly cyclic graphs and conversely. An undirected graph is shown to be CP-balanced if and only if it is a weakly Euler graph. For directed graphs, CP-submodular graphs can be characterized by directed weakly cyclic graphs. Further, it is proven that any strongly connected directed graph is CP-balanced. For mixed graphs it is shown that a graph is CP-submodular if and only if it is a mixed weakly cyclic graph. Finally, we note that undirected, directed and mixed weakly cyclic graphs can be recognized in linear time. Received May 20, 1997 / Revised version received August 18, 1998?Published online June 11, 1999     

Degenerate parabolic equations with initial data measures

We address the problem of existence of solutions to degenerate (and nondegenerate) parabolic equations under optimal assumptions on the initial data, which are assumed to be measures. The requirements imposed on the initial data are connected both with the degeneracy of the principal part of the equation, and with the form of the nonlinear forcing term. The latter depends on the space gradient of a power of the solution. Applications to related problems are also outlined.

     

Inverse Scattering Transform for the Focusing Ablowitz‐Ladik System with Nonzero Boundary Conditions

The purpose of this paper is to construct the inverse scattering transform for the focusing Ablowitz‐Ladik equation with nonzero boundary conditions at infinity. Both the direct and the inverse problems are formulated in terms of a suitable uniform variable; the inverse problem is posed as a Riemann‐Hilbert problem on a doubly connected curve in the complex plane, and solved by properly accounting for the asymptotic dependence of eigenfunctions and scattering data on the Ablowitz‐Ladik potential.     

Mathematical Modelling of Cable Stayed Bridges: Existence, Uniqueness, Continuous Dependence on Data, Homogenization of Cable Systems

A model of a cable stayed bridge is proposed. This model describes the behaviour of the center span, the part between pylons, hung on one row of cable stays. The existence, the uniqueness of a solution of a time independent problem and the continuous dependence on data are proved. The existence and the uniqueness of a solution of a linearized dynamic problem are proved. A homogenizing procedure making it possible to replace cables by a continuous system is proposed. A nonlinear dynamic problem connected with the homogenizing procedure is proposed and the existence and uniqueness of a solution are proved.     

Optimality conditions and duality on approximate solutions in vector optimization with arcwise connectivity

In this paper a new class of generalized vector-valued arcwise connected functions, termed sub-arcwise connected functions, is introduced. The properties of sub-arcwise connected functions are derived. The approximate quasi efficient solutions of vector optimization problems are studied, and the necessary and sufficient optimality conditions are obtained under the assumption of arcwise connectivity. An approximate Mond-Weir type dual problem is formulated and the duality theorems are established.     

Functional-differential equations in a class of analytic functions and its application to elastic composites

According to Muskhelishvili’s approach, two-dimensional elastic problems for media with non-overlapping inclusions are reduced to boundary value problems for analytic functions in multiply connected domains. Using a method of functional equations developed by Mityushev, we reduce such a problem for a circular multiply connected domain to functional-differential equations. It is proved that the operator corresponding to the functional-differential equations is compact in the Hardy–Sobolev space. Moreover, these equations can be solved by the method of successive approximation under some natural conditions.     

A meshless method for nonhomogeneous polyharmonic problems using method of fundamental solution coupled with quasi-interpolation technique

This paper proposes a meshless method based on coupling the method of fundamental solutions (MFS) with quasi-interpolation for the solution of nonhomogeneous polyharmonic problems. The original problems are transformed to homogeneous problems by subtracting a particular solution of the governing differential equation. The particular solution is approximated by quasi-interpolation and the corresponding homogeneous problem is solved using the MFS. By applying quasi-interpolation, problems connected with interpolation can be avoided. The error analysis and convergence study of this meshless method are given for solving the boundary value problems of nonhomogeneous harmonic and biharmonic equations. Numerical examples are also presented to show the efficiency of the method.     

Integral points, divisibility between values of polynomials and entire curves on surfaces

We prove some new degeneracy results for integral points and entire curves on surfaces; in particular, we provide the first examples, to our knowledge, of a simply connected smooth variety whose sets of integral points are never Zariski-dense. Some of our results are connected with divisibility problems, i.e. the problem of describing the integral points in the plane where the values of some given polynomials in two variables divide the values of other given polynomials.     

Inverse source problem and active shielding for composite domains

The problem of active shielding (AS) for a multiply connected domain consists of constructing additional sources of the field (e.g., acoustic) so that all individual subdomains can either communicate freely with one another or otherwise be shielded from their peers. This problem can be interpreted as a special inverse source problem for the differential equation (or system) that governs the field. In the paper, we obtain general solution for a discretized composite AS problem and show that it reduces to solving a collection of auxiliary problems for simply connected domains.