On minima of a functional of the gradient: Upper and lower solutions

This paper studies a scalar minimization problem with an integral functional of the gradient under affine boundary conditions. A new approach is proposed using a minimal and a maximal solution to the convexified problem. We prove a density result: any relaxed solution continuously depending on boundary data may be approximated uniformly by solutions of the nonconvex problem keeping continuity relative to data. We also consider solutions to the nonconvex problem having Lipschitz dependence on boundary data with the best Lipschitz constant.     

Initial value problems for creeping flow of Maxwell fluids

We consider the flow of nonlinear Maxwell fluids in the unsteady quasistatic case, where the effect of inertia is neglected. We study the well-posedness of the resulting PDE initial-boundary value problem locally in time. This well-posedness depends on the unique solvability of an elliptic boundary value problem. We first present results for the 3D case with sufficiently small initial data and for a simple shear flow problem with arbitrary initial data; after that we extend our results to some 3D flow problems with large initial data.We solve our problem using an iteration between linear subproblems. The limit of the iteration provides the solution of our original problem.     

Privacy-preserving data splitting: a combinatorial approach

Privacy-preserving data splitting is a technique that aims to protect data privacy by storing different fragments of data in different locations. In this work we give a new combinatorial formulation to the data splitting problem. We see the data splitting problem as a purely combinatorial problem, in which we have to split data attributes into different fragments in a way that satisfies certain combinatorial properties derived from processing and privacy constraints. Using this formulation, we develop new combinatorial and algebraic techniques to obtain solutions to the data splitting problem. We present an algebraic method which builds an optimal data splitting solution by using Gröbner bases. Since this method is not efficient in general, we also develop a greedy algorithm for finding solutions that are not necessarily minimally sized.

     

Collision-free path coloring with application to minimum-delay gathering in sensor networks

Efficient data gathering is an important challenge in sensor networks. In this paper we address the problem of gathering sensed data to the sink of a sensor network minimizing the time to complete the process. We present optimal time data gathering algorithms for any sensor network topology, in the half-duplex with directional antennas model, when each sensor has one data packet to be gathered and merging of packets is not allowed at intermediate nodes. Our results improve on existing approximation algorithms. We approach the gathering problem by obtaining optimal solutions to a path coloring problem in graphs.     

On analytic solutions to the generalized Cauchy problem with data on three surfaces for a quasilinear system

The generalized Cauchy problem with data on three surfaces is under consideration for a quasilinear analytic system of the third order. Under some simplifying assumption, we find necessary and sufficient conditions for existence of a solution in the form of triple series in the powers of the independent variables. We obtain convenient sufficient conditions under which the data of the generalized Cauchy problem has a unique locally analytic solution. We give counterexamples demonstrating that in the case we study it is impossible to state necessary and sufficient conditions for analytic solvability of the generalized Cauchy problem. We also show that the analytic solution can fail to exist even if the generalized Cauchy problem with data on three surfaces has a formal solution since the series converge only at a sole point, the origin.     

Boolean regression

We take a regression-based approach to the problem of induction, which is the problem of inferring general rules from specific instances. Whereas traditional regression analysis fits a numerical formula to data, we fit a logical formula to boolean data. We can, for instance, construct an expert system for fitting rules to an expert's observed behavior. A regression-based approach has the advantage of providing tests of statistical significance as well as other tools of regression analysis. Our approach can be extended to nonboolean discrete data, and we argue that it is better suited to rule construction than logit and other types of categorical data analysis. We find maximum likelihood and bayesian estimates of a best-fitting boolean function or formula and show that bayesian estimates are more appropriate. We also derive confidence and significance levels. We show that finding the best-fitting logical formula is a pseudo-boolean optimization problem, and finding the best-fitting monotone function is a network flow problem.The first and second authors gratefully acknowledge the partial support of NSF (Grant DMS 89-06870) and AFOSR (Grants 89-0512 and 90-0008), and the third author that of AFOSR (Grant 91-0287) and ONR (Grant N00014-92-J-1028).     

Tabu search approaches for solving the two-group classification problem

