The connected <Emphasis Type="Italic">p</Emphasis>-median problem on block graphs

In this paper, we study a variant of the p-median problem on block graphs G in which the p-median is asked to be connected, and this problem is called the connected p-median problem. We first show that the connected p-median problem is NP-hard on block graphs with multiple edge weights. Then, we propose an O(n)-time algorithm for solving the problem on unit-edge-weighted block graphs, where n is the number of vertices in G.     

A new heuristic approach for the P-median problem

The Euclidean p-median problem is concerned with the decision of the locations for public service centres. Existing methods for the planar Euclidean p-median problems are capable of efficiently solving problems of relatively small scale. This paper proposes two new heuristic algorithms aiming at problems of large scale. Firstly, to reflect the different degrees of proximity to optimality, a new kind of local optimum called level-m optimum is defined. For a level-m optimum of a p-median problem, where m<p, each of its subsets containing m of the p partitions is a global optimum of the corresponding m-median subproblem. Starting from a conventional local optimum, the first new algorithm efficiently improves it to a level-2 optimum by applying an existing exact algorithm for solving the 2-median problem. The second new algorithm further improves it to a level-3 optimum by applying a new exact algorithm for solving the 3-median problem. Comparison based on experimental results confirms that the proposed algorithms are superior to the existing heuristics, especially in terms of solution quality.     

A Lagrangian search method for the <Emphasis Type="Italic">P</Emphasis>-median problem

In this paper, we propose a novel algorithm for solving the classical P-median problem. The essential aim is to identify the optimal extended Lagrangian multipliers corresponding to the optimal solution of the underlying problem. For this, we first explore the structure of the data matrix in P-median problem to recast it as another equivalent global optimization problem over the space of the extended Lagrangian multipliers. Then we present a stochastic search algorithm to find the extended Lagrangian multipliers corresponding to the optimal solution of the original P-median problem. Numerical experiments illustrate that the proposed algorithm can effectively find a global optimal or very good suboptimal solution to the underlying P-median problem, especially for the computationally challenging subclass of P-median problems with a large gap between the optimal solution of the original problem and that of its Lagrangian relaxation.     

Heuristic Solution Methods for Two Location Problems with Unreliable Facilities

In this paper, the p-median and p-centre problems are generalized by considering the possibility that one or more of the facilities may become inactive. The unreliable p-median problem is defined by introducing the probability that a facility becomes inactive. The (p, q)-centre problem is defined when p facilities need to be located but up to q of them may become unavailable at the same time. An heuristic procedure is presented for each problem. A rigorous procedure is discussed for the (p, q)-centre problem. Computational results are presented.     

<Emphasis Type="Italic">p</Emphasis>-Medians and Multi-Medians

The classical p-median problem is discussed, together with methods for its solution. The multi-median problem, a generalization of the p-median problem in which more than one type of facility is allowed, is introduced and methods of solution developed. Numerical results are presented.     

Hilbert boundary value problem in the weighted spaces <Emphasis Type="Italic">L</Emphasis><Superscript>1</Superscript>(<Emphasis Type="Italic">ρ</Emphasis>)

The paper studies a Hilbert boundary value problem in L ¹(ρ), where ρ(t) = |1–t|^α and α is a real number. For α > ?1, it is proved that the homogeneous problem has n + κ linearly independent solutions when n + κ ≥ 0, where a(t) is the coefficient of the problem, besides, κ ind a(t) and n = [α] + 1 if α is not an integer, and n = α if α is an integer. Conditions under which the problem is solvable are found for the case when α > ?1 and n+κ < 0. For α ≤ ?1 the number of linearly independent solutions of the homogeneous problem depends on the behavior of the function a(t) at the point t = 1.     

On Trees of Bounded Degree with Maximal Number of Greatest Independent Sets

Given n and d, we describe the structure of trees with the maximal possible number of greatest independent sets in the class of n-vertex trees of vertex degree at most d.We show that the extremal tree is unique for all even n but uniqueness may fail for odd n; moreover, for d = 3 and every odd n ≥ 7, there are exactly ?(n ? 3)/4? + 1 extremal trees. In the paper, the problem of searching for extremal (n, d)-trees is also considered for the 2-caterpillars; i.e., the trees in which every vertex lies at distance at most 2 from some simple path. Given n and d ∈ {3, 4}, we completely reveal all extremal 2-caterpillars on n vertices each of which has degree at most d.     

