Fast heuristics for protection networks for dynamic routing

Traffic volatility and network reliability are important issues in the provision of high speed network services. We consider the construction of a second network, the protection network which can carry overload traffic due to the failure or congestion of any two links in the original network. The level of protection against such contingencies can be specified by a traffic requirement matrix. We construct a fully connected protection network, for an n node network, using an O(n²) heuristic based on the largest two traffic requirements for each node. This procedure is then modified to generate a more effective O(n⁴) heuristic, both methods facilitate fast processing for two-hop dynamic routing. We compare the performance of the heuristics with the O(n¹⁵) optimal solution.     

An Optimal Heuristic For Coordinated Multi-Item Inventory Replenishments

The inventory control problem can be vastly simplified if the replenishments of inventory items are coordinated with one another. That is, whenever an item is replenished, n other items, where n is a decision variable, are also replenished. One way to ensure this would be to classify the inventory items into several groups with a common order interval for each group. In this paper we establish that the optimal groups will be consecutive by hD/A, where h, D and A are the holding cost, demand rate and set-up cost of an item respectively. Using this property of consecutiveness, we develop a fast converging heuristic to create m groups optimally, m = 2, 3,..., M. The heuristic is a substitute for the dynamic programme which would otherwise be necessary and it has the potential for nomographic applications.     

Calculating the Number of Functions with a Given Endomorphism

An iterative procedure is proposed for calculating the number of k-valued functions of n variables such that each one has an endomorphism different from any constant and permutation. Based on this procedure, formulas are found for the number of three-valued functions of n variables such that each one has nontrivial endomorphisms. For any arbitrary semigroup of endomorphisms, the power is found of the set of all three-valued functions of n variables such that each one has endomorphisms from a specified semigroup.     

Two new heuristics for the <Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/<Emphasis Type="Italic">n</Emphasis>/0 queueing loss system with examples based on the two-phase Coxian distribution

In this paper, we introduce a new heuristic approach for the numerical analysis of queueing systems. In particular, we study the general, multi-server queueing loss system, the GI/G/n/0 queue, with an emphasis on the calculation of steady-state loss probabilities. Two new heuristics are developed, called the GM Heuristic and the MG Heuristic, both of which make use of an exact analysis of the corresponding single-server GI/G/1/0 queue. The GM Heuristic also uses an exact analysis of the GI/M/n/0 queue, while the MG Heuristic uses an exact analysis of the M/G/n/0 queue. Experimental results are based on the use of two-phase Coxian distributions for both the inter-arrival time and the service time; these include an error analysis for each heuristic and the derivation of experimental probability bounds for the loss probability. For the class of problems studied, it is concluded that there are likely to be many situations where the accuracy of the GM Heuristic is adequate for practical purposes. Methods are also developed for combining the GM and MG Heuristics. In some cases, this leads to approximations that are significantly more accurate than those obtained by the individual heuristics.     

On the Strong <Emphasis Type="Italic">n</Emphasis>-partite Tournaments with Exactly Two Cycles of Length <Emphasis Type="Italic">n</Emphasis> − 1

Gutin and Rafiey (Australas J. Combin. 34 (2006), 17-21) provided an example of an n-partite tournament with exactly n ? m + 1 cycles of length of m for any given m with 4 ≤ m ≤ n, and posed the following question. Let 3 ≤ m ≤ n and n ≥ 4. Are there strong n-partite tournaments, which are not themselves tournaments, with exactly n ? m + 1 cycles of length m for two values of m? In the same paper, they showed that this question has a negative answer for two values n ? 1 and n. In this paper, we prove that a strong n-partite tournament with exactly two cycles of length n ? 1 must contain some given multipartite tournament as subdigraph. As a corollary, we also show that the above question has a negative answer for two values n ? 1 and any l with 3 ≤ l ≤ n and l ≠ n ? 1.     

Maximum Distance Between Slater Orders and Copeland Orders of Tournaments

