Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes

The n-dimensional hypercube network Q_n is one of the most popular interconnection networks since it has simple structure and is easy to implement. The n-dimensional locally twisted cube LTQ_n, an important variation of the hypercube, has the same number of nodes and the same number of connections per node as Q_n. One advantage of LTQ_n is that the diameter is only about half of the diameter of Q_n. Recently, some interesting properties of LTQ_n have been investigated in the literature. The presence of edge-disjoint Hamiltonian cycles provides an advantage when implementing algorithms that require a ring structure by allowing message traffic to be spread evenly across the interconnection network. The existence of two edge-disjoint Hamiltonian cycles in locally twisted cubes has remained unknown. In this paper, we prove that the locally twisted cube LTQ_n with n?4 contains two edge-disjoint Hamiltonian cycles. Based on the proof of existence, we further provide an O(n2ⁿ)-linear time algorithm to construct two edge-disjoint Hamiltonian cycles in an n-dimensional locally twisted cube LTQ_n with n?4, where LTQ_n contains 2ⁿ nodes and n2ⁿ⁻¹ edges.     

Geometric pattern matching for point sets in the plane under similarity transformations

We consider the following geometric pattern matching problem: Given two sets of points in the plane, P and Q, and some (arbitrary) δ>0, find a similarity transformation T (translation, rotation and scale) such that h(T(P),Q)<δ, where h(⋅,⋅) is the directional Hausdorff distance with L_∞ as the underlying metric; or report that none exists. We are only interested in the decision problem, not in minimizing the Hausdorff distance, since in the real world, where our applications come from, δ is determined by the practical uncertainty in the position of the points (pixels). Similarity transformations have not been dealt with in the context of the Hausdorff distance and we fill the gap here. We present efficient algorithms for this problem imposing a reasonable separation restriction on the points in the set Q. If the L_∞ distance between every pair of points in Q is at least 8δ, then the problem can be solved in O(mn²logn) time, where m and n are the numbers of points in P and Q respectively. If the L_∞ distance between every pair of points in Q is at least cδ, for some c, 0<c<1, we present a randomized approximate solution with expected runtime O(n²c−4ε−8log⁴mn), where ε>0 controls the approximation. Our approximation is on the size of the subset, B⊆P, such that h(T(B),Q)<δ and |B|>(1−ε)|P| with high probability.     

Constructing independent spanning trees for locally twisted cubes

The independent spanning trees (ISTs) problem attempts to construct a set of pairwise independent spanning trees and it has numerous applications in networks such as data broadcasting, scattering and reliable communication protocols. The well-known ISTs conjecture, Vertex/Edge Conjecture, states that any n-connected/n-edge-connected graph has n vertex-ISTs/edge-ISTs rooted at an arbitrary vertex r. It has been shown that the Vertex Conjecture implies the Edge Conjecture. In this paper, we consider the independent spanning trees problem on the n-dimensional locally twisted cube LTQ_n. The very recent algorithm proposed by Hsieh and Tu (2009) [12] is designed to construct n edge-ISTs rooted at vertex 0 for LTQ_n. However, we find out that LTQ_n is not vertex-transitive when n≥4; therefore Hsieh and Tu’s result does not solve the Edge Conjecture for LTQ_n. In this paper, we propose an algorithm for constructing n vertex-ISTs for LTQ_n; consequently, we confirm the Vertex Conjecture (and hence also the Edge Conjecture) for LTQ_n.     

A predictive model of impurity diffusion coefficients in face-centered-cubic metallic systems based on machine-learning

