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.     

Simulated annealing and tabu search approaches for the Corridor Allocation Problem

In the Corridor Allocation Problem, we are given n facilities to be arranged along a corridor. The arrangements on either side of the corridor should start from a common point on the left end of the corridor. In addition, no space is allowed between two adjacent facilities. The problem is motivated by applications such as the arrangement of rooms in office buildings, hospitals, shopping centers or schools. Tabu search and simulated annealing algorithms are presented to minimize the sum of weighted distances between every pair of facilities. The algorithms are evaluated on several instances of different sizes either randomly generated or available in the literature. Both algorithms reached the optimal (when available) or best-known solutions of the instances with n ? 30. For larger instances with size 42 ? n ? 70, the simulated annealing implementation obtained smaller objective values, while requiring a smaller number of function evaluations.     

Optimal algorithms for the α-neighbor p-center problem

Assigning multiple service facilities to demand points is important when demand points are required to withstand service facility failures. Such failures may result from a multitude of causes, ranging from technical difficulties to natural disasters. The α-neighbor p-center problem deals with locating p service facilities. Each demand point is assigned to its nearest α service facilities, thus it is able to withstand up to α − 1 service facility failures. The objective is to minimize the maximum distance between a demand point and its αth nearest service facility. We present two optimal algorithms for both the continuous and discrete α-neighbor p-center problem. We present experimental results comparing the performance of the two optimal algorithms for α = 2. We also present experimental results showing the performance of the relaxation algorithm for α = 1, 2, 3.     

Haplotyping populations by pure parsimony based on compatible genotypes and greedy heuristics

The population haplotype inference problem based on the pure parsimony criterion (HIPP) infers an m × n genotype matrix for a population by a 2m × n haplotype matrix with the minimum number of distinct haplotypes. Previous integer programming based HIPP solution methods are time-consuming, and their practical effectiveness remains unevaluated. On the other hand, previous heuristic HIPP algorithms are efficient, but their theoretical effectiveness in terms of optimality gaps has not been evaluated, either. We propose two new heuristic HIPP algorithms (MGP and GHI) and conduct more complete computational experiments. In particular, MGP exploits the compatible relations among genotypes to solve a reduced integer linear programming problem so that a solution of good quality can be obtained very quickly; GHI exploits a weight mechanism to selects better candidate haplotypes in a greedy fashion. The computational results show that our proposed algorithms are efficient and effective, especially for solving cases with larger recombination rates.     

Lower bounds of Copson type for Hausdorff matrices

Let 1 ? p ? ∞, 0 < q ? p, and A = (a_n,k)_n,k?0 ? 0. Denote by L_p,q(A) the supremum of those L satisfying the following inequality:

     

A new comparison theorem on conditional quantiles

This paper studies the conditional quantile regression problem involving the pinball loss. We introduce a concept of τ-quantile of p-average logarithmic type q to complement the previous study by Steinwart and Christman (2008, 2011) [1] and [2]. A new comparison theorem is provided which can be used for further error analysis of some learning algorithms.     

A note on the Estrada-Hatano communicability algorithm for detecting community structure in complex networks

Recently Estrada and Hatano proposed an algorithm for the detection of community structure in complex networks using the concept of network communicability. Here we amend this algorithm by eliminating the subjectivity of choosing degree of overlapping and including an additional check of the fitness of detected communities. We show that this amendment can detect some communities which remain undetected by Estrada and Hatano’s algorithm. For instance, let G(p, q) be a graph obtained from two cliques, K_p and K_q(p ? q ? 3), joined by a single edge. It is apparent that this graph contains two communities, namely the two cliques. However, Estrada and Hatano’s algorithm detects only K_q as a community when p is sufficiently larger than q. Our algorithm correctly detects both communities. Also, our method also finds the correct community structure in one of the classic benchmark networks, the Zachary karate club.     

Nordsieck methods with computationally verified algebraic stability

We describe the search for algebraically stable Nordsieck methods of order p = s and stage order q = p, where s is the number of stages. This search is based on the theoretical criteria for algebraic stability proposed recently by Hill, and Hewitt and Hill, for general linear methods for ordinary differential equations. These criteria, which are expressed in terms of the non-negativity of the eigenvalues of a Hermitian matrix on the unit circle, are then verified computationally for the derived Nordsieck methods of order p ? 2.     