Given a tournament T?=?(X, A), we consider two tournament solutions applied to T: Slater’s solution and Copeland’s solution. Slater’s solution consists in determining the linear orders obtained by reversing a minimum number of directed edges of T in order to make T transitive. Copeland’s solution applied to T ranks the vertices of T according to their decreasing out-degrees. The aim of this paper is to compare the results provided by these two methods: to which extent can they lead to different orders? We consider three cases: T is any tournament, T is strongly connected, T has only one Slater order. For each one of these three cases, we specify the maximum of the symmetric difference distance between Slater orders and Copeland orders. More precisely, thanks to a result dealing with arc-disjoint circuits in circular tournaments, we show that this maximum is equal to n(n???1)/2 if T is any tournament on an odd number n of vertices, to (n ²???3n?+?2)/2 if T is any tournament on an even number n of vertices, to n(n???1)/2 if T is strongly connected with an odd number n of vertices, to (n ²???3n???2)/2 if T is strongly connected with an even number n of vertices greater than or equal to 8, to (n ²???5n?+?6)/2 if T has an odd number n of vertices and only one Slater order, to (n ²???5n?+?8)/2 if T has an even number n of vertices and only one Slater order.     

On an Extremal Problem for Poset Dimension

Let f(n) be the largest integer such that every poset on n elements has a 2-dimensional subposet on f(n) elements. What is the asymptotics of f(n)? It is easy to see that f(n) = n ^1/2. We improve the best known upper bound and show f(n) = O (n ^2/3). For higher dimensions, we show \(f_{d}(n)=\O \left (n^{\frac {d}{d + 1}}\right )\), where f _d (n) is the largest integer such that every poset on n elements has a d-dimensional subposet on f _d (n) elements.     

On collineation groups of finite projective spaces containing a Singer cycle

By a result of Kantor, any subgroup of GL(n, q) containing a Singer cycle normalizes a field extension subgroup. This result has as a consequence a projective analogue, and this paper gives the details of this deduction, showing that any subgroup of PΓL(n, q) containing a projective Singer cycle normalizes the image of a field extension subgroup GL(n/s, q^s) under the canonical homomorphism GL(n, q) → PGL(n, q), for some divisor s of n, and so is contained in the image of ΓL(n/s, q^s) under the canonical homomorphism ΓL(n, q) → PΓL(n, q). The actions of field extension subgroups on V (n, q) are also investigated. In particular, we prove that any field extension subgroup GL(n/s, q^s) of GL(n, q) has a unique orbit on s-dimensional subspaces of V (n, q) of length coprime to q. This orbit is a Desarguesian s-partition of V (n, q).     

Homology of braid groups,the Burau representation,and points on superelliptic curves over finite fields

The (reduced) Burau representation V _n of the braid group B _n is obtained from the action of B _n on the homology of an infinite cyclic cover of the disc with n punctures. In this paper, we calculate H _*(B _n ; V _n ). Our topological calculation has the following arithmetic interpretation (which also has different algebraic proofs): the expected number of points on a random superelliptic curve of a fixed genus over F _q is q.     

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.     

A note on scheduling jobs with equal processing times and inclusive processing set restrictions

We consider the problem of scheduling n jobs on m parallel machines with inclusive processing set restrictions. Each job has a given release date, and all jobs have equal processing times. The objective is to minimize the makespan of the schedule. Li and Li (2015) have developed an O(n²+mn log?n) time algorithm for this problem. In this note, we present a modified algorithm with an improved time complexity of O(min{m, log?n} ? n log?n).     

On the Problem of the Optimal Choice of Record Values

Let the independent random variables X1, X2, … have the same continuous distribution function. The upper record values X(1) = X₁ < X(2) < … generated by this sequence of variables, as well as the lower record values x(1) = X₁ > x(2) > …, are considered. It is known that in this situation, the mean value c(n) of the total number of the both types of records among the first n variables X is given by the equality c(n)=2(1+1/2+…+1/n), n = 1, 2, …. The problem considered here is following: how, sequentially obtaining the observed values x₁, x₂, … of variables X and selecting one of them as the initial point, to obtain the maximal mean value e(n) of the considered numbers of records among the rest random variables. It is not possible to come back to rejected elements of the sequence. Some procedures of the optimal choice of the initial element X _r are discussed. The corresponding tables for the values e(n) and differences δ(n)= e(n)–c(n) are presented for different values of n. The value of δ= lim_n→∞δ(n)is also given. In some sense, the considered problem and optimization procedure presented in this paper are quite similar to the classical “secretary problem,” in which the probability of selecting the last record value in the set of independent identically distributed X is maximized.     

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

