On the Main Aspects of the Inverse Conductivity Problem

We consider a nonlinear inverse problem for an elliptic partial differential equation known as the Calder{\''o}n problem or the inverse conductivity problem. Based on several results, we briefly summarize them to motivate this research field. We give a general view of the problem by reviewing the available results for $C^2$ conductivities. After reducing the original problem to the inverse problem for a Schr\"odinger equation, we apply complex geometrical optics solutions to show its uniqueness. After extending the ideas of the uniqueness proof result, we establish a stable dependence between the conductivity and the boundary measurements. By using the Carleman estimate, we discuss the partial data problem, which deals with measurements that are taken only in a part of the boundary.     

On the complexity of the dominating induced matching problem in hereditary classes of graphs

The dominating induced matching problem, also known as efficient edge domination, is the problem of determining whether a graph has an induced matching that dominates every edge of the graph. This problem is known to be NP-complete. We study the computational complexity of the problem in special graph classes. In the present paper, we identify a critical class for this problem (i.e., a class lying on a “boundary” separating difficult instances of the problem from polynomially solvable ones) and derive a number of polynomial-time results. In particular, we develop polynomial-time algorithms to solve the problem for claw-free graphs and convex graphs.     

Numerical Optimization for the Location of Wastewater Outfalls

In this paper we solve a constrained optimal control problem related to the location of the wastewater outfalls in a sewage disposal system. This is a problem where the control is the position and the constraints are non-convex and pointwise, which makes difficult its resolution. We discretize the problem by means of a characteristics-Galerkin method and we use three algorithms for the numerical resolution of the discretized optimization problem: an interior point algorithm, the Nelder-Mead simplex method and a duality method. Finally, we compare the numerical results obtained by applying the described methods for a realistic problem posed in the ría of Vigo (Galicia, Spain).     

Optimal design of the damping set for the stabilization of the wave equation

We consider the problem of optimizing the shape and position of the damping set for the internal stabilization of the linear wave equation in RN, N=1,2. In a first theoretical part, we reformulate the problem into an equivalent non-convex vector variational one using a characterization of divergence-free vector fields. Then, by means of gradient Young measures, we obtain a relaxed formulation of the problem in which the original cost density is replaced by its constrained quasi-convexification. This implies that the new relaxed problem is well-posed in the sense that there exists a minimizer and, in addition, the infimum of the original problem coincides with the minimum of the relaxed one. In a second numerical part, we address the resolution of the relaxed problem using a first-order gradient descent method. We present some numerical experiments which highlight the influence of the over-damping phenomena and show that for large values of the damping potential the original problem has no minimizer. We then propose a penalization technique to recover the minimizing sequences of the original problem from the optimal solution of the relaxed one.     

Survivable networks,linear programming relaxations and the parsimonious property

We consider the survivable network design problem — the problem of designing, at minimum cost, a network with edge-connectivity requirements. As special cases, this problem encompasses the Steiner tree problem, the traveling salesman problem and thek-edge-connected network design problem. We establish a property, referred to as the parsimonious property, of the linear programming (LP) relaxation of a classical formulation for the problem. The parsimonious property has numerous consequences. For example, we derive various structural properties of these LP relaxations, we present some algorithmic improvements and we perform tight worst-case analyses of two heuristics for the survivable network design problem.The research of both authors was partially supported by the National Science Foundation under grant ECS-8717970 and the Leaders for manufacturing program at MIT.     

On the subset sum problem over finite fields

The subset sum problem over finite fields is a well-known NP-complete problem. It arises naturally from decoding generalized Reed–Solomon codes. In this paper, we study the number of solutions of the subset sum problem from a mathematical point of view. In several interesting cases, we obtain explicit or asymptotic formulas for the solution number. As a consequence, we obtain some results on the decoding problem of Reed–Solomon codes.     

Time optimal sampled-data controls for the heat equation

In this paper, we first design a time optimal control problem for the heat equation with sampled-data controls, and then use it to approximate a time optimal control problem for the heat equation with distributed controls.The study of such a time optimal sampled-data control problem is not easy, because it may have infinitely many optimal controls. We find connections among this problem, a minimal norm sampled-data control problem and a minimization problem, and obtain some properties on these problems. Based on these, we not only build up error estimates for optimal time and optimal controls between the time optimal sampled-data control problem and the time optimal distributed control problem, in terms of the sampling period, but we also prove that such estimates are optimal in some sense.     

A numerical method for solving the Dirichlet problem for the wave equation

