A new method of solving nonlinear mathematical programming problems involving r-invex functions

A new approach to a solution of a nonlinear constrained mathematical programming problem involving r-invex functions with respect to the same function η is introduced. An η-approximated problem associated with an original nonlinear mathematical programming problem is presented that involves η-approximated functions constituting the original problem. The equivalence between optima points for the original mathematical programming problem and its η-approximated optimization problem is established under r-invexity assumption.     

On the forbidden induced subgraph sandwich problem

We consider the sandwich problem, a generalization of the recognition problem introduced by Golumbic et al. (1995) [15], with respect to classes of graphs defined by excluding induced subgraphs. We prove that the sandwich problem corresponding to excluding a chordless cycle of fixed length k is NP-complete. We prove that the sandwich problem corresponding to excluding K_r?e for fixed r is polynomial. We prove that the sandwich problem corresponding to 3PC(⋅,⋅)-free graphs is NP-complete. These complexity results are related to the classification of a long-standing open problem: the sandwich problem corresponding to perfect graphs.     

‘Multidimensional’ extensions and a nested dual approach for the m-median problem

A general framework for modeling median type locational decisions, where (i) travel costs and demands may be stochastic, (ii) multiple services or commodities need to be considered, and/or (iii) multiple median type objectives might exist, is presented—using the concept of “multidimensional networks”. The classical m-median problem, the stochastic m-median problem, the multicommodity m-median problem and and multiobjective m-median problem are defined within this framework.By an appropriate transformation of variables, the multidimensional m-median problem simplifies to the classical m-median problem but with a K-fold increase in the number of nodes, where K is the number of dimensions of the network. A nested dual approach to solve the resulting classical m-median problem, that uses Erlenkotter's facility location scheme as a subroutine, is presented. Computational results indicate that the procedure may perhaps be the best available one to solve the m-median problem exactly.     

Minimizing mean squared deviation of completion times with maximum tardiness constraint

We consider a nonpreemptive single-machine scheduling problem to minimize mean squared deviation of job completion times about a common due date with maximum tardiness constraint (MSD/T_max problem), where the common due date is large enough so that it does not constrain the minimization of MSD.The MSD/T_max problem is classified into three cases according to the value of maximum allowable tardiness Δ: Δ-unconstrained, Δ-constrained and tightly Δ-constrained cases. It is shown that the Δ-unconstrained MSD/T_max problem is equivalent to the unconstrained MSD problem and that the tightly Δ-constrained MSD/T_max problem with common due date d is equivalent to the tightly constrained MSD problem with common due date Δ. We also provide bounds to decide when the MSD/T_max problem is Δ-unconstrained or Δ-constrained. Then a solution procedure to the MSD/T_max problem is presented with several examples.     

A note on the m-center problem with rectilinear distances

Given n demand points on a plane, the problem we consider is to locate a given number, m, of facilities on the plane so that the maximum of the set of rectilinear distances of each demand point to its nearest facility is minimized. This problem is known as the m-center problem on the plane. A related problem seeks to determine, for a given r, the minimum number of facilities and their locations so as to ensure that every point is within r units of rectilinear distance from its nearest facility. We formulate the latter problem as a problem of covering nodes by cliques of an intersection graph. Certain bounds are established on the size of the problem. An efficient algorithm is provided to generate this set-covering problem. Computational results with this approach are summarized.     

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.     

The even Orlicz Minkowski problem

The classical Minkowski problem leads to the Lp Minkowski problem and now to the Orlicz Minkowski problem. Existence is demonstrated for the even Orlicz Minkowski problem. A byproduct is a new approach to the solution of the classical Minkowski problem.     

Intersection theorems under dimension constraints

In Ahlswede et al. [Discrete Math. 273(1-3) (2003) 9-21] we posed a series of extremal (set system) problems under dimension constraints. In the present paper, we study one of them: the intersection problem. The geometrical formulation of our problem is as follows. Given integers 0?t, k?n determine or estimate the maximum number of (0,1)-vectors in a k-dimensional subspace of the Euclidean n-space Rⁿ, such that the inner product (“intersection”) of any two is at least t. Also we are interested in the restricted (or the uniform) case of the problem; namely, the problem considered for the (0,1)-vectors of the same weight ω.The paper consists of two parts, which concern similar questions but are essentially independent with respect to the methods used.In Part I, we consider the unrestricted case of the problem. Surprisingly, in this case the problem can be reduced to a weighted version of the intersection problem for systems of finite sets. A general conjecture for this problem is proved for the cases mentioned in Ahlswede et al. [Discrete Math. 273(1-3) (2003) 9-21]. We also consider a diametric problem under dimension constraint.In Part II, we study the restricted case and solve the problem for t=1 and k<2ω, and also for any fixed 1?t?ω and k large.     

A branch-and-bound method for the minimum k−enclosing ball problem

The minimum k-enclosing ball problem seeks the ball with smallest radius that contains at least k of m given points. This problem is NP-hard. We present a branch-and-bound algorithm on the tree of the subsets of k points to solve this problem. Our method is able to solve the problem exactly in a short amount of time for small and medium sized datasets.     

Clustering and domination in perfect graphs

A k-cluster in a graph is an induced subgraph on k vertices which maximizes the number of edges. Both the k-cluster problem and the k-dominating set problem are NP-complete for graphs in general. In this paper we investigate the complexity status of these problems on various sub-classes of perfect graphs. In particular, we examine comparability graphs, chordal graphs, bipartite graphs, split graphs, cographs and κ-trees. For example, it is shown that the k-cluster problem is NP-complete for both bipartite and chordal graphs and the independent k-dominating set problem is NP-complete for bipartite graphs. Furthermore, where the k-cluster problem is polynomial we study the weighted and connected versions as well. Similarly we also look at the minimum k-dominating set problem on families which have polynomial k-dominating set algorithms.     