This paper develops models for diffusion coefficient prediction to provide parameters for atomic mobility databases and to assist material design in a multi-scale simulation framework for face-centered-cubic (fcc) alloys. Models of impurity-diffusion activation energy (Q_I) and self-diffusion activation energy (Q_s) are trained using machine-learning with experimental diffusion data and basic physical properties. The values of Q_s in body-centered cubic (bcc), fcc and hexagonal close-packed (hcp) can be well-predicted using melting temperature, electronic configuration, atomic properties and elasticity parameters. Estimates of Q_I in fcc metallic systems calculated using a model with six features agreed well with experimental data. Compared with previous models of Q_s and Q_I, the newly developed models exhibit higher coefficients of determination (R²) and significantly lower mean absolute errors. The self- and impurity-diffusion coefficients in fcc metallic systems can be simulated by these models. The models are also successfully applied during the assessment process of the Ni–Ti binary atomic mobility database. Thus, the developed models provide an easy and reliable method for estimating the self- or impurity-diffusion coefficients of fcc alloys when they are unavailable.     

Model reduction by CPOD and Kriging

This paper proposes a novel approach for multi-objective optimization when the criteria of interest rely on a functional output from an expensive-to-evaluate numerical simulator. More specifically, the proposed method is developed in the frame of an automotive application. The aim of this application is to design the shape of an intake port in order to maximize the mass flow (denoted by Q) and the tumble (denoted by T), which both depend on a 3D velocity field obtained by numerical flow simulation. Since the considered flow simulator is time-consuming, using regular multi-objective genetic algorithms (MOGA) directly on integral quantities depending on the simulator output is prohibitive. Three different Reduced Order Models (ROMs) are presented. The first one consists in directly Kriging the integral quantities Q and T on the basis of the outputs computed at an initial design of experiments, and basing the optimization search on the sequentially obtained couples of response surfaces. The other methods explored in the present work consist in building a parametrized representation of the whole velocity field by different variants of the Proper Orthogonal Decomposition (POD). Instead of directly Kriging Q and T at un-sampled locations, the proposed technique is hence to proceed in two steps: first approximate the functional outcome by Kriging the POD coefficients, and then compute the integral quantities Q and T associated with the approximate 3D field. However, such an approach induces new difficulties since the truncated POD does not preserve the global (integrated) quantities, and that surrogate-based MOGA with this kind of POD are therefore likely to fail locating the (Q, T)-Pareto front accurately. This is what motivates to propose an original constrained POD method (called CPOD) meant to overcome the bias created by the truncation made in regular POD. More precisely, this means modifying the way of calculating the POD coefficients by imposing the integral quantities Q and T based on the truncated POD to match with the actual Q and T values obtained by flow simulation at the design of experiments. A detailed comparison of the Pareto sets obtained from the three ROMs demonstrates the interest of the CPOD approach.     

Popular mixed matchings

We study the problem of matching applicants to jobs under one-sided preferences; that is, each applicant ranks a non-empty subset of jobs under an order of preference, possibly involving ties. A matching M is said to be more popular than T if the applicants that prefer M to T outnumber those that prefer T to M. A matching is said to be popular if there is no matching more popular than it. Equivalently, a matching M is popular if ?(M,T)≥?(T,M) for all matchings T, where ?(X,Y) is the number of applicants that prefer X to Y.Previously studied solution concepts based on the popularity criterion are either not guaranteed to exist for every instance (e.g., popular matchings) or are NP-hard to compute (e.g., least unpopular matchings). This paper addresses this issue by considering mixed matchings. A mixed matching is simply a probability distribution over matchings in the input graph. The function ? that compares two matchings generalizes in a natural manner to mixed matchings by taking expectation. A mixed matching P is popular if ?(P,Q)≥?(Q,P) for all mixed matchings Q.We show that popular mixed matchings always exist and we design polynomial time algorithms for finding them. Then we study their efficiency and give tight bounds on the price of anarchy and price of stability of the popular matching problem.     

Constrained,mixed-integer and multi-objective optimisation of building designs by NSGA-II with fitness approximation