The two-group classification problem consists in constructing a classifier that can distinguish between the two groups. In this paper, we consider the two-group classification problem which consists in determining a hyperplane that minimizes the number of misclassified points. We assume that the data set is numeric and with no missing data. We develop a tabu search (TS) heuristic for solving this NP-hard problem. The TS approach is based on a more convenient equivalent formulation of the classification problem. We also propose supplementary new intensification phases based on surrogate constraints. The results of the conducted computational experiments show that our TS algorithms produce solutions very close to the optimum and require significantly lower computational effort, so it is a valuable alternative to the MIP approaches. Moreover the tabu search procedures showed in this paper can be extended in a natural way to the general classification problem, which consists of generating more than one separating hyperplanes.     

On possibility of obtaining linear accuracy evaluation of approximate solutions to inverse problems

We consider a concept of linear a priori estimate of the accuracy for approximate solutions to inverse problems with perturbed data. We establish that if the linear estimate is valid for a method of solving the inverse problem, then the inverse problem is well-posed according to Tikhonov. We also find conditions, which ensure the converse for the method of solving the inverse problem independent on the error levels of data. This method is well-known method of quasi-solutions by V. K. Ivanov. It provides for well-posed (according to Tikhonov) inverse problems the existence of linear estimates. If the error levels of data are known, a method of solving well-posed according to Tikhonov inverse problems is proposed. This method called the residual method on the correctness set (RMCS) ensures linear estimates for approximate solutions. We give an algorithm for finding linear estimates in the RMCS.     

On strong optimality of interval linear programming

We consider a linear programming problem with interval data. We discuss the problem of checking whether a given solution is optimal for each realization of interval data. This problem was studied for particular forms of linear programming problems. Herein, we extend the results to a general model and simplify the overall approach. Moreover, we inspect computational complexity, too. Eventually, we investigate a related optimality concept of semi-strong optimality, showing its characterization and complexity.     

Asymptotic behavior of solutions to a system of viscous conservation laws related to a phase transition problem

We study the asymptotic behavior of solutions for a system of viscous conservation laws with discontinuous initial data. We discuss mainly the case where the system without the viscosity term is of hyperbolic elliptic mixed type. This problem is related to a phase transition problem. We study the initial value problem and show the decay rates of solutions to piecewise constant states where two phases coexist. The modification necessary for the hyperbolic case is also discussed.     

Non-formation of a vacuum state in a standing piston problem

When boundary data is introduced, additional terms are introduced into the weak formulation of the Navier-Stokes conservation law. We examine the example of single standing piston problem. The single piston problem corresponds to a fixed boundary problem.It is intuitively clear when a single piston filled with gas is pulled apart, even though gas becomes sparse in density, a vacuum state is never formed, because of viscosity. To study this rigorously, the Navier-Stokes equations are used to describe the gas's density and velocity, subject to the presence of viscosity. We prove that, given reasonable assumptions on the boundary data, vacuum states cannot form, if they are not present initially.     

Stability properties of an inverse parabolic problem with unknown boundaries

We treat the stability issue for an inverse problem arising from non-destructive evaluation by thermal imaging. We consider the determination of an unknown portion of the boundary of a thermic conducting body by overdetermined boundary data for a parabolic initial-boundary value problem. We obtain that when the unknown part of the boundary is a priori known to be smooth, the data are as regular as possible and all possible measurements are taken into account, the problem is exponentially ill-posed. Then, we prove that a single measurement with some a priori information on the unknown part of the boundary and minimal assumptions on the data, in particular on the thermal conductivity, is enough to have stable determination of the unknown boundary. Given the exponential ill-posedness, the stability estimate obtained is optimal. AMS 2000 Mathematics Subject Classification. Primary 35R30, Secondary 35B60, 33C90     

Haplotyping with missing data via perfect path phylogenies

Computational methods for inferring haplotype information from genotype data are used in studying the association between genomic variation and medical condition. Recently, Gusfield proposed a haplotype inference method that is based on perfect phylogeny principles. A fundamental problem arises when one tries to apply this approach in the presence of missing genotype data, which is common in practice. We show that the resulting theoretical problem is NP-hard even in very restricted cases. To cope with missing data, we introduce a variant of haplotyping via perfect phylogeny in which a path phylogeny is sought. Searching for perfect path phylogenies is strongly motivated by the characteristics of human genotype data: 70% of real instances that admit a perfect phylogeny also admit a perfect path phylogeny. Our main result is a fixed-parameter algorithm for haplotyping with missing data via perfect path phylogenies. We also present a simple linear-time algorithm for the problem on complete data.     

On a family of initial-boundary value problems for the heat equation