A Heuristic Decomposition Algorithm for Scheduling Problems on Mixed Graphs

We consider a scheduling problem where a set of n jobs has to be processed on a set of m machines and arbitrary precedence constraints between operations are given. Moreover, for any two operations i and j values a _ij >0 and a _ji >0 may be given where a _ij is the minimal difference between the starting times of operations i and j when operation i is processed first. Often, the objective is to minimize the makespan but we consider also arbitrary regular criteria. Even the special cases of the classical job shop problem J//C_max belong to the set of NP-hard problems. Therefore, approximation or heuristic algorithms are necessary to handle large-dimension problems. Based on the mixed graph model we give a heuristic decomposition algorithm for such a problem, i.e. the initial problem is partitioned into subproblems that can be solved exactly or approximately with a small error bound. These subproblems are obtained by a relaxation of a subset of the set of undirected edges of the mixed graph. The subproblems are successively solved and a proportion of the results obtained for one subproblem is kept for further subproblem definitions. Numerical results of the algorithm presented here are given.     

Lower bounds for the largest eigenvalue of the gcd matrix on {1, 2,..., n}

Consider the n×n matrix with (i, j)’th entry gcd (i, j). Its largest eigenvalue λ_n and sum of entries s_n satisfy λ_n > s_n/n. Because s_n cannot be expressed algebraically as a function of n, we underestimate it in several ways. In examples, we compare the bounds so obtained with one another and with a bound from S.Hong, R.Loewy (2004). We also conjecture that λ_n > 6π^?2nlogn for all n. If n is large enough, this follows from F.Balatoni (1969).     

Note edge-colourings of <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">n,n</Emphasis></Subscript> with no long two-coloured cycles

Consider the set of all proper edge-colourings of a graph G with n colours. Among all such colourings, the minimum length of a longest two-coloured cycle is denoted L(n, G). The problem of understanding L(n, G) was posed by Häggkvist in 1978 and, specifically, L(n, K _n,n ) has received recent attention. Here we construct, for each prime power q ≥ 8, an edge-colouring of K _n,n with n colours having all two-coloured cycles of length ≤ 2q ², for integers n in a set of density 1 ? 3/(q ? 1). One consequence is that L(n, K _n,n ) is bounded above by a polylogarithmic function of n, whereas the best known general upper bound was previously 2n ? 4.     

On basicity of perturbed system of exponents in Lebesgue space with variable summability factor

In this paper, the system of exponents \(\{ e^{i\lambda _n t} \} _{n \in Z} \) is considered, where {λ _n } ? R has the following asymptotic form: λ _n = n ? α sign n + O(|n|^?β). Basis properties of this system in Lebesgue space with variable summability factor are investigated.     

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.     

Scheduling jobs with release dates,equal processing times,and inclusive processing set restrictions

We consider the problem of scheduling a given set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a given release date and is compatible to only a subset of the machines. The machines are ordered and indexed in such a way that a higher-indexed machine can process all the jobs that a lower-indexed machine can process. We present a solution procedure to solve this problem in O(n²+mnlogn) time. We also extend our results to the tree-hierarchical processing sets case and the uniform machine case.     

Meromorphic Solutions for a Class of Differential Equations and Their Applications

In this note, we study the admissible meromorphic solutions for algebraic differential equation fⁿf' + P_n?1(f) = R(z)e^α(z), where P_n?1(f) is a differential polynomial in f of degree ≤ n ? 1 with small function coefficients, R is a non-vanishing small function of f, and α is an entire function. We show that this equation does not possess any meromorphic solution f(z) satisfying N(r, f) = S(r, f) unless P_n?1(f) ≡ 0. Using this result, we generalize a well-known result by Hayman.