Experimental investigation and thermodynamic modeling of the Cu–Mn–Ni system

The phase equilibria of the ternary Cu–Mn–Ni system in the region above 40 at.% Mn at 600 ^°C were investigated by means of optical microscopy, X-ray diffraction, scanning electron microscopy with energy dispersive X-ray spectroscopy and electron probe microanalysis. The isothermal section of the Cu–Mn–Ni system at 600 ^°C consists of 4 two-phase regions (cbcc_A12 +fcc_A1, cub_A13 +fcc_A1, cbcc_A12 + cub_A13, L₁₀$L{1}_0$ +fcc_A1) and 1 three-phase region (cbcc_A12 +cub_A13 +fcc_A1). The disordered fcc_A1 phase exhibits a large continuous solution between γ$\gamma$(Cu,Ni) and γ$\gamma$(Mn). The L₁₀$L{1}_0$ phase only equilibrates with fcc_A1 phase, and the solubility of Cu in L₁₀$L{1}_0$ phase is up to 16 at.%. A thermodynamic modeling for this system was performed by considering reliable literature data and incorporating the current experimental results. A self-consistent set of thermodynamic parameters was obtained, and the calculated results show a general agreement with the experimental data.     

A representation theorem for (q-)holonomic sequences

Chomsky and Schützenberger showed in 1963 that the sequence _dL(n)$d_L(n)$, which counts the number of words of a given length n in a regular language L, satisfies a linear recurrence relation with constant coefficients for n  , i.e., it is C-finite. It follows that every sequence s(n)$s(n)$ which satisfies a linear recurrence relation with constant coefficients can be represented as _dL1(n)−_dL2(n)$d_{L_1}(n)-d_{L_2}(n)$ for two regular languages. We view this as a representation theorem for C-finite sequences. Holonomic or P-recursive sequences are sequences which satisfy a linear recurrence relation with polynomial coefficients. q-Holonomic sequences are the q-analog of holonomic sequences. In this paper we prove representation theorems of holonomic and q-holonomic sequences based on position specific weights on words, and for holonomic sequences, without using weights, based on sparse regular languages.     

Asynchronous deterministic rendezvous in graphs

Two mobile agents (robots) having distinct labels and located in nodes of an unknown anonymous connected graph have to meet. We consider the asynchronous version of this well-studied rendezvous problem and we seek fast deterministic algorithms for it. Since in the asynchronous setting, meeting at a node, which is normally required in rendezvous, is in general impossible, we relax the demand by allowing meeting of the agents inside an edge as well. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of edge traversals of both agents until rendezvous is achieved. If agents are initially situated at a distance D   in an infinite line, we show a rendezvous algorithm with cost O(D|_Lmin|²)$\mathrm{O}(D|L_{\min }{|}^2)$ when D   is known and O((D+|_Lmax|)³)$\mathrm{O}((D+\left|L_{\max }\right|{)}^3)$ if D   is unknown, where |_Lmin|$\left|L_{\min }\right|$ and |_Lmax|$\left|L_{\max }\right|$ are the lengths of the shorter and longer label of the agents, respectively. These results still hold for the case of the ring of unknown size, but then we also give an optimal algorithm of cost O(n|_Lmin|)$\mathrm{O}(n|L_{\min }|)$, if the size n   of the ring is known, and of cost O(n|_Lmax|)$\mathrm{O}(n|L_{\max }|)$, if it is unknown. For arbitrary graphs, we show that rendezvous is feasible if an upper bound on the size of the graph is known and we give an optimal algorithm of cost O(D|_Lmin|)$\mathrm{O}(D|L_{\min }|)$ if the topology of the graph and the initial positions are known to agents.     

Operations preserving regular languages

Given a strictly increasing sequence s   of non-negative integers, filtering a word _a0a1?_an$a_0{a}_1?a_n$ by s   consists in deleting the letters _ai$a_i$ such that i   is not in the set {_s0,_s1,…}$\{s_0,s_1,\dots \}$. By a natural generalization, denote by L[s]$L[s]$, where L is a language, the set of all words of L filtered by s. The filtering problem is to characterize the filters s such that, for every regular language L  , L[s]$L[s]$ is regular. In this paper, the filtering problem is solved, and a unified approach is provided to solve similar questions, including the removal problem considered by Seiferas and McNaughton. Our approach relies on a detailed study of various residual notions, notably residually ultimately periodic sequences and residually rational transductions.     

Online bin packing with arbitrary release times

We study a new variant of the online bin-packing problem, in which each item _ai$a_i$ is associated with a size _ai$a_i$ and also a release time _ri$r_i$ so that it must be placed at least _ri$r_i$ above the bottom of a bin. Items arrive in turn and must be assigned without any knowledge of subsequent items. The goal is to pack all items into unit-size bins using the minimum number of bins. We study the problem with all items have equal size. First, we show that the ANY FIT algorithm cannot be approximated within any constant. Then we present a best possible online algorithm with asymptotic competitive ratio of two.     

Borderedness-preserving homomorphisms

This paper aims at investigating properties of homomorphisms which preserve the bordered words. The bordered words are classified into _d1$d_1$-words and _d2$d_2$-words, where the length of the proper border of _d2$d_2$-word is greater than half of it. Some characterizations of _d1$d_1$-word-preserving homomorphism are studied. Some relationships among d-primitivity-preserving homomorphisms, _d1$d_1$-word-preserving homomorphisms, and _d2$d_2$-word-preserving homomorphisms are investigated. We show that every d-primitivity-preserving homomorphism is _d1$d_1$-word-preserving and every _d1$d_1$-word-preserving homomorphism is _d2$d_2$-word-preserving.     