Reducing building energy demand is a crucial part of the global response to climate change, and evolutionary algorithms (EAs) coupled to building performance simulation (BPS) are an increasingly popular tool for this task. Further uptake of EAs in this industry is hindered by BPS being computationally intensive: optimisation runs taking days or longer are impractical in a time-competitive environment. Surrogate fitness models are a possible solution to this problem, but few approaches have been demonstrated for multi-objective, constrained or discrete problems, typical of the optimisation problems in building design. This paper presents a modified version of a surrogate based on radial basis function networks, combined with a deterministic scheme to deal with approximation error in the constraints by allowing some infeasible solutions in the population. Different combinations of these are integrated with Non-Dominated Sorting Genetic Algorithm II (NSGA-II) and applied to three instances of a typical building optimisation problem. The comparisons show that the surrogate and constraint handling combined offer improved run-time and final solution quality. The paper concludes with detailed investigations of the constraint handling and fitness landscape to explain differences in performance.     

Simultaneous inner and outer approximation of shapes

For compact Euclidean bodiesP, Q, we define λ(P, Q) to be the smallest ratior/s wherer > 0,s > 0 satisfy \(sQ' \subseteq P \subseteq rQ''\) . HeresQ denotes a scaling ofQ by the factors, andQ′,Q″ are some translates ofQ. This function λ gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. If homothetic bodies are identified, the logarithm of this function is a metric. (Two bodies arehomothetic if one can be obtained from the other by scaling and translation.) For integerk ≥ 3, define λ(k) to be the minimum value such that for each convex polygonP there exists a convexk-gonQ with λ(P, Q) ≤ λ(k). Among other results, we prove that 2.118 ... <-λ(3) ≤ 2.25 and λ(k) = 1 + Θ(k ^?2). We give anO(n ² log² n)-time algorithm which, for any input convexn-gonP, finds a triangleT that minimizes λ(T, P) among triangles. However, in linear time we can find a trianglet with λ(t, P)<-2.25. Our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion-planning problem. In each case we describe algorithms which run faster when certain implicitslackness parameters of the input are bounded away from 1. These algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.     

Coefficient Fields of Solutions in Kovacic's Algorithm

In this paper we prove the following theorem: if the Riccati equation w^′ + w² = R(x), R ϵ Q(x), has algebraic solutions, then there exists a minimum polynomial defining such a solution whose coefficients lie at most in a cubic extension of the field Q. In Zharkov (1992), the same result was erroneously stated for, at most, quadratic extensions of Q. However, M. Singer discovered that in some cases the cubic extensions are necessary. Here we give a corrected and more detailed proof of the theorem.     

(1+4)-dimensional spherically symmetric black holes in <Emphasis Type="Italic">f</Emphasis>(<Emphasis Type="Italic">T</Emphasis>)

New non-vacuum spherically symmetric solutions in (1+4)-dimensional space-time are derived using the field equations of f(T) theory, where T is the torsion scalar defined as \(T\mathop = \limits^{def} {T^\mu }_{\nu \rho }S_\mu ^{\nu \rho }\). The energy density, radial and transversal pressures in these solutions are shown to satisfy the energy conditions. Other interesting solutions are obtained under the constraint of vanishing radial pressure for different choices of f(T). Impositions are provided to reproduce the (1+4)-dimensional AdS-Schwarzschild solution. In the quadratic case, i.e., f(T) ∝ T ², other impositions are derived and have shown to satisfy the non-diagonal components of the field equations of f(T) theory. The physics relevant to the resulting models is discussed.     

On the hop-constrained survivable network design problem with reliable edges

In this paper, we study the hop-constrained survivable network design problem with reliable edges. Given a graph with non-negative edge costs and node pairs Q, the hop-constrained survivable network design problem consists of constructing a minimum cost set of edges so that the induced subgraph contains at least K edge-disjoint paths containing at most L edges between each pair in Q. In addition, we consider here a subset of reliable edges that are not subject to failure. We study two variants: a static problem where the reliability of edges is given, and an upgrading problem where edges can be upgraded to the reliable status at a given cost. We adapt for the two variants an extended formulation proposed in Botton, Fortz, Gouveia, Poss (2011) [1] for the case without reliable edges. As before, we use Benders decomposition to accelerate the solving process. Our computational results indicate that these two variants appear to be more difficult to solve than the original problem (without reliable edges). We conclude with an economical analysis which evaluates the incentive of using reliable edges in the network.     

Reliable dissipative control for stochastic impulsive systems

This paper deals with the problem of reliable dissipative control for a class of stochastic hybrid systems. The systems under study are subject to Markovian jump, parameter uncertainties, possible actuator failure and impulsive effects, which are often encountered in practice and the sources of instability. Our attention is focused on the design of linear state feedback controllers and impulsive controllers such that, for all admissible uncertainties as well as actuator failure occurring among a prespecified subset of actuators, the stochastic hybrid system is stochastically robustly stable and strictly (Q,S,R)-dissipative. The sufficient conditions are obtained by using linear matrix inequality (LMI) techniques. The main results of this paper extend the existing results on H^∞ control.     

On the K best integer network flows

We address the problem of finding the K best integer solutions of a linear integer network flow problem. We design an O(f(n,m,L,U)+KmS(n,m,L)) time and O(K+m) memory space algorithm to determine the K best integer solutions, in a directed network with n nodes, m arcs, maximum absolute value cost L, and an upper bound U on arc capacities and node supplies. f(n,m,L,U) is the best time needed to solve the minimum cost flow problem in a directed network and S(n,m,L) is the best time to solve the single-source shortest path problem in a network with non-negative lengths. The introduced algorithm efficiently determines a “proper minimal cycle” by taking advantage of the relationship between the best solutions. This way, we improve the theoretical as well as practical memory space bounds of the well-known method due to Hamacher. Our computational experiments confirm this result.     

Deriving failures models for nonuniform concurrency from structured operational semantics

Semantic models are studied for concurrent languages which arenonuniform in that they involve individual variables which store values, and possible actions of an agent depend on its current state. First, an operational modelO _L(O) based on afailures domain is defined from alabeled transition system L(T) which is in turn specified by a setT of rules for deriving transitions. A method is the introduced for deriving a denotational failures modelD _T fromT whenT fits a certain syntactical format, called theNonuniform Non-Blocking Copy-Free SOS format (NU-NB-CF-SOS format), which is based on the format due to De Simone with certain additional restrictions specific to the nonuniform, setting. BothO _L(O) andD _T are constructed by applying the methodology of metric semantics, and the equivalence betweenD _T andO _L(T) is established by showing that bothO _L(T) andD _T are fixed-points of a higher-order mapping, which has a unique fixed-point by Banach’s fixed-point theorem.     

A genetic algorithm approach for multi-product multi-period continuous review inventory models

This paper formulates an approach for multi-product multi-period (Q, r) inventory models that calculates the optimal order quantity and optimal reorder point under the constraints of shelf life, budget, storage capacity, and “extra number of products” promotions according to the ordered quantity. Detailed literature reviews conducted in both fields have uncovered no other study proposing such a multi-product (Q, r) policy that also has a multi-period aspect and which takes all the aforementioned constraints into consideration. A real case study of a pharmaceutical distributor in Turkey dealing with large quantities of perishable products, for whom the demand structure varies from product to product and shows deterministic and variable characteristics, is presented and an easily-applicable (Q, r) model for distributors operating in this manner proposed. First, the problem is modeled as an integer linear programming (ILP) model. Next, a genetic algorithm (GA) solution approach with an embedded local search is proposed to solve larger scale problems. The results indicate that the proposed approach yields high-quality solutions within reasonable computation times.     

Asynchronous PRAMS with Memory Latency

We introduce two new asynchronous PRAM models which allow significant latencies for accessing global memory. In both models, accessing global memory takes L time units where Lis a fixed parameter, but the models provide two different mechanisms to help hide this latency. The Delay PRAM (D-PRAM) allows reads and writes to be issued before earlier reads and writes are completed; the Block PRAM (B-PRAM) allows a block of Lcontiguous locations in global memory to be read or written in O(L) time units. For both models we develop work-optimal randomized algorithms that solve a Certified Write-All Problem (CWA) of size n with expected O(n) work using up to (n log L)/(L log n) processors. This is a fundamental problem since it can be used as a synchronization primitive for n parallel instructions. If the D-PRAM has some restrictions on the asynchrony allowed we can use our CWA solution to simulate any n-processor CRCW PRAM program on a restricted D-PRAM with memory latency L, using O(n) expected work per parallel step, and using up to (n log L)/(L log n) D-PRAM processors. We prove a matching lower bound which shows that our CWA solution is optimal in terms of expected work. Our algorithms work both for models where the latency L to access global memory is fixed, and for models where the latency can vary probabilistically.     

Finite difference discretization of the extended Fisher-Kolmogorov equation in two dimensions

Approximate solutions are considered for the extended Fisher-Kolmogorov (EFK) equation in two space dimension with Dirichlet boundary conditions by a Crank-Nicolson type finite difference scheme. A priori bounds are proved using Lyapunov functional. Further, existence, uniqueness and convergence of difference solutions with order O(h²+k²) in the L^∞-norm are proved. Numerical results are also given in order to check the properties of analytical solutions.     

Application of gene expression programming in hot metal forming for intelligent manufacturing

Design of the die in hot metal forming operations depends on the required forming load. There are several approaches in the literature for load prediction. Artificial neural networks (ANNs) have been successfully used by a few researches to estimate the forming loads. This paper aims at using the effectiveness of a new evolutionary approach called gene expression programming (GEP) for the estimation of forging load in hot upsetting and hot extrusion processes. Several parameters such as angle (α), L/D ratio (R), friction coefficient (µ), velocity (v) and temperature (T) were used as input parameters. The accuracy of the developed GEP models was also compared with ANN models. This comparison was evidenced by some statistical measurements (R ², RMSE, MAE). The outcomes of the study showed that GEP can be used as an effective tool for representing the complex relationship between the input and output parameters of hot metal forming processes.

     

Approximation techniques for several stochastic inventory models

This paper considers two methods for approximating several complex stochastic inventory models. The first method involves determining optimal policies for a simpler modified version of the original problem. Examples of this approach, as used by the author, include stocking perishable inventory, the leadtime lost sales problem and an inventory problem with recycling. A second technique, which is appropriate for continuous review models, is based on using a line of reasoning similar to that used by Hadley and Whitin in the development of a heuristic (Q.R) inventory model. Examples of the approach include solutions of some continuous review systems including stocking decaying inventories and determining expected backorders in an inventory system with rationing.     

Control of 1-D parabolic PDEs with Volterra nonlinearities, Part I: Design

Boundary control of nonlinear parabolic PDEs is an open problem with applications that include fluids, thermal, chemically-reacting, and plasma systems. In this paper we present stabilizing control designs for a broad class of nonlinear parabolic PDEs in 1-D. Our approach is a direct infinite dimensional extension of the finite-dimensional feedback linearization/backstepping approaches and employs spatial Volterra series nonlinear operators both in the transformation to a stable linear PDE and in the feedback law. The control law design consists of solving a recursive sequence of linear hyperbolic PDEs for the gain kernels of the spatial Volterra nonlinear control operator. These PDEs evolve on domains T_n of increasing dimensions n+1 and with a domain shape in the form of a “hyper-pyramid”, 0≤ξ_n≤ξ_n−1?≤ξ₁≤x≤1. We illustrate our design method with several examples. One of the examples is analytical, while in the remaining two examples the controller is numerically approximated. For all the examples we include simulations, showing blow up in open loop, and stabilization for large initial conditions in closed loop. In a companion paper we give a theoretical study of the properties of the transformation, showing global convergence of the transformation and of the control law nonlinear Volterra operators, and explicitly constructing the inverse of the feedback linearizing Volterra transformation; this, in turn, allows us to prove L² and H¹ local exponential stability (with an estimate of the region of attraction where possible) and explicitly construct the exponentially decaying closed loop solutions.