A variation of a conjecture due to Erdös and Sós

Erdoes and Soes conjectured in 1963 that every graph G on n vertices with edge number e（G） 〉 1/2（k - 1）n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n 〉 9/ 2k^2 ＋ 37/2＋ 14 and every graph G on n vertices with e（G） 〉 1/2 （k- 1）n, we prove that there exists a graph G＇ on n vertices having the same degree sequence as G and containing every tree T with k edges as a subgraph.     

Radar placement along banks of river

In this paper, we consider the Radar Placement and Power Assignment problem (RPPA) along a river. In this problem, a set of crucial points in the river are required to be monitored by a set of radars which are placed along the two banks. The goal is to choose the locations for the radars and assign powers to them such that all the crucial points are monitored and the total power is minimized. If each crucial point is required to be monitored by at least k radars, the problem is a k-Coverage RPPA problem (k-CRPPA). Under the assumption that the river is sufficiently smooth, one may focus on the RPPA problem along a strip (RPPAS). In this paper, we present an O(n ⁹) dynamic programming algorithm for the RPPAS, where n is the number of crucial points to be monitored. In the special case where radars are placed only along the upper bank, we present an O(kn ⁵) dynamic programming algorithm for the k-CRPPAS. For the special case that the power is linearly dependent on the radius, we present an O(n log n)-time \({2\sqrt 2}\)-approximation algorithm for the RPPAS.     

On the complexity of inverse convex ordered 1-median problem on the plane and on tree networks

An ordered median function is used in location theory to generalize a class of problems, including median and center problems. In this paper we consider the complexity of inverse ordered 1-median problems on the plane and on trees, where the multipliers are sorted nondecreasingly. Based on the convexity of the objective function, we prove that the problems with variable weights or variable coordinates on the line are NP-hard. Then we can directly get the NP-hardness result for the corresponding problem on the plane. We finally develop a cubic time algorithm that solves the inverse convex ordered 1-median problem on trees with relaxation on modification bounds.     

A note on the cubical dimension of new classes of binary trees

The cubical dimension of a graph G is the smallest dimension of a hypercube into which G is embeddable as a subgraph. The conjecture of Havel (1984) claims that the cubical dimension of every balanced binary tree with 2 ⁿ vertices, n ? 1, is n. The 2-rooted complete binary tree of depth n is obtained from two copies of the complete binary tree of depth n by adding an edge linking their respective roots. In this paper, we determine the cubical dimension of trees obtained by subdividing twice a 2-rooted complete binary tree and prove that every such balanced tree satisfies the conjecture of Havel.     

An algorithm to compute <Emphasis Type="Italic">ω</Emphasis>-primality in a numerical monoid

Let M be a commutative, cancellative, atomic monoid and x a nonunit in M. We define ω(x)=n if n is the smallest positive integer with the property that whenever x∣a ₁???a _t , where each a _i is an atom, there is a T?{1,2,…,t} with |T|≤n such that x∣∏_k∈T a _k . The ω-function measures how far x is from being prime in M. In this paper, we give an algorithm for computing ω(x) in any numerical monoid. Simple formulas for ω(x) are given for numerical monoids of the form 〈n,n+1,…,2n?1〉, where n≥3, and 〈n,n+1,…,2n?2〉, where n≥4. The paper then focuses on the special case of 2-generator numerical monoids. We give a formula for computing ω(x) in this case and also necessary and sufficient conditions for determining when x is an atom. Finally, we analyze the asymptotic behavior of ω(x) by computing \(\lim_{x\rightarrow \infty}\frac{\omega(x)}{x}\).     

An Optimal Algorithm for the <Emphasis Type="Italic">k</Emphasis>-Fixed-Endpoint Path Cover on Proper Interval Graphs

In this paper we consider the k-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a graph G and a set T of k vertices, a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint simple paths that covers the vertices of G, such that the vertices of T are all endpoints of these paths. The goal is to compute a k-fixed-endpoint path cover of G with minimum cardinality. We propose an optimal algorithm for this problem with runtime O(n), where n is the number of intervals in G. This algorithm is based on the Stair Normal Interval Representation (SNIR) matrix that characterizes proper interval graphs. In this characterization, every maximal clique of the graph is represented by one matrix element; the proposed algorithm uses this structural property, in order to determine directly the paths in an optimal solution.     

