The <Emphasis Type="Italic">p</Emphasis>-Centre Problem—Heuristic and Optimal Algorithms

The p-centre problem, or minimax location-allocation problem in location theory terminology, is the following: given n demand points on the plane and a weight associated with each demand point, find p new facilities on the plane that minimize the maximum weighted Euclidean distance between each demand point and its closest new facility. We present two heuristics and an optimal algorithm that solves the problem for a given p in time polynomial in n. Computational results are presented.     

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.     

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.     

<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.     

The pos/neg-weighted 2-medians in balanced trees with subtree-shaped customers

This paper deals with the pos/neg-weighted p-median problem on tree graphs where all customers are modeled as subtrees. We present a polynomial algorithm for the 2-median problem on an arbitrary tree. Then we improve the time complexity to O(n log n) for the problem on a balanced tree, where n is the number of the vertices in the tree.     

Seifert manifolds and (1, 1)-knots

The aim of this paper is to investigate the relations between Seifert manifolds and (1, 1)-knots. In particular, we prove that each orientable Seifert manifold with invariants

$\{ Oo,0| - 1;\underbrace {(p,q),...,(p,q)}_{n times},(l,l - 1)\} $

has the fundamental group cyclically presented by G _n ((x ₁ ^q ...x _n ^{q l} x _n ^?p ) and, moreover, it is the n-fold strongly-cyclic covering of the lens space L(|nlq ? p|, q) which is branched over the (1, 1)-knot K(q, q(nl ? 2), p ? 2q, p ? q) if p ≥ 2q and over the (1, 1)-knot K(p? q, 2q ? p, q(nl ? 2), p ? q) if p< 2q.

     

Improved bounds on the Hadwiger–Debrunner numbers

Let HD _d (p, q) denote the minimal size of a transversal that can always be guaranteed for a family of compact convex sets in Rd which satisfy the (p, q)-property (p ≥ q ≥ d + 1). In a celebrated proof of the Hadwiger–Debrunner conjecture, Alon and Kleitman proved that HD _d (p, q) exists for all p ≥ q ≥ d + 1. Specifically, they prove that \(H{D_d}(p,d + 1)is\tilde O({p^{{d^2} + d}})\).We present several improved bounds: (i) For any \(q \geqslant d + 1,H{D_d}(p,d) = \tilde O({p^{d(\frac{{q - 1}}{{q - d}})}})\). (ii) For q ≥ log p, \(H{D_d}(p,q) = \tilde O(p + {(p/q)^d})\). (iii) For every ? > 0 there exists a p₀ = p₀(?) such that for every p ≥ p₀ and for every \(q \geqslant {p^{\frac{{d - 1}}{d} + \in }}\) we have p ? q + 1 ≤ HD _d (p, q) ≤ p ? q + 2. The latter is the first near tight estimate of HD _d (p, q) for an extended range of values of (p, q) since the 1957 Hadwiger–Debrunner theorem.We also prove a (p, 2)-theorem for families in R² with union complexity below a specific quadratic bound.     

Blow-up of <Emphasis Type="Italic">p</Emphasis>-Laplacian evolution equations with variable source power

We study the blow-up and/or global existence of the following p-Laplacian evolution equation with variable source power

$${s_j} = {\beta _j} + \overline {{\beta _{n - j}}}p$$

where Ω is either a bounded domain or the whole space ? ^N , q(x) is a positive and continuous function defined in Ω with 0 < q _? = inf q(x) ? q(x) ? sup q(x) = q+ < ∞. It is demonstrated that the equation with variable source power has much richer dynamics with interesting phenomena which depends on the interplay of q(x) and the structure of spatial domain Ω, compared with the case of constant source power. For the case that Ω is a bounded domain, the exponent p ? 1 plays a crucial role. If q+ > p ? 1, there exist blow-up solutions, while if q ₊ < p ? 1, all the solutions are global. If q _? > p ? 1, there exist global solutions, while for given q _? < p ? 1 < q ₊, there exist some function q(x) and Ω such that all nontrivial solutions will blow up, which is called the Fujita phenomenon. For the case Ω = ? ^N , the Fujita phenomenon occurs if 1 < q _? ? q ₊ ? p ? 1 + p/N, while if q _? > p ? 1 + p/N, there exist global solutions.

     

Set-theoretic complete intersection monomial curves in $${\mathbb{P}^n}$$

In this paper, we give a sufficient numerical criterion for a monomial curve in a projective space to be a set-theoretic complete intersection. Our main result generalizes a similar statement proven by Keum for monomial curves in three-dimensional projective space. We also prove that there are infinitely many set-theoretic complete intersection monomial curves in the projective n?space for any suitably chosen n ? 1 integers. In particular, for any positive integers p, q, where gcd(p, q) = 1, the monomial curve defined by p, q, r is a set-theoretic complete intersection for every \({r \geq pq( q - 1)}\).     

Iterated local search with Trellis-neighborhood for the partial Latin square extension problem

A partial Latin square (PLS) is a partial assignment of n symbols to an \(n\times n\) grid such that, in each row and in each column, each symbol appears at most once. The PLS extension problem is an NP-hard problem that asks for a largest extension of a given PLS. We consider the local search such that the neighborhood is defined by (p, q)-swap , i.e., the operation of dropping exactly p symbols and then assigning symbols to at most q empty cells. As a fundamental result, we provide an efficient \((p,\infty )\)-neighborhood search algorithm that finds an improved solution or concludes that no such solution exists for \(p\in \{1,2,3\}\). The running time of the algorithm is \(O(n^{p+1})\). We then propose a novel swap operation, Trellis-swap, which is a generalization of (p, q)-swap with \(p\le 2\). The proposed Trellis-neighborhood search algorithm runs in \(O(n^{3.5})\) time. The iterated local search (ILS) algorithm with Trellis-neighborhood is more likely to deliver a high-quality solution than not only ILSs with \((p,\infty )\)-neighborhood but also state-of-the-art optimization solvers such as IBM ILOG CPLEX and LocalSolver.     

Exact Solutions of a Second-Order Nonlinear Partial Differential Equation

The equation ?²u/?t?x + u^p?u/?x = u^q describing a nonstationary process in semiconductors, with parameters p and q that are a nonnegative integer and a positive integer, respectively, and satisfy p + q ≥ 2, is considered in the half-plane (x, t) ∈ ? × (0,∞). All in all, fourteen families of its exact solutions are constructed for various parameter values, and qualitative properties of these solutions are noted. One of these families is defined for all parameter values indicated above.     

Constructive heuristics for the uncapacitated continuous location-allocation problem

The multisource location-allocation problem in continuous space is investigated. Two constructive heuristic techniques are proposed to solve this problem. Both methods are based on designing suitable schemes for the generation of the initial solutions. The first considers the furthest distance rule and is enhanced by schemes borrowed from tabu search such as constructing the forbidden regions and freeing strategy. The second considers the discrete solutions found when solving the p-median problem. Some results on existing test problems are presented.     

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.     

On recognizability of some finite simple orthogonal groups by spectrum

It is proved that, if G is a finite group that has the same set of element orders as the simple group D _p (q), where p is prime, p ≥ 5 and q ∈ {2, 3, 5}, then the commutator group of G/F(G) is isomorphic to D _p (q), the subgroup F(G) is equal to 1 for q = 5 and to O _q (G) for q ∈ {2, 3}, F(G) ≤ G′, and |G/G′| ≤ 2.     

On the geometric mean operator with variable limits of integration

A new criterion for the weighted L _p ?L _q boundedness of the Hardy operator with two variable limits of integration is obtained for 0 < q < q + 1 ≤ p < ∞. This criterion is applied to the characterization of the weighted L _p ?L _q boundedness of the corresponding geometric mean operator for 0 < q < p < ∞.     

An Algorithm for Solving Capacitated Multicommodity <Emphasis Type="Italic">p</Emphasis>-median Transportation Problems

An algorithm for solving a special capacitated multicommodity p-median transportation problem (CMPMTP), which arises in container terminal management, is presented. There are some algorithms to solve similar kinds of problems. The formulation here is different from the existing modelling of the p-median or some related location problems. We extend the existing work by applying a Lagrangean relaxation to the CMPMTP. In order to obtain a satisfactory solution, a heuristic branch-and-bound algorithm is designed to search for a better solution, if one is possible. A comparison is also made with different algorithms.     

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 blow-up regimes in one nonlinear parabolic equation

A nonlinear heat equation with a special source on a straight line is considered. The family of exact solutions to this equation that have the form p(t) + q(t)cosx/√2, where functions p(t) and q(t) satisfy a certain dynamic system, is constructed. The system is comprehensively analyzed, and the behavior of p(t) and q(t) depending on initial data is revealed. It is found that some of the unbounded solutions from the aforementioned family are close, in a certain sense, to an analytical solution to the heat equation with power nonlinearities. The Cauchy problem for the equations considered is studied as well. It is proved that, depending on the initial solution function, solutions may develop in a blow-up regime or decay.