The two-machine no-wait general and proportionate open shop makespan problem

We consider the two-machine no-wait open shop minimum makespan problem in which the determination of an optimal solution requires an optimal pairing of the jobs followed by the optimal sequencing of the job pairs. We show that the required enumeration can be curtailed by reducing the pair sequencing problem for a given pair set to a traveling salesman problem which is equivalent to a two-machine no-wait flow shop problem solvable in O(n log n) time. We then propose an optimal O(n log n) algorithm for the proportionate problem with equal machine speeds in which each job has the same processing time on both machines. We show that our O(n log n) algorithm also applies to the more general proportionate problem with equal machine speeds and machine-specific setup times. We also analyze the proportionate problem with unequal machine speeds and conclude that the required enumeration can be further curtailed (compared to the problem with arbitrary job processing times) by eliminating certain job pairs from consideration.     

Mixed equilibrium problems with Z*-bifunctions and least element problems in Banach lattices

The purpose of this paper is to study the relations among a mixed equilibrium problem, a least element problem and a minimization problem in Banach lattices. We propose the concept of Z*-bifunctions as well as the concept of a feasible set for the mixed equilibrium problem. We prove that the feasible set of the mixed equilibrium problem is a sublattice provided that the associated bifunction is a strictly α-monotone Z*-bifunction. We establish the equivalence of the mixed equilibrium problem, the least element problem and the minimization problem under strict α-monotonicity and Z*-bifunction conditions.     

Numerical solutions of the m-membranes problem

In this paper numerical approximation for the m-membrane problem is considered. We make a change of variables that leads to a different expression of the quadratic functional that allows after discretizing the problem to reformulate it as finite dimensional bound constrained quadratic problem. To our knowledge this is the first paper on numerical approximation of the m-membrane problem. We reformulate the m-membrane problem as a bound constraint quadratic minimization problem. The bound constraint quadratic form is solved with the gradient projection method.     

A uniqueness theorem in the inverse problem for the integrodifferential electrodynamics equations

Under study is the problem of finding the kernel and the index of dielectric permeability for the system of integrodifferential electrodynamics equations with wave dispersion. We consider a direct problem in which the external pulse current is a dipole located at a point y on the boundary ?B of the unit ball B. The point y runs over the whole boundary and is a parameter of the problem. The information available about the solution to the direct problem is the trace on ?B of the solution to the Cauchy problem given for the times close to the time when a wave from the dipole source arrives at a point x. The main result of the article consists in obtaining some theorems related to the uniqueness problems for a solution to the inverse problem.     

The p/q-active uncapacitated facility location problem: Investigation of the solution space and an LP-fitting heuristic

The p/q-active uncapacitated facility location problem is the problem of locating p facilities on n possible sites each serving at least q of the m clients at the minimum cost. The problem is an extension of the uncapacitated facility location problem (UFL) where constraints on the number of facilities and their minimum activity have been added. A use of this formulation could be the opening of p new schools where each must have at least q pupils. p/q-active is NP-hard like the UFL.     

R-domination on block graphs

The k-domination problem is to select a minimum cardinality vertex set D of a graph G such that every vertex of G is within distance k from some vertex of D. We consider a generalization of the k-domination problem, called the R-domination problem. A linear algorithm is presented that solves this problem for block graphs. Our algorithm is a generalization of Slater's algorithm [12], which is applicable for forest graphs.     

Inverse 1-median problem on trees under weighted Hamming distance

The inverse 1-median problem consists in modifying the weights of the customers at minimum cost such that a prespecified supplier becomes the 1-median of modified location problem. A linear time algorithm is first proposed for the inverse problem under weighted l _?? norm. Then two polynomial time algorithms with time complexities O(n log n) and O(n) are given for the problem under weighted bottleneck-Hamming distance, where n is the number of vertices. Finally, the problem under weighted sum-Hamming distance is shown to be equivalent to a 0-1 knapsack problem, and hence is ${\mathcal{NP}}$ -hard.     

Transitive algebras and reductive algebras on reproducing analytic Hilbert spaces

In this paper, we consider the well-known transitive algebra problem and reductive algebra problem on vector valued reproducing analytic Hilbert spaces. For an analytic Hilbert space H(k) with complete Nevanlinna-Pick kernel k, it is shown that both transitive algebra problem and reductive algebra problem on multiplier invariant subspaces of H(k)⊗Cm have positive answer if the algebras contain all analytic multiplication operators. This extends several known results on the problems.     

Nucleation in the FitzHugh-Nagumo system: Interface-spike solutions

We find nucleation solutions of N interfaces and K spikes to the one-dimensional FitzhHugh-Nagumo system. Each spike sits asymptotically in the middle between two interfaces. We use the Lyapunov-Schmidt reduction method, in which the problem is split into a finite-dimensional problem related to the translation of the K spikes and an infinite-dimensional complement problem. However the complement problem remains near degenerate due to the translation of the N interfaces. To overcome this difficulty we move the interfaces by a small distance and solve the complement problem with the help of a Newton iteration argument.     

On a non-homogeneous eigenvalue problem involving a potential: An Orlicz–Sobolev space setting

In this paper we study a non-homogeneous eigenvalue problem involving variable growth conditions and a potential V. The problem is analyzed in the context of Orlicz–Sobolev spaces. Connected with this problem we also study the optimization problem for the particular eigenvalue given by the infimum of the Rayleigh quotient associated to the problem with respect to the potential V when V lies in a bounded, closed and convex subset of a certain variable exponent Lebesgue space.