Contribution to the General Linear Conjugation Problem for A Piecewise Analytic Vector

Establishing an analogy between the theories of Riemann–Hilbert vector problem and linear ODEs, for the n-dimensional homogeneous linear conjugation problem on a simple smooth closed contour Γ partitioning the complex plane into two domains D⁺ and D^? we show that if we know n?1 particular solutions such that the determinant of the size n?1 matrix of their components omitting those with index k is nonvanishing on D⁺ ∪ Γ and the determinant of the matrix of their components omitting those with index j is nonvanishing on Γ ∪ D^? {∞}, where \(k,j = \overline {1,n} \), then the canonical system of solutions to the linear conjugation problem can be constructed in closed form.     

Simplexes in a normed space

Is it true that any set of n + 1 points in Rⁿ can be isometrically embedded into any n-dimensional real normed apace? For n ≥ 3, the answer to this question is unknown to the author of this paper. For n = 2, it is clear that the answer is positive. For n = 3, the problem is reduced to the case where four points lie in a plane. A certain reduction is assigned for arbitrary n.     

A Polynomial Time Algorithm for the Resource Allocation Problem with a Convex Objective Function

Consider the resource allocation problem:minimize ∑ⁿ_i=1 f_i(x_i) subject to ∑ⁿ_i=1 x_i = N and x_i's being nonnegative integers, where each f_i is a convex function. The well-known algorithm based on the incremental method requires O(N log n + n) time to solve this problem. We propose here a new algorithm based on the Lagrange multiplier method, requiring O[n²(log N)²] time. The latter is faster if N is much larger than n. Such a situation occurs, for example, when the optimal sample size problem related to monitoring the urban air pollution is treated.     

On the Completeness of Products of Harmonic Functions and the Uniqueness of the Solution of the Inverse Acoustic Sounding Problem

It is proved that the family of all pairwise products of regular harmonic functions on D and of the Newtonian potentials of points on the line L ? Rⁿ is complete in L₂(D), where D is a bounded domain in Rⁿ, n ≥ 3, such that \(\bar D\) ∩ L = ?. This result is used in the proof of uniqueness theorems for the inverse acoustic sounding problem in R³.     

Solution of the NP-hard total tardiness minimization problem in scheduling theory

The classical NP-hard (in the ordinary sense) problem of scheduling jobs in order to minimize the total tardiness for a single machine 1‖ΣT _j is considered. An NP-hard instance of the problem is completely analyzed. A procedure for partitioning the initial set of jobs into subsets is proposed. Algorithms are constructed for finding an optimal schedule depending on the number of subsets. The complexity of the algorithms is O(n ²Σp _j ), where n is the number of jobs and p _j is the processing time of the jth job (j = 1, 2, …, n).     

Medi-centre Location Problems

In this paper we consider two medi-centre location problems. One is the m-medi-centre problem in which we add to the m-median problem uniform distance constraints. The other problem is the uncapacitated medi-centre facility location problem where we include the fixed costs of establishing the facilities and thus the number of facilities is also a decision variable. For the two problems we present algorithms and discuss computational experience.     

On Modular Edge-Graceful Graphs

Let G be a connected graph of order \({n\ge 3}\) and size m and \({f:E(G)\to \mathbb{Z}_n}\) an edge labeling of G. Define a vertex labeling \({f': V(G)\to \mathbb{Z}_n}\) by \({f'(v)= \sum_{u\in N(v)}f(uv)}\) where the sum is computed in \({\mathbb{Z}_n}\) . If f′ is one-to-one, then f is called a modular edge-graceful labeling and G is a modular edge-graceful graph. A graph G is modular edge-graceful if G contains a modular edge-graceful spanning tree. Several classes of modular edge-graceful trees are determined. For a tree T of order n where \({n\not\equiv 2 \pmod 4}\) , it is shown that if T contains at most two even vertices or the set of even vertices of T induces a path, then T is modular edge-graceful. It is also shown that every tree of order n where \({n\not\equiv 2\pmod 4}\) having diameter at most 5 is modular edge-graceful.