Optimal location with equitable loads

The problem considered in this paper is to find p locations for p facilities such that the weights attracted to each facility will be as close as possible to one another. We model this problem as minimizing the maximum among all the total weights attracted to the various facilities. We propose solution procedures for the problem on a network, and for the special cases of the problem on a tree or on a path. The complexity of the problem is analyzed, O(n) algorithms and an O(pn ³) dynamic programming algorithm are proposed for the problem on a path respectively for p=2 and p>2 facilities. Heuristic algorithms (two types of a steepest descent approach and tabu search) are proposed for its solution. Extensive computational results are presented.     

Vertex Cover: Further Observations and Further Improvements

Recently, there has been increasing interest and progress in lowering the worst-case time complexity for well-known NP-hard problems, particularly for the Cover problem. In this paper, new properties for the problem are indicated, and several simple and new techniques are introduced, which lead to an improved algorithm of time O(kn + 1.2852^k) for the problem. Our algorithm also induces improvement on previous algorithms for the problem on graphs of small degree.     

Polygon containment under translation

The polygon containment problem is the problem of deciding whether a polygon P can be translated to fit inside another polygon P'. We present algorithms for two cases of the polygon containment problem: when both P and P' are rectilinearly convex, and when P is convex and P' is arbitrary. In both cases the algorithms run in time O(n²logn), where n is the sum of the number of bounding edges of the two polygons. Applications to an inspection problem and a stock-cutting problem are discussed, as is the containment problem when both P and P' are nonconvex.     

About strongly polynomial time algorithms for quadratic optimization over submodular constraints

We present new strongly polynomial algorithms for special cases of convex separable quadratic minimization over submodular constraints. The main results are: an O(NM log(N ²/M)) algorithm for the problemNetwork defined on a network onM arcs andN nodes; an O(n logn) algorithm for thetree problem onn variables; an O(n logn) algorithm for theNested problem, and a linear time algorithm for theGeneralized Upper Bound problem. These algorithms are the best known so far for these problems. The status of the general problem and open questions are presented as well.This research has been supported in part by ONR grant N00014-91-J-1241.Corresponding author.     

Generalized -complementarity problems in Banach spaces

In this paper, a class of generalized f-complementarity problems and three classes of variational inequalities are introduced in real Banach spaces, and the equivalences among them are established under certain conditions. Several coercivity conditions are introduced for the existence of solutions of the generalized f-complementarity problem. Under some suitable assumptions, it is shown that each of these coercivity conditions is equivalent to the nonemptyness and boundedness of the solution set for the generalized f-complementarity problem in infinite-dimensional Banach spaces, and even the nonemptyness and compactness of the solution set for the generalized f-complementarity problem in finite-dimensional spaces. The existence of least elements for the feasible set of the generalized f-complementarity problem is also presented under suitable conditions.     

Parallel algorithms for permutation graphs

In this paper, parallel algorithms are presented for solving some problems on permutation graphs. The coloring problem is solved inO(log² n) time usingO(n ³/logn) processors on the CREW PRAM, orO(logn) time usingO(n ³) processors on the CRCW PRAM. The weighted clique problem, the weighted independent set problem, the cliques cover problem, and the maximal layers problem are all solved with the same complexities. We can also show that the longest common subsequence problem belongs to the class NC.     

Generalized dynamic programming methods in integer programming

When regarded as a shortest route problem, an integer program can be seen to have a particularly simple structure. This allows the development of an algorithm for finding thek ^th best solution to an integer programming problem with max{O(kmn), O(k logk)} operations. Apart from its value in the parametric study of an optimal solution, the approach leads to a general integer programming algorithm consisting of (1) problem relaxation, (2) solution of the relaxed problem parametrically by dynamic programming, and (3) generation ofk ^th best solutions until a feasible solution is found. Elementary methods based on duality for reducingk for a given problem relaxation are then outlined, and some examples and computational aspects are discussed.     

Convergence of a fourth-order singular perturbation of the n-dimensional radially symmetric Monge–Ampère equation