New ideas for decomposing nonlinearities in differential equations

In this paper we consider the decomposition for the nonlinearity in a differential equation for the solution by decomposition. By analyzing and transforming the Taylor expansion of the nonlinearity about the initial solution component, the decomposition of the nonlinearity is converted to the partitions of the solution sets for a class of Diophantine equations. This conversion simplifies the discussion and presents a new idea for decompositions. We enumerate five types of partitions and their corresponding decomposition polynomials. Each of the last four types contains infinitely many kinds of decomposition polynomials in the form of finite sums. In Types 2, 3 and 4, there is a parameter q and each value of q corresponds to a class of decomposition polynomials. In Type 5, each positive integer sequence {c_j} satisfying 1 = c₁ ? c₂ ? ? and j ? c_j for j = 2, 3, … corresponds to a class of decomposition polynomials. Four classes of the Adomian polynomials [R. Rach, A new definition of the Adomian polynomials, Kybernetes 37 (2008) 910-955] are derived as particular cases.     

Finite projective planes admitting a projective linear group PSL (2, q)

Let S be a projective plane, and let G?Aut(S) and PSL(2, q) ? G ? PΓL(2, q) with q > 3. If G acts point-transitively on S, then q = 7 and S is of order 2.     

Symmetry transformations for square sliced three-way arrays, with applications to their typical rank

The typical 3-tensorial rank has been much studied over algebraically closed fields, but very little has been achieved in the way of results pertaining to the real field. The present paper examines the typical 3-tensorial rank over the real field, when the slices of the array involved are square matrices. The typical rank of 3 × 3 × 3 arrays is shown to be five. The typical rank of p × q × q arrays is shown to be larger than q + 1 unless there are only two slices (p = 2), or there are three slices of order 2 × 2 (p = 3 and q = 2). The key result is that when the rank is q + 1, there usually exists a rank-preserving transformation of the array to one with symmetric slices.     

Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan

This study addresses a single machine scheduling problem with periodic maintenance, where the machine is assumed to be stopped periodically for maintenance for a constant time w during the scheduling period. Meanwhile, the maintenance period [u, v] is assumed to have been previously arranged and the time w is assumed not to exceed the available maintenance period [u, v] (i.e. w ? v − u). The time u(v) is the earliest (latest) time at which the machine starts (stops) its maintenance. The objective is to minimize the makespan. Two mixed binary integer programming (BIP) models are provided for deriving the optimal solution. Additionally, an efficient heuristic is proposed for finding the near-optimal solution for large-sized problems. Finally, computational results are provided to demonstrate the efficiency of the models and the effectiveness of the heuristics. The mixed BIP model can optimally solve up to 100-job instances, while the average percentage error of the heuristic is below 1%.     

Economical tight examples for the biased Erd?s-Selfridge theorem

A positional game is essentially a generalization of tic-tac-toe played on a hypergraph (V,F). A pivotal result in the study of positional games is the Erd?s-Selfridge theorem, which gives simple criteria for the existence of a Breaker's winning strategy on a hypergraph F. It has been shown that the Erd?s-Selfridge theorem can be tight and that numerous extremal systems exist for that theorem. We focus on a generalization of the Erd?s-Selfridge theorem proven by Beck for biased (p:q) games, which we call the (p:q)-Erd?s-Selfridge theorem. We show that for pn-uniform hypergraphs there is a unique extremal system for the (p:q)-Erd?s-Selfridge theorem (q?2) when Maker must win in exactly n turns (i.e., as quickly as possible).     

Batch delivery scheduling with batch delivery cost on a single machine

We consider a scheduling problem in which n independent and simultaneously available jobs are to be processed on a single machine. The jobs are delivered in batches and the delivery date of a batch equals the completion time of the last job in the batch. The delivery cost depends on the number of deliveries. The objective is to minimize the sum of the total weighted flow time and delivery cost. We first show that the problem is strongly NP-hard. Then we show that, if the number of batches is B, the problem remains strongly NP-hard when B ? U for a variable U ? 2 or B ? U for any constant U ? 2. For the case of B ? U, we present a dynamic programming algorithm that runs in pseudo-polynomial time for any constant U ? 2. Furthermore, optimal algorithms are provided for two special cases: (i) jobs have a linear precedence constraint, and (ii) jobs satisfy the agreeable ratio assumption, which is valid, for example, when all the weights or all the processing times are equal.     