In this paper we present a numerical method for solving the Dirichlet problem for a two-dimensional wave equation. We analyze the ill-posedness of the problem and construct a regularization algorithm. Using the Fourier series expansion with respect to one variable, we reduce the problem to a sequence of Dirichlet problems for one-dimensional wave equations. The first stage of regularization consists in selecting a finite number of problems from this sequence. Each of the selected Dirichlet problems is formulated as an inverse problem Aq = f with respect to a direct (well-posed) problem. We derive formulas for singular values of the operator A in the case of constant coefficients and analyze their behavior to judge the degree of ill-posedness of the corresponding problem. The problem Aq = f on a uniform grid is reduced to a system of linear algebraic equations A _ll q = F. Using the singular value decomposition, we find singular values of the matrix A _ll and develop a numerical algorithm for constructing the r-solution of the original problem. This algorithm was tested on a discrete problem with relatively small number of grid nodes. To improve the calculated r-solution, we applied optimization but observed no noticeable changes. The results of computational experiments are illustrated.     

Criterion for the strong solvability of the mixed Cauchy problem for the Laplace equation

In the present paper, we prove a necessary and sufficient condition for the well-posedness of the problem indicated in the title in the space L ₂(Ω). To this end, we use expansions in the eigenfunctions of the mixed Cauchy problem for the Laplace equation with a deviating argument.     

On the semicontinuity problem of fibers and global F-regularity

In this article, we discuss the semicontinuity problem of certain properties on fibers for a morphism of schemes. One aspect of this problem is local. Namely, we consider properties of schemes at the level of local rings, in which the main results are established by solving the lifting and localization problems for local rings. In particular, we obtain the localization theorems in the case of seminormal and F-rational rings, respectively. Another aspect of this problem is global, which is often related to the vanishing problem of certain higher direct image sheaves. As a test example, we consider the deformation of the global F-regularity.     

A new method for solving the nonlinear second-order boundary value differential equations

In this paper we use measure theory to solve a wide range of second-order boundary value ordinary differential equations. First, we transform the problem to a first order system of ordinary differential equations (ODE’s) and then define an optimization problem related to it. The new problem is modified into one consisting of the minimization of a linear functional over a set of Radon measures; the optimal measure is then approximated by a finite combination of atomic measures and the problem converted approximatly to a finite-dimensional linear programming problem. The solution to this problem is used to construct the approximate solution of the original problem. Finally we get the error functionalE (we define in this paper) for the approximate solution of the ODE’s problems.     

An Iterative Method for Finding the Least Solution to the Tensor Complementarity Problem

In this paper, we are concerned with finding the least solution to the tensor complementarity problem. When the involved tensor is strongly monotone, we present a way to estimate the nonzero elements of the solution in a successive manner. The procedure for identifying the nonzero elements of the solution gives rise to an iterative method of solving the tensor complementarity problem. In each iteration, we obtain an iterate by solving a lower-dimensional tensor equation. After finitely many iterations, the method terminates with a solution to the problem. Moreover, the sequence generated by the method is monotonically convergent to the least solution to the problem. We then extend this idea for general case and propose a sequential mathematical programming method for finding the least solution to the problem. Since the least solution to the tensor complementarity problem is the sparsest solution to the problem, the method can be regarded as an extension of a recent result by Luo et al. (Optim Lett 11:471–482, 2017). Our limited numerical results show that the method can be used to solve the tensor complementarity problem efficiently.     

On the Minimum Sum Coloring of P 4-Sparse Graphs

In this paper, we study the minimum sum coloring (MSC) problem on P ₄-sparse graphs. In the MSC problem, we aim to assign natural numbers to vertices of a graph such that adjacent vertices get different numbers, and the sum of the numbers assigned to the vertices is minimum. Based in the concept of maximal sequence associated with an optimal solution of the MSC problem of any graph, we show that there is a large sub-family of P ₄-sparse graphs for which the MSC problem can be solved in polynomial time. Moreover, we give a parameterized algorithm and a 2-approximation algorithm for the MSC problem on general P ₄-sparse graphs.     

On the determination of the potential function from given orbits

The paper deals with the problem of finding the field of force that generates a given (N ? 1)-parametric family of orbits for a mechanical system with N degrees of freedom. This problem is usually referred to as the inverse problem of dynamics. We study this problem in relation to the problems of celestial mechanics. We state and solve a generalization of the Dainelli and Joukovski problem and propose a new approach to solve the inverse Suslov’s problem. We apply the obtained results to generalize the theorem enunciated by Joukovski in 1890, solve the inverse Stäckel problem and solve the problem of constructing the potential-energy function U that is capable of generating a bi-parametric family of orbits for a particle in space. We determine the equations for the sought-for function U and show that on the basis of these equations we can define a system of two linear partial differential equations with respect to U which contains as a particular case the Szebehely equation. We solve completely a special case of the inverse dynamics problem of constructing U that generates a given family of conics known as Bertrand’s problem. At the end we establish the relation between Bertrand’s problem and the solutions to the Heun differential equation. We illustrate our results by several examples.     