An approximation algorithm to the k-Steiner Forest problem

Given a graph G$G$, an integer k$k$, and a demand set D={(_s1,_t1),…,(_sl,_tl)}$D=\{(s_1,t_1),\dots ,(s_l,t_l)\}$, the k$k$-Steiner Forest problem finds a forest in graph G$G$ to connect at least k$k$ demands in D$D$ such that the cost of the forest is minimized. This problem was proposed by Hajiaghayi and Jain in SODA’06. Thereafter, using a Lagrangian relaxation technique, Segev et al. gave the first approximation algorithm to this problem in ESA’06, with performance ratio O(n^2/3logl)$O(n^{2/3}logl)$. We give a simpler and faster approximation algorithm to this problem with performance ratio O(n^2/3logk)$O(n^{2/3}logk)$ via greedy approach, improving the previously best known ratio in the literature.     

Pareto and scalar bicriterion optimization in scheduling deteriorating jobs

In the paper two problems of a single machine bicriterion scheduling of a set of deteriorating jobs are considered. The jobs are independent, nonpreemptable and are ready for processing at time 0$0$. The processing time _pj$p_j$ of each job is a linear function of the starting time _Sj$S_j$ of the job, _pj=1+_αjSj$p_j=1+{\alpha }_j{S}_j$, where _Sj?0$S_j?0$ and _αj>0${\alpha }_j>0$ for j=0,1,...,n$j=0,1,...,n$.     

Scheduling machine-dependent jobs to minimize lateness on machines with identical speed under availability constraints

In this paper we consider the problem of scheduling n$n$ preemptive jobs on m$m$ machines with identical speed under machine availability and eligibility constraints when minimizing maximum lateness (_Lmax$(L_{\max }$). The lateness of a job is defined to be its completion time minus its due date, and _Lmax$L_{\max }$ is the maximum value of lateness among all jobs. We assume that each machine is not continuously available at all time throughout the planning horizon and each job is only allowed to be processed on specific machines. Network flow technique is used to formulate this scheduling problem into a series of maximum flow problems. We propose a polynomial time two-phase binary search algorithm to verify the feasibility of the problem and to solve the scheduling problem optimally if a feasible schedule exists. Finally, we show that the time complexity of the algorithm is O((n+(2n+2x))³log(UB-LB))$O((n+(2n+2x){)}^3\log (\text{<italic>UB</italic>}-\text{<italic>LB</italic>}))$. Most literature in parallel machine scheduling assume that all machines are continuously available for processing and all jobs can be processed at any available machine throughout the planning horizon. But both assumptions might not be true in some practical environment, such as machine preventive maintenance and machines that have different capabilities to process jobs. This type of scheduling problem is seldom studied in the literature. The purpose of this paper is to examine the scheduling problem with machines with identical speed under machine availability and eligibility constraints. The objective is to minimize maximum lateness. We formulate this scheduling problem into a series of maximum flow problems with different values of _Lmax$L_{\max }$. A polynomial time two-phase binary search algorithm is proposed to verify the feasibility of the problem and to determine the optimal _Lmax$L_{\max }$.     

Nonstandard numerical methods for a mathematical model for influenza disease

In this paper we construct and develop two competitive implicit finite difference scheme for a deterministic mathematical model associated with the evolution of influenza A disease in human population. Qualitative dynamics of the model is determined by the basic reproduction number, _R0$R_0$. Numerical schemes developed here are based on nonstandard finite difference methods. Our aim is to transfer essential properties of the continuous model to the discrete schemes and to obtain unconditional stable schemes. The proposed numerical schemes have two fixed points which are identical to the critical points of the continuous model and it is shown that they have the same stability properties. Numerical simulations with different initial conditions, parameters values and time step sizes are developed for different values of parameter _R0$R_0$, convergence to the disease free equilibrium point when _R0<1$R_0<1$ and to the endemic equilibrium point when _R0>1$R_0>1$ are obtained independent of the time step size. These numerical integration schemes are useful since can reproduce the dynamics of original differential equations.     

Degree-constrained decompositions of graphs: Bounded treewidth and planarity

We study the problem of decomposing the vertex set V$V$ of a graph into two nonempty parts _V1,_V2$V_1,V_2$ which induce subgraphs where each vertex v∈_V1$v\in V_1$ has degree at least a(v)$a(v)$ inside _V1$V_1$ and each v∈_V2$v\in V_2$ has degree at least b(v)$b(v)$ inside _V2$V_2$. We give a polynomial-time algorithm for graphs with bounded treewidth which decides if a graph admits a decomposition, and gives such a decomposition if it exists. This result and its variants are then applied to designing polynomial-time approximation schemes for planar graphs where a decomposition does not necessarily exist but the local degree conditions should be met for as many vertices as possible.     

Notes on inverse bin-packing problems

In bin-packing problems, given items need to be packed using a minimum number of bins. Inverse bin-packing number problems, IBPN for short, assume a given set of items and number of bins. The objective is to achieve the minimum perturbation to the item-size vector so that all the items can be packed into the prescribed number of bins. In this paper, complexity status and approximation behavior for IBPN were investigated. Under the _Lp$L_p$-norm, ∀p∈{1,2,…,∞}$\forall p\in \{1,2,\dots ,\infty \}$, IBPN turns out to be NP-hard in the strong sense. IBPN under the _L1$L_1$-norm admits a polynomial time differential approximation scheme, and a fully polynomial time approximation scheme if a constant number of machines is provided as input. We also consider another IBPN variant where a specified feasible solution is given instead of a target bin number. The objective is to make the given solution optimal with minimum modification. We provide the hardness result for this problem.