An elliptic boundary problem in a half–space

The spectral theory for general non–selfadjoint elliptic boundary problems involving a discontinuous weight function has been well developed under certain restrictions concerning the weight function. In the course of extending the results so far established to a more general weight function, there arises the problem of establishing, in an L_p Sobolev space setting, the existence of and a priori estimates for solutions for a boundary problem for the half–space ?ⁿ₊ involving a weight function which vanishes at the boundary x_n = 0. In this paper we resolve this problem.     

The Riesz Basis Property of an Indefinite Sturm-Liouville Problem with a Non-Odd Weight Function

For the Sturm-Liouville eigenvalue problem − f′′ = λrf on [−1, 1] with Dirichlet boundary conditions and with an indefinite weight function r changing its sign at 0 we discuss the question whether the eigenfunctions form a Riesz basis of the Hilbert space L ² _|r|[− 1, 1]. So far a number of sufficient conditions on r for the Riesz basis property are known. However, a sufficient and necessary condition is only known in the special case of an odd weight function r. We shall here give a generalization of this sufficient and necessary condition for certain generally non-odd weight functions satisfying an additional assumption.      

A Dirichlet problem for an H-system with variable H

We give conditions onH, a continuous and bounded real function inR ³, to obtain at least two solutions for the problem (Dir) below.H can be far from being constant in the sense of [9]. Our motivation is a better understanding of the Plateau problem for the prescribed mean curvature equation.     

Using Homogeneous Weights for Approximating the Partial Cover Problem

In this paper we consider the natural generalizations of two fundamental problems, the Set-Cover problem and the Min-Knapsack problem. We are given a hypergraph, each vertex of which has a nonnegative weight, and each edge of which has a nonnegative length. For a given threshold , our objective is to find a subset of the vertices with minimum total cost, such that at least a length of of the edges is covered. This problem is called the partial set cover problem. We present an O(|V|² + |H|)-time, Δ_E-approximation algorithm for this problem, where Δ_E ≥ 2 is an upper bound on the edge cardinality of the hypergraph and |H| is the size of the hypergraph (i.e., the sum of all its edges cardinalities). The special case where Δ_E = 2 is called the partial vertex cover problem. For this problem a 2-approximation was previously known, however, the time complexity of our solution, i.e., O(|V|²), is a dramatic improvement.We show that if the weights are homogeneous (i.e., proportional to the potential coverage of the sets) then any minimal cover is a good approximation. Now, using the local-ratio technique, it is sufficient to repeatedly subtract a homogeneous weight function from the given weight function.     

On Principal Eigenvalues for Indefinite Problems in Euclidean Space

For the eigenvalue problem—λΔu = q(x)u in IR^d, with the weight function q changing sign, conditions are discussed for existence of eigenvalues with positive decaying eigenfunctions.     

Linear problem of tracking a given motion under an integral constraint on control

We consider the problem of optimally tracking a given vector function by means of a generalized projection of the trajectory of a linear controlled object with an integral constraint on the control. The deviation from a given motion is measured in the metric of the space C ^m [0, T] of continuous vector functions of appropriate dimension m. We describe a constructive method for solving this optimization problem with a given accuracy.     

Critical exponents in a degenerate parabolic equation with weighted source

This article deals with the Fujita-type theorems to the Cauchy problem of degenerate parabolic equation not in divergence form with weighted source u _t ?=?u ^p Δu?+?a(x)u ^q in ? ⁿ ?×?(0,?T), where p?≥?1, q?>?1, and the positive weight function a(x) is of the order |x| ^m with m?>??2. It was known that for the degenerate diffusion equation in divergence form, the weight function affects both of the critical Fujita exponent and the second critical exponent (describing the critical smallness of initial data required by global solutions via the decay rates of the initial data at space-infinity). Contrarily, it is interesting to prove that the weight function in the present model with degenerate diffusion not in divergence form influences the second critical exponent only, without changing the critical Fujita exponent.     

The Calderón approach to an elliptic boundary problem