Algebraic formulations for the solution of the nullspace‐free eigenvalue problem using the inexact Shift‐and‐Invert Lanczos method

Given the generalized symmetric eigenvalue problem Ax=λMx, with A semidefinite and M definite, we analyse some algebraic formulations for the approximation of the smallest non‐zero eigenpairs, assuming that a sparse basis for the null space is available. In particular, we consider the inexact version of the Shift‐and‐Invert Lanczos method, and we show that apparently different algebraic formulations provide the same approximation iterates, under some natural hypotheses. Our results suggest that alternative strategies need to be explored to really take advantage of the special problem setting, other than reformulating the algebraic problem. Experiments on a real application problem corroborate our theoretical findings. Copyright © 2002 John Wiley & Sons, Ltd.     

An initial-boundary value problem for the Maxwell equations

In this paper, by using methods from complex analysis and quaternionic analysis, we investigate an initial-boundary value problem for the Maxwell equations and obtain the general solutions and solvable conditions of the problem respectively in different cases. In addition, by using a similar method, we also discuss an initial-boundary value problem for a hyperbolic complex system of first order equations in R³.     

New developments in the application of Pontryagin's Principle for the hydrothermal optimization

^** Email: bayon{at}uniovi.es In this paper we have developed a much simpler theory than previousones that resolves the problem of the optimization of hydrothermalsystems. The problem involves non-holonomic inequality constraints.In particular, we have established a necessary condition forthe stationary functions of the functional. We shall use Pontryagin'sMinimum Principle as the basis for proving this theorem, settingout our problem in terms of optimal control in continuous time,with the Lagrange-type functional. This theorem allows us toelaborate the optimization algorithm that leads to the determinationof the optimal solution of the hydrothermal system. We generalizethe problem, taking into account a cost associated with thewater, to then set out and solve the corresponding Bolza's problem.Finally, we present an example employing the algorithm developedfor this purpose with the ‘Mathematica’ package.     

On the complexity of the disjoint paths problem

In this paper we consider the disjoint paths problem. Given a graphG and a subsetS of the edge-set ofG the problem is to decide whether there exists a family of disjoint circuits inG each containing exactly one edge ofS such that every edge inS belongs to a circuit inC. By a well-known theorem of P. Seymour the edge-disjoint paths problem is polynomially solvable for Eulerian planar graphsG. We show that (assumingPNP) one can drop neither planarity nor the Eulerian condition onG without losing polynomial time solvability. We prove theNP-completeness of the planar edge-disjoint paths problem by showing theNP-completeness of the vertex disjoint paths problem for planar graphs with maximum vertex-degree three. This disproves (assumingPNP) a conjecture of A. Schrijver concerning the existence of a polynomial time algorithm for the planar vertex-disjoint paths problem. Furthermore we present a counterexample to a conjecture of A. Frank. This conjecture would have implied a polynomial algorithm for the planar edge-disjoint paths problem. Moreover we derive a complete characterization of all minorclosed classes of graphs for which the disjoint paths problem is polynomially solvable. Finally we show theNP-completeness of the half-integral relaxation of the edge-disjoint paths problem. This implies an answer to the long-standing question whether the edge-disjoint paths problem is polynomially solvable for Eulerian graphs.Supported by Sonderforschungsbereich 303 (DFG)     

On relaxing the integrality of the allocation variables of the reliability fixed-charge location problem

The aim of the reliability fixed-charge location problem is to find robust solutions to the fixed-charge location problem when some facilities might fail with probability q. In this paper we analyze for which allocation variables in the reliability fixed-charge location problem formulation the integrality constraint can be relaxed so that the optimal value matches the optimal value of the binary problem. We prove that we can relax the integrality of all the allocation variables associated to non-failable facilities or of all the allocation variables associated to failable facilities but not of both simultaneously. We also demonstrate that we can relax the integrality of all the allocation variables whenever a family of valid inequalities is added to the set of constraints or whenever the parameters of the problem satisfy certain conditions. Finally, when solving the instances in a data set we discuss which relaxation or which modification of the problem works better in terms of resolution time and we illustrate that relaxing the integrality of the allocation variables inappropriately can alter the objective value considerably.     

On the gluing problem for the spectral invariants of Dirac operators

In this paper, we solve the gluing problem for the ζ-determinant of a Dirac Laplacian. To do so, we develop a new approach to solve such problems which relies heavily on the theory of elliptic boundary problems, the analysis of the resolvent of the Dirac operator, and the introduction of an auxiliary model problem. Moreover, as a byproduct of our approach we obtain a new gluing formula for the eta invariant au gratis.