Moore–Penrose invertibility of differences and products of projections in rings with involution

This article concerns the MP inverse of the differences and the products of projections in a ring R   with involution. Some equivalent conditions are obtained. As applications, the MP invertibility of the commutator pq−qp$pq-qp$ and the anti-commutator pq+qp$pq+qp$ are characterized, where p and q are projections in R  . Some related known results in C^?$C^{?}$-algebra are generalized.     

Exact and approximation algorithms for the min–max k-traveling salesmen problem on a tree

Given k identical salesmen, where k ? 2 is a constant independent of the input size, the min–max k-traveling salesmen problem on a tree is to determine a set of k tours for the salesmen to serve all customers that are located on a tree-shaped network, so that each tour starts from and returns to the root of the tree with the maximum total edge weight of the tours minimized. The problem is known to be NP-hard even when k = 2. In this paper, we have developed a pseudo-polynomial time exact algorithm for this problem with any constant k ? 2, closing a question that has remained open for a decade. Along with this, we have further developed a (1 + ?)-approximation algorithm for any ? > 0.     

Approximability of single machine scheduling with fixed jobs to minimize total completion time

We consider the single machine scheduling problem to minimize total completion time with fixed jobs, precedence constraints and release dates. There are some jobs that are already fixed in the schedule. The remaining jobs are free to be assigned to any free-time intervals on the machine in such a way that they do not overlap with the fixed jobs. Each free job has a release date, and the order of processing the free jobs is restricted by the given precedence constraints. The objective is to minimize the total completion time. This problem is strongly NP-hard. Approximability of this problem is studied in this paper. When the jobs are processed without preemption, we show that the problem has a linear-time n-approximation algorithm, but no pseudopolynomial-time (1 − δ)n-approximation algorithm exists even if all the release dates are zero, for any constant δ > 0, if P ≠ NP, where n is the number of jobs; for the case that the jobs have no precedence constraints and no release dates, we show that the problem has no pseudopolynomial-time (2 − δ)-approximation algorithm, for any constant δ > 0, if P ≠ NP, and for the weighted version, we show that the problem has no polynomial-time 2^q(n)-approximation algorithm and no pseudopolynomial-time q(n)-approximation algorithm, where q(n) is any given polynomial of n. When preemption is allowed, we show that the problem with independent jobs can be solved in O(n log n) time with distinct release dates, but the weighted version is strongly NP-hard even with no release dates; the problems with weighted independent jobs or with jobs under precedence constraints are shown having polynomial-time n-approximation algorithms. We also establish the relationship of the approximability between the fixed job scheduling problem and the bin-packing problem.     

The generating function of a family of the sequences in terms of the continuant

Let a₀, a₁, … , a_r−1 be positive numbers and define a sequence {q_m}, with initial conditions q₀ = 0 and q₁ = 1, and for all m ? 2, q_m = a_tq_m−1 + q_m−2 where m ≡ t(mod r). For r = 2, the author called the sequence {q_m} as the generalized Fibonacci sequences and studied it in [1]. But, it remains open to find a closed form of the generating function for general {q_m}. In this paper, we solve this open problem, that is, we find a closed form of the generating function for {q_m}in terms of the continuant.     

Norm statistics and the complexity of clustering problems

In this paper we introduce a new class of clustering problems. These are similar to certain classical problems but involve a novel combination of ?_p-statistics and ?_q norms. We discuss a real world application in which the case p=2 and q=1 arises in a natural way. We show that, even for one dimension, such problems are NP-hard, which is surprising because the same 1-dimensional problems for the ‘pure’ ?₂-statistic and ?₂ norm are known to satisfy a ‘string property’ and can be solved in polynomial time. We generalize the string property for the case p=q. The string property need not hold when q≤p−1 and we show that instances may be constructed, for which the best solution satisfying the string property does arbitrarily poorly. We state some open problems and conjectures.