We consider a boundary problem for an elliptic system in a bounded region Ω ? ?ⁿ and where the spectral parameter is multiplied by a discontinuous weight function ω (x) = diag(ω₁(x), …, ω_N (x)). The problem is considered under limited smoothness assumptions and under an ellipticity with parameter condition. Recently, this problem was studied under the assumption that the ω_j (x)^–1 are essentially bounded in Ω. In this paper we suppose that ω (x) vanishes identically in a proper subregion Ω of Ω and that the ω_j (x)^–1 are essentially bounded in . Then by using methods which are a variant of those used in constructing the Calderón projectors for the boundary Γ of Ω, we shall derive results here which will enable us in a subsequent work to apply the ideas of Calderón to develop the spectral theory associated with the problem under consideration here (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Nonlinear programming and an optimization problem on infinitely differentiable functions

A nonnegative, infinitely differentiable function ø defined on the real line is called a Friedrichs mollifier function if it has support in [0, 1] and ₀ ¹ ø(t)dt=1. In this article the following problem is considered. Determine _k =inf ₀ ¹ vø^(k)(t)dt, k=1,..., where ø^(k) denotes thekth derivative of ø and the infimum is taken over the set of all mollifier functions. This problem has applications to monotone polynomial approximation as shown by this author elsewhere. In this article, the structure of the problem of determining _k is analyzed, and it is shown that the problem is reducible to a nonlinear programming problem involving the minimization of a strictly convex function of [(k–1)/2] variables, subject to a simple ordering restriction on the variables. An optimization problem on the functions of bounded variation, which is equivalent to the nonlinear programming problem, is also developed. The results of this article and those from approximation of functions theory are applied elsewhere to derive numerical values of various mathematical quantities involved in this article, e.g., _k =k~2^2k–1 for allk=1, 2, ..., and to establish certain inequalities of independent interest. This article concentrates on problem reduction and equivalence, and not numerical value.This research was supported in part by the National Science Foundation under Grant No. GK-32712.     

The multi-weighted Steiner tree problem

We formulate and investigate the Multi-Weighted Steiner Problem (MWS), a generalization of the Steiner problem in graphs, involving more than one weight function. As a special case, it contains the hierarchical network design problem. With the notion of "bottleneck length/distance", a min-max measure, we analyze the interaction between differently weighted edges in a solution. Combining the results with known methods for the Steiner problem in graphs and the hierarchical network design problem, two heuristics for the MWS are developed, one based on weight modifications and the other on exchanging edges. Both are of time complexityO(kv ²), withv the number of nodes andk the number of special nodes in the graph. The first is also suited for thedirected MWS; the second is expected to perform better on the undirected version. Before actually solving the Steiner problem in graphs and the hierarchical network design problem, preprocessing techniques exploiting tests to reduce the problem graphs have proven to be valuable. We adapt three prominent tests for use in the MWS.     

Weighted Hardy's inequality and the Kolmogorov equation perturbed by an inverse-square potential

In this article, we give necessary and sufficient conditions for the existence of a weak solution of a Kolmogorov equation perturbed by an inverse-square potential. More precisely, using a weighted Hardy's inequality with respect to an invariant measure μ, we show the existence of the semigroup solution of the parabolic problem corresponding to a generalized Ornstein–Uhlenbeck operator perturbed by an inverse-square potential in L ²(? ^N ,?μ). In the case of the classical Ornstein–Uhlenbeck operator we obtain nonexistence of positive exponentially bounded solutions of the parabolic problem if the coefficient of the inverse-square function is too large.     

Towards an example of a nonconvex monotone follower control problem

A one-dimensional monotone follower control problem with a nonconvex Lagrangian is considered. The control problem consists in tracking a standard Wiener process by an adapted nondecreasing process starting at 0. The verification theorem for the problem is presented. The optimal control and the value function are explicitly defined. For some values of parameters of the problem, it is shown that the value function belongs to C ². An interesting feature of the optimally controlled state process is that for some initial states it has jumps at times other than the inital time. Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 61, Optimal Control, 2008.     

Uniqueness and stability in an inverse problem for a Poisson’s equation

Consider the Poisson's equation ψ" (x) ＝ -ev-ψ eψ-v-N(x) with the Dirichlet boundary data, and we mainly investigate the inverse problem of determining the unknown function N(x) from a parameter function family. Some uniqueness and stability results in the inverse problem are obtained.     

Approximation Algorithm for MAX DICUT with Given Sizes of Parts

Given a directed graph G and an edge weight function w : A(G)→ R^ , the maximum directed cut problem (MAX DICUT) is that of finding a directed cut δ(S) with maximum total weight. We consider a version of MAX DICUT -- MAX DICUT with given sizes of parts or MAX DICUT WITH GSP -- whose instance is that of MAX DICUT plus a positive integer k, and it is required to find a directed cut δ(S) having maximum weight over all cuts δ(S) with |S| -- k. We present an approximation algorithm for this problem which is based on semidefinite programming (SDP) relaxation. The algorithm achieves the presently best performance guarantee for a range of k.     

Maximal regularity for the non-stationary Stokes system in an aperture domain

We prove estimates in L^s (0, T; L_w^q (W)) L^s (0, T; L_w^q (\Omega)) for the solution of the non-stationary Stokes system in an aperture domain, where 1 <s, q< ￥ \infty and the weight function w \omega is in the Muckenhoupt class A_q A_q .¶The result is achieved by combining a characterisation of maximal regularity by R {\mathcal R} -bounded operator families with the fact that R {\mathcal R} -boundedness follows from weighted estimates for Muckenhoupt weights.     

Multiple positive solutions of an elliptic equation with a convex-concave nonlinearity containing a sign-changing term

We study the existence of multiple positive solutions to a nonlinear Dirichlet problem for the p-Laplacian (in a bounded domain in ℝ ^N ) with a concave nonlinearity and with a nonlinear perturbation involving a function of the spatial variable whose sign can change the character of concavity. Under two different sets of conditions imposed on the perturbation, we prove the existence of two and three positive solutions, respectively.     

Approximation of the bifurcation function for elliptic boundary value problems

The bifurcation function for an elliptic boundary value problem is a vector field B(ω) on R ^d whose zeros are in a one‐to‐one correspondence with the solutions of the boundary value problem. Finite element approximations of the boundary value problem are shown to give rise to an approximate bifurcation function B^h(ω), which is also a vector field on R ^d. Estimates of the difference B(ω) − B^h(ω) are derived, and methods for computing B^h(ω) are discussed. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 194–213, 2000     

An Efficient Algorithm for Finding a Maximum Weight k-Independent Set on Trapezoid Graphs

The maximum weight k-independent set problem has applications in many practical problems like k-machines job scheduling problem, k-colourable subgraph problem, VLSI design layout and routing problem. Based on DAG (Directed Acyclic Graph) approach, an O(kn ²) time sequential algorithm is designed in this paper to solve the maximum weight k-independent set problem on weighted trapezoid graphs. The weights considered here are all non-negative and associated with each of the n vertices of the graph.     

A matroid algorithm and its application to the efficient solution of two optimization problems on graphs

We address the problem of finding a minimum weight baseB of a matroid when, in addition, each element of the matroid is colored with one ofm colors and there are upper and lower bound restrictions on the number of elements ofB with colori, fori = 1, 2,,m. This problem is a special case of matroid intersection. We present an algorithm that exploits the special structure, and we apply it to two optimization problems on graphs. When applied to the weighted bipartite matching problem, our algorithm has complexity O(|EV|+|V| ²log|V|). HereV denotes the node set of the underlying bipartite graph, andE denotes its edge set. The second application is defined on a general connected graphG = (V,E) whose edges have a weight and a color. One seeks a minimum weight spanning tree with upper and lower bound restrictions on the number of edges with colori in the tree, for eachi. Our algorithm for this problem has complexity O(|EV|+m ² |V|+ m|V| ²). A special case of this constrained spanning tree problem occurs whenV ^* is a set of pairwise nonadjacent nodes ofG. One must find a minimum weight spanning tree with upper and lower bound restrictions on the degree of each node ofV ^*. Then the complexity of our algorithm is O(|VE|+|V ^* V| ²). Finally, we discuss a new relaxation of the traveling salesman problem.This report was supported in part by NSF grant ECS 8601660.     

The Exterior Dirichlet Problem for the Biharmonic Equation: Solutions with Bounded Dirichlet Integral

We study the unique solvability of the Dirichlet problem for the biharmonic equation in the exterior of a compact set under the assumption that a generalized solution of this problem has a bounded Dirichlet integral with weight |x|^a. Depending on the value of the parameter ^a,a we prove uniqueness theorems or present exact formulas for the dimension of the solution space of the Dirichlet problem.