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

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.     

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)}\).     

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.

     

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.     

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.     

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.     

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.     

On solvability of f(p(x)) = q(f(x)) for given real functions p,q

We investigate the solvability of functional equations f(p(x)) =  q(f(x)) for given functions p and q which are partially or completely defined on the set of all real numbers. For these investigations, we use methods for constructions of homomorphisms of mono-unary algebras. We can present a simple characterisation of solvability of the above equation in the case that p, q are strictly increasing and continuous functions. It gives, on the one hand, a practical use for a class of functional equations. On the other hand, it is a contribution to questions on topological conjugacy of monotonous real functions.     

Universal rigidity of bar frameworks via the geometry of spectrahedra

A bar framework (G, p) in dimension r is a graph G whose nodes are points \(p^1,\ldots ,p^n\) in \(\mathbb {R}^r\) and whose edges are line segments between pairs of these points. Two frameworks (G, p) and (G, q) are equivalent if each edge of (G, p) has the same (Euclidean) length as the corresponding edge of (G, q). A pair of non-adjacent vertices i and j of (G, p) is universally linked if \(||p^i-p^j||\) = \(||q^i-q^j||\) in every framework (G, q) that is equivalent to (G, p). Framework (G, p) is universally rigid iff every pair of non-adjacent vertices of (G, p) is universally linked. In this paper, we present a unified treatment of the universal rigidity problem based on the geometry of spectrahedra. A spectrahedron is the intersection of the positive semidefinite cone with an affine space. This treatment makes it possible to tie together some known, yet scattered, results and to derive new ones. Among the new results presented in this paper are: (1) The first sufficient condition for a given pair of non-adjacent vertices of (G, p) to be universally linked. (2) A new, weaker, sufficient condition for a framework (G, p) to be universally rigid thus strengthening the existing known condition. An interpretation of this new condition in terms of the Strong Arnold Property is also presented.     

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.     

Minimal Translation Hypersurfaces in Euclidean Space

The graph of a function f defined in some open set of the Euclidean space of dimension (p + q) is said to be a translation graph if f may be expressed as the sum of two independent functions ? and ψ defined in open sets of the Euclidean spaces of dimension p and q, respectively. We obtain a useful expression for the mean curvature of the graph of f in terms of the Laplacian, the gradient of ? and ψ as well as of the mean curvatures of their graphs. We study translation graphs having zero mean curvature, that is, minimal translation graphs, by imposing natural conditions on ? and ψ, like harmonicity, minimality and eikonality (constant norm of the gradient), giving several examples as well as characterization results.     

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.