We consider the heat problem with nonlocal boundary conditions containing a real parameter. For the zero value of the parameter, this problem is well known as the Samarskii-Ionkin problem and has been comprehensively studied. We analyze the spectral problem for the operator of second derivative subjected to the boundary conditions of the original problem. By separation of variables, we prove the existence and uniqueness of a classical solution for any nonzero value of the parameter. The obtained a priori estimates for a solution imply the stability of the problem with respect to the initial data.     

Optimality of Balanced Proper Orthogonal Decomposition for Data Reconstruction

Proper orthogonal decomposition (POD) finds an orthonormal basis yielding an optimal reconstruction of a given dataset. We consider an optimal data reconstruction problem for two general datasets related to balanced POD, which is an algorithm for balanced truncation model reduction for linear systems. We consider balanced POD outside of the linear systems framework, and prove that it solves the optimal data reconstruction problem. The theoretical result is illustrated with an example.     

Solving the Simple Plant Location Problem using a Data Correcting Approach

The Data Correcting Algorithm is a branch and bound type algorithm in which the data of a given problem instance is `corrected' at each branching in such a way that the new instance will be as close as possible to a polynomially solvable instance and the result satisfies an acceptable accuracy (the difference between optimal and current solution). In this paper the data correcting algorithm is applied to determining exact and approximate optimal solutions to the simple plant location problem. Implementations of the algorithm are based on a pseudo-Boolean representation of the goal function of this problem, and a new reduction rule. We study the efficiency of the data correcting approach using two different bounds, the Khachaturov-Minoux bound and the Erlenkotter bound. We present computational results on several benchmark instances, which confirm the efficiency of the data-correcting approach.     

Nonlinear spectral problem for a Hamiltonian system of differential equations with redundant conditions

We consider a nonlinear spectral problem for a self-adjoint Hamiltonian system of differential equations. The boundary conditions correspond to a self-adjoint problem. It is assumed that the input data (the matrix of the system and the matrices of the boundary conditions) satisfy certain conditions of monotonicity with respect to the spectral parameter. In addition to the main boundary conditions, a redundant nonlocal condition given by a Stieltjes integral is imposed on the solution. For the nontrivial solvability of the over-determined problem thus obtained, the original problem is replaced by an auxiliary problem that is consistent with the entire set of conditions. This auxiliary problem is obtained from the original one by allowing a discrepancy of a specific form. We study the resulting problem and give a numerical method for its solution.     

Nonlocal problem with integral conditions for a system of hyperbolic equations in characteristic rectangle

We consider a nonlocal problem with integral conditions for a system of hyperbolic equations in rectangular domain. We investigate the questions of existence of unique classical solution to the problemunder consideration and approaches of its construction. Sufficient conditions of unique solvability to the investigated problem are established in the terms of initial data. The nonlocal problem with integral conditions is reduced to an equivalent problem consisting of the Goursat problem for the system of hyperbolic equations with functional parameters and functional relations. We propose algorithms for finding a solution to the equivalent problem with functional parameters on the characteristics and prove their convergence. We also obtain the conditions of unique solvability to the auxiliary boundary-value problem with an integral condition for the system of ordinary differential equations. As an example, we consider the nonlocal boundary-value problem with integral conditions for a two-dimensional system of hyperbolic equations.     

Solution to the Neumann problem exterior to a prolate spheroid by radial basis functions

We consider the exterior Neumann problem of the Laplacian with boundary condition on a prolate spheroid. We propose to use spherical radial basis functions in the solution of the boundary integral equation arising from the Dirichlet–to–Neumann map. Our approach is particularly suitable for handling of scattered data, e.g. satellite data. We also propose a preconditioning technique based on domain decomposition method to deal with ill-conditioned matrices arising from the approximation problem.     

Analysis of a history-dependent frictional contact problem

We consider a mathematical model which describes the quasistatic contact between a viscoelastic body and a foundation. The material’s behaviour is modelled with a constitutive law with long memory. The contact is frictional and is modelled with normal compliance and memory term, associated to the Coulomb’s law of dry friction. We present the classical formulation of the problem, list the assumptions on the data and derive a variational formulation of the model. Then we prove the unique weak solvability of the problem. The proof is based on arguments of history-dependent variational inequalities. We also study the dependence of the weak solution with respect to the data and prove a convergence result.