This paper concerns with the convergence analysis of a fourth-order singular perturbation of the Dirichlet Monge–Ampère problem in the n-dimensional radial symmetric case. A detailed study of the fourth- order problem is presented. In particular, various a priori estimates with explicit dependence on the perturbation parameter ε are derived, and a crucial convexity property is also proved for the solution of the fourth-order problem. Using these estimates and the convexity property, we prove that the solution of the perturbed problem converges uniformly and compactly to the unique convex viscosity solution of the Dirichlet Monge–Ampère problem. Rates of convergence in the H^k-norm for k = 0, 1, 2 are also established.     

Multicriteria movement synchronization scheduling problems and algorithms

This article deals with multicriteria optimization models and algorithms of movement scheduling for many objects to synchronize their movement (2CMSS problem). The model consists of two parts: (1) node–disjoint path planning visiting specified nodes for K objects with a given vector of intermediate nodes for each one (NDSP problem); (2) movement synchronization in some intermediate nodes (MS problem). For synchronous movement, two categories of criteria are defined: time of movement and ‘distance’ of K-moved objects from the movement pattern. We defined the problem as a discrete-continuous, non-linear, two-criteria mathematical programming problem. We proposed to use a two-stage algorithm to solve the 2CMSS problem (as lexicographic solution): At first we have to find the vector of node–disjoint shortest paths for K objects visiting intermediate nodes to set optimal paths under the assumption that we use maximal possible velocities on each arc belonging to a path for each object (solution of the NDSP problem), and next we try to decrease the values of velocities to optimize the second criterion (synchronization, solution of the MS problem). Experimental analyses of effectiveness and complexity of the algorithms are presented.     

Tight bounds for the number of edge guards for spiral polygons

In this paper we give tight lower and upper bounds for the number of edge guards required for covering spiral polygons. We have proved that [(n + 2)/5]edge guards are necessary and sufficient to cover a spiral polygon. It has been shown by Aggarwal [2] that [(n + 2)/5]diagonal guards are necessary and sufficient to cover a spiral polygon. Edge guards are more restrictive than diagonal guards. Hence the previous theorem can be got as a corollary using our theorem. The necessary condition of the edge guard problem for spiral polygons has not been investigated although the diagonal guard problem for the same has been solved [2]. The necessary proof of the edge guard problem follows from the necessary condition of the diagonal guard problem but we have given an alternate proof of necessity.     

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.     

Existence and Relaxation Theorems for Nonlinear Multivalued Boundary Value Problems

In this paper we consider a general nonlinear boundary value problem for second-order differential inclusions. We prove two existence theorems, one for the ``convex' problem and the other for the ``nonconvex' problem. Then we show that the solution set of the latter is dense in the C ¹ (T,R ^N ) -norm to the solution set of the former (relaxation theorem). Subsequently for a Dirichlet boundary value problem we prove the existence of extremal solutions and we show that they are dense in the solutions of the convexified problem for the C ¹ (T,R ^N ) -norm . Our tools come from multivalued analysis and the theory of monotone operators and our proofs are based on the Leray—Schauder principle. Accepted 18 September 1997     

Legal coloring of graphs

The following computational problem was initiated by Manber and Tompa (22nd FOCS Conference, 1981): Given a graphG=(V, E) and a real functionf:V→R which is a proposed vertex coloring. Decide whetherf is a proper vertex coloring ofG. The elementary steps are taken to be linear comparisons. Lower bounds on the complexity of this problem are derived using the chromatic polynomial ofG. It is shown how geometric parameters of a space partition associated withG influence the complexity of this problem. Existing methods for analyzing such space partitions are suggested as a powerful tool for establishing lower bounds for a variety of computational problems.     

An inverse problem of finding the time‐dependent diffusion coefficient from an integral condition

We consider the inverse problem of determining the time‐dependent diffusivity in one‐dimensional heat equation with periodic boundary conditions and nonlocal over‐specified data. The problem is highly nonlinear and it serves as a mathematical model for the technological process of external guttering applied in cleaning admixtures from silicon chips. First, the well‐posedness conditions for the existence, uniqueness, and continuous dependence upon the data of the classical solution of the problem are established. Then, the problem is discretized using the finite‐difference method and recasts as a nonlinear least‐squares minimization problem with a simple positivity lower bound on the unknown diffusivity. Numerically, this is effectively solved using the lsqnonlin routine from the MATLAB toolbox. In order to investigate the accuracy, stability, and robustness of the numerical method, results for a few test examples are presented and discussed. Copyright © 2015 John Wiley & Sons, Ltd.     

Optimally Computing the Shortest Weakly Visible Subedge of a Simple Polygon

Given ann-vertex simple polygonP, the problem of computing the shortest weakly visible subedge ofPis that of finding a shortest line segmentson the boundary ofPsuch thatPis weakly visible froms(ifsexists). In this paper, we present new geometric observations that are useful for solving this problem. Based on these geometric observations, we obtain optimal sequential and parallel algorithms for solving this problem. Our sequential algorithm runs inO(n) time, and our parallel algorithm runs inO(log n) time usingO(n/log n) processors in the CREW PRAM computational model. Using the previously best known sequential algorithms to solve this problem would takeO(n²) time. We also give geometric observations that lead to extremely simple and optimal algorithms for solving, both sequentially and in parallel, the case of this problem where the polygons are rectilinear.     

Finite-type integrable geometric structures

In this paper, we consider finite-type geometric structures of arbitrary order and solve the integrability problem for these structures. This problem is equivalent to the integrability problem for the corresponding G-structures. The latter problem is solved by constructing the structure functions for G-structures of order ≥1. These functions coincide with the well-known ones for the first-order G-structures, although their constructions are different. We prove that a finite-type G-structure is integrable if and only if the structure functions of the corresponding number of its first prolongations are equal to zero. Applications of this result to second-and third-order ordinary differential equations are noted. __________ Translated from Fundamental’naya i Prikladnaya Matematika (Fundamental and Applied Mathematics), Vol. 10, No. 1, Geometry of Integrable Models, 2004.     

On the solvability of boundary value problems for quasilinear ultraparabolic equations in some mathematical models of the dynamics of biological systems

Under consideration is the problem of modeling some population dynamics. Mathematically, it reduces to studying the solvability of a nonlocal boundary value problem for quasilinear ultraparabolic equations with astronomical time t and biological time (age) a. Some theorems of existence and uniqueness are proved for regular solutions to this problem.     

Application of a Mickens finite‐difference scheme to the cylindrical Bratu‐Gelfand problem

The boundary value problem Δu + λe^u = 0 where u = 0 on the boundary is often referred to as “the Bratu problem.” The Bratu problem with cylindrical radial operators, also known as the cylindrical Bratu‐Gelfand problem, is considered here. It is a nonlinear eigenvalue problem with two known bifurcated solutions for λ < λ_c, no solutions for λ > λ_c and a unique solution when λ = λ_c. Numerical solutions to the Bratu‐Gelfand problem at the critical value of λ_c = 2 are computed using nonstandard finite‐difference schemes known as Mickens finite differences. Comparison of numerical results obtained by solving the Bratu‐Gelfand problem using a Mickens discretization with results obtained using standard finite differences for λ < 2 are given, which illustrate the superiority of the nonstandard scheme. © 2004 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 20: 327–337, 2004     

A Transmission Problem Involving a Parameter and a Weight

In the course of developing a spectral theory for non-selfadjoint elliptic boundary problems involving an indefinite weight function, there arises a transmission problem which has not hitherto been dealt with in a L_p setting. By educing our problem to one for ordinary differential equations with the aid of the Fourier transformation, we are able to resolve the transmission problem,that is to say, we are able to establish L_p estimates for its solutions which are supported in a neighbourhood of the origin, and this is p ecisely what is required for the furthe development of the spectral theory for the boundary problems cited above.     

Multi-Duality in Minimal Surface—Type Problems

The multi-duality of the nonlinear variational problem inf J(u, Λu) is studied for minimal surfaces-type problems. By using the method developed by Gao and Strang [1], the Fenchel-Rockafellar's duality theory is generalized to the problems with affine operator Λ. Two dual variational principles are established for nonparametric surfaces with constant mean curvature. We show that for the same primal problem, there may exist different dual problems. The primal problem may or may not possess a solution, whereas each dual problem possesses a unique solution. An evolutionary method for solving the nonlinear optimal-shape design problem is presented with numerical results.