Entanglement and Berry phase in a 9 × 9 Yang–Baxter system

A M-matrix which satisfies the Hecke algebraic relations is presented. Via the Yang–Baxterization approach, we obtain a unitary solution \breveR(q,j₁,j₂){\breve{R}(\theta,\varphi_{1},\varphi_{2})} of Yang–Baxter equation. It is shown that any pure two-qutrit entangled states can be generated via the universal \breveR{\breve{R}}-matrix assisted by local unitary transformations. A Hamiltonian is constructed from the \breveR{\breve{R}}-matrix, and Berry phase of the Yang–Baxter system is investigated. Specifically, for j₁ = j₂{\varphi_{1}\,{=}\,\varphi_{2}}, the Hamiltonian can be represented based on three sets of SU(2) operators, and three oscillator Hamiltonians can be obtained. Under this framework, the Berry phase can be interpreted.     

An analytic approach to the problem of separability of quantum states based upon the theory of cones

Exploiting the cone structure of the set of unnormalized mixed quantum states, we offer an approach to detect separability independently of the dimensions of the subsystems. We show that any mixed quantum state can be decomposed as ρ = (1−λ)C _ρ  + λE _ρ , where C _ρ is a separable matrix whose rank equals that of ρ and the rank of E _ρ is strictly lower than that of ρ. With the simple choice C_r=M₁?M₂{C_{\rho}=M_{1}\otimes M_{2}} we have a necessary condition of separability in terms of λ, which is also sufficient if the rank of E _ρ equals 1. We give a first extension of this result to detect genuine entanglement in multipartite states and show a natural connection between the multipartite separability problem and the classification of pure states under stochastic local operations and classical communication. We argue that this approach is not exhausted with the first simple choices included herein.     

The sudden death of entanglement in constructed Yang–Baxter systems

Some Hamiltonians are constructed from the unitary \checkR_i,i+1(q, j){\check{R}_{i,i+1}(\theta, \varphi)}-matrices, where θ and j{\varphi} are time-independent parameters. We show that the entanglement sudden death (ESD) can happen in these closed Yang–Baxter systems. It is found that the ESD is not only sensitive to the initial condition, but also has a great connection with different Yang–Baxter systems. Especially, we find that the meaningful parameter j{\varphi} has a great influence on ESD.     

Minimizing total tardiness on parallel machines with preemptions

The basic scheduling problem we are dealing with in this paper is the following one. A set of jobs has to be scheduled on a set of parallel uniform machines. Each machine can handle at most one job at a time. Each job becomes available for processing at its release date. All jobs have the same execution requirement and arbitrary due dates. Each machine has a known speed. The processing of any job may be interrupted arbitrarily often and resumed later on any machine. The goal is to find a schedule that minimizes the sum of tardiness, i.e., we consider problem Q∣r _j ,p _j =p, pmtn∣∑T _j whose complexity status was open. Recently, Tian et al. (J. Sched. 9:343–364, 2006) proposed a polynomial algorithm for problem 1∣r _j ,p _j =p, pmtn∣∑T _j . We show that both the problem P∣ pmtn∣∑T _j of minimizing total tardiness on a set of parallel machines with allowed preemptions and the problem P∣r _j ,p _j =p, pmtn∣∑T _j of minimizing total tardiness on a set of parallel machines with release dates, equal processing times and allowed preemptions are NP-hard. Moreover, we give a polynomial algorithm for the case of uniform machines without release dates, i.e., for problem Q∣p _j =p, pmtn∣∑T _j .     

Uniform resource networks I. Complete graphs

A bidirectional resource network is a directed graph in which any two vertices υ _i , υ _j are either not adjacent or are connected by a pair of edges (υ _i , υ _j ), (υ _j , υ _i ). Non-negative numbers (resources) are assigned to vertices. The rules of functioning for such networks are formulated and processes of resource distribution in bidirectional networks represented by complete graphs are considered. It is shown that limit states of such networks do not depend on initial resource distributions.     

Resource scheduling with variable requirements over time

The problem of scheduling resources for tasks with variable requirements over time can be stated as follows. We are given two sequences of vectors A=A ₁,…,A _n and R=R ₁,…,R _m . Sequence A represents resource availability during n time intervals, where each vector A _i has q elements. Sequence R represents resource requirements of a task during m intervals, where each vector R _i has q elements. We wish to find the earliest time interval i, termed latency, such that for 1≤k≤m, 1≤j≤q: A _i+k−1 ^j ≥R _k ^j , where A _i+k−1 ^j and R _k ^j are the jth elements of vectors A _i+k−1 and R _k , respectively. One application of this problem is I/O scheduling for multimedia presentations. The fastest known algorithm to compute the optimal solution of this problem has computation time (Amir and Farach, in Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), San Francisco, CA, pp. 212–223, 1991; Inf. Comput. 118(1):1–11, 1995). We propose a technique that approximates the optimal solution in linear time: . We evaluated the performance of our algorithm when used for multimedia I/O scheduling. Our results show that 95% of the time, our solution is within 5% of the optimal.     

Parallel batch scheduling of equal-length jobs with release and due dates

In this paper we study parallel batch scheduling problems with bounded batch capacity and equal-length jobs in a single and parallel machine environment. It is shown that the feasibility problem 1|p-batch,b<n,r _j ,p _j =p,C _j ≤d _j |− can be solved in O(n ²) time and that the problem of minimizing the maximum lateness can be solved in O(n ²log n) time. For the parallel machine problem P|p-batch,b<n,r _j ,p _j =p,C _j ≤d _j |− an O(n ³log n)-time algorithm is provided, which can also be used to solve the problem of minimizing the maximum lateness in O(n ³log ² n) time.     

The Expressibility of First Order Dynamic Logic

This paper resolved an open problem proposed by A .P. Stolboushkin and M .A. Taitslin.We studied the expressibility of first order dynamic logic, and constructed infinite recursive programclasses K_1 , K_2, …, RG K_1 K_2 … RF, such that L (RG)相似文献   

A special case of the single-machine total tardiness problem is NP-hard

In this paper, it is shown that the special case B-1 of the single-machine total tardiness problem 1 ∥ ΣT _j is NP-hard in the ordinary sense. For this case, there exists a pseudo-polynomial algorithm with run time O(n σp _j). Published in Russian in Izvestiya Akademii Nauk. Teoriya i Sistemy Upravleniya, 2006, No. 3, pp. 120–128. Article was translated by the authors.     

Output-Sensitive Algorithm for Computing β-Skeletons

The β-skeleton is a measure of the internal shape of a planar set of points. We get an entire spectrum of shapes by varying the parameter β. For a fixed value of β, a β-skeleton is a geometric graph obtained by joining each pair of points whose β-neighborhood is empty. For β≥1, this neighborhood of a pair of points p _i ,p _j is the interior of the intersection of two circles of radius , centered at the points (1−β/2)p _i +(β/2)p _j and (β/2)p _i +(1−β/2)p _j , respectively. For β∈(0,1], it is the interior of the intersection of two circles of radius , passing through p _i and p _j . In this paper we present an output-sensitive algorithm for computing a β-skeleton in the metrics l ₁ and l _∞ for any β≥2. This algorithm is in O(nlogn+k), where k is size of the output graph. The complexity of the previous best known algorithm is in O(n ^5/2logn) [7]. Received April 26, 2000     

Online Dynamic Programming Speedups

Consider the dynamic program h(n)=min _1≤j≤n a(n,j), where a(n,j) is some formula that may (online) or may not (offline) depend on the previously computed h(i), for i<n. The goal is to compute all h(n), for 1≤n≤N. It is well known that, if a(n,j) satisfy the Monge property, then the SMAWK algorithm (Aggarwal et al., Algorithmica 2(1):195–208, 1987) can solve the offline problem in O(N) time; a Θ(N) speedup over the naive algorithm. In this paper we extend this speedup to the online case, that is, to compute h(n) in the order n=1,2,…,N when (i) we do not know the values of a(n′,j) for n′>n before h(n) has been computed and (ii) do not know the problem size N in advance. We show that if a(n,j) satisfy a stronger, but sometimes still natural, property than the Monge one, then each h(n) can be computed in online fashion in O(1) amortized time. This maintains the speedup online, in the sense that the total time to compute all h(n) is O(N). We also show how to compute each h(n) in the worst case O(log N) time, while maintaining the amortized time bound. For a(n,j) satisfying our stronger property, our algorithm is also simpler than the standard SMAWK algorithm for solving the offline case. We illustrate our technique on two examples from the literature; the first is the D-median problem on a line, and the second comes from mobile wireless paging. The research of the first author was partially supported by the NSF program award CNS-0626606; the research of the second and third authors was partially supported by Hong Kong RGC CERG grant HKUST6312/04E.     

On-line coloring and cliques covering for KK s,t -free graphs

The problem of on-line coloring of an arbitrary graphs is known to be hard. Here we consider the problem of on-line coloring in the simplified situation where the input graph is KK_s,t-free. We show that the on-line coloring algorithm with the First Fit strategy of proposed by Capponi and Pilotto in [1] is the best one for KK_1,t-free graphs (t≥3). A.Capponi and C.Pilotto have shown that this algorithm achieves a competitive ratio of t−1 while we show that it is the best possible. However for the family of KK_s,t-free graphs (s≥2, t≥2) there exists no on-line coloring algorithm with a competitive function. The problem of an on-line cliques covering for these families is hard. There exists no on-line cliques covering algorithm with a competitive function for the family of KK_s,t-free graphs (s≥ 1, t≥3). The additional assumption that the input graph is given in a connected way does not help a lot and does not change our results described above.     

On a reduction of the interval coloring problem to a series of bandwidth coloring problems

Given a graph G=(V,E) with strictly positive integer weights ω _i on the vertices i∈V, an interval coloring of G is a function I that assigns an interval I(i) of ω _i consecutive integers (called colors) to each vertex i∈V so that I(i)∩I(j)=∅ for all edges {i,j}∈E. The interval coloring problem is to determine an interval coloring that uses as few colors as possible. Assuming that a strictly positive integer weight δ _ij is associated with each edge {i,j}∈E, a bandwidth coloring of G is a function c that assigns an integer (called a color) to each vertex i∈V so that |c(i)−c(j)|≥δ _ij for all edges {i,j}∈E. The bandwidth coloring problem is to determine a bandwidth coloring with minimum difference between the largest and the smallest colors used. We prove that an optimal solution of the interval coloring problem can be obtained by solving a series of bandwidth coloring problems. Computational experiments demonstrate that such a reduction can help to solve larger instances or to obtain better upper bounds on the optimal solution value of the interval coloring problem.     

Algorithms for some maximization scheduling problems on a single machine

In this paper, we consider two scheduling problems on a single machine, where a specific objective function has to be maximized in contrast to usual minimization problems. We propose exact algorithms for the single machine problem of maximizing total tardiness 1‖max-ΣT _j and for the problem of maximizing the number of tardy jobs 1‖maxΣU _j . In both cases, it is assumed that the processing of the first job starts at time zero and there is no idle time between the jobs. We show that problem 1‖max-ΣT _j is polynomially solvable. For several special cases of problem 1‖maxΣT _j , we present exact polynomial algorithms. Moreover, we give an exact pseudo-polynomial algorithm for the general case of the latter problem and an alternative exact algorithm.     

Asymmetric multi-party quantum state sharing of an arbitrary m-qubit state

We present a scheme for asymmetric multi-party quantum state sharing of an arbitrary m-qubit state with n agents. The sender Alice first shares m − 1 Bell states and one n + 1-particle Greenberger–Horne–Zeilinger state with n agents, where the agent Bob, who is designated to recover the original m-qubit state, just keeps m particles and other agents (all controllers) n − 1 particles, that is, each controller only holds one particle in hand. Subsequently, Alice performs m Bell-basis measurements on her 2m particles and each controller only need take a single-particle measurement on his particle with the basis X. Finally, Bob can recover the original m-qubit state with the corresponding local unitary operations according to Alice and all controllers’ measurement results. Its intrinsic efficiency for qubits approaches 100%, and the total efficiency really approaches the maximal value, which is higher than those of the known symmetric schemes.     

Geodesic portrait of de Sitter-Schwarzschild spacetime

De Sitter-Schwarzschild space-time is a globally regular spherically symmetric spacetime which is asymptotically de Sitter as r → 0 and asymptotically Schwarzschild as r → ∞. A source term in the Einstein equations smoothly connects de Sitter vacuum at the origin with Minkowski vacuum at infinity and corresponds to an anisotropic vacuum fluid defined by symmetry of its stress-energy tensor which is invariant under radial boosts. In the range of the mass parameter M ≥ M _crit, de Sitter-Schwarzschild spacetime represents a vacuum nonsingular black hole, while M < M _crit corresponds to a compact gravitationally bound vacuum object without horizons, called a G-lump. Masses of objects are related to both de Sitter vacuum trapped inside and to smooth breaking of the spacetime symmetry from the de Sitter group at the origin to the Poincaré group at infinity. We here present a geodesic survey of de Sitter-Schwarzschild spacetime.     

Synchronous vs. Asynchronous Unison

This paper considers the self-stabilizing unison problem in uniform distributed systems. The contribution of this paper is threefold. First, we establish that when any self-stabilizing asynchronous unison protocol runs in synchronous systems, it converges to synchronous unison if the size of the clock K is greater than C _G , C _G being the length of the maximal cycle of the shortest maximal cycle basis if the graph contains cycles, 2 otherwise (tree networks). The second result demonstrates that the asynchronous unison in Boulinier et al. (In PODC ’04: Proceedings of the twenty-third annual ACM symposium on principles of distributed computing, pp. 150–159, 2004) provides a general self-stabilizing synchronous unison for trees which is optimal in memory space, i.e., it works with any K≥3, without any extra state, and stabilizes within 2D rounds, where D is the diameter of the network. This protocol gives a positive answer to the question whether there exists or not a general self-stabilizing synchronous unison for tree networks with a state requirement independent of local or global information of the tree. If K=3, then the stabilization time of this protocol is equal to D only, i.e., it reaches the optimal performance of Herman and Ghosh (Inf. Process. Lett. 54:259–265, 1995). The third result of this paper is a self-stabilizing unison for general synchronous systems. It requires K≥2 only, at least K+D states per process, and its stabilization time is 2D only. This is the best solution for general synchronous systems, both for the state requirement and the stabilization time. A preliminary version of this work was presented at the 7th International Symposium on Self-Stabilizing Systems (SSS 2005), Barcelona, Spain, October 2005.     

On the billiard approach in multidimensional cosmological models

A short overview of the billiard approach for cosmological-type models with n Einstein factor spaces is presented. We start with the billiard representation for pseudo-Euclidean Toda-like systems of cosmological origin. Then we consider cosmological models with a multicomponent perfect-fluid and with composite branes. The second case describes cosmological and spherically symmetric configurations in a theory with scalar fields and fields of forms. The conditions for appearance of asymptotic Kasnerlike and oscillating behaviors in the limits τ → +0 and τ → +∞ (where τ is the synchronous variable) are formulated (e.g., in terms of inequalities for Kasner parameters). Examples of billiards related to the hyperbolic Kac-Moody algebras E ₁₀, AE ₃ and A _1,II are given. Plenary talk given at the International Conference RUSGRAV-13, June 23–28, 2008, PFUR, Moscow.     

Testing Periodicity

We study the string-property of being periodic and having periodicity smaller than a given bound. Let Σ be a fixed alphabet and let p,n be integers such that p ￡ \fracn2p\leq \frac{n}{2} . A length-n string over Σ, α=(α ₁,…,α _n ), has the property Period(p) if for every i,j∈{1,…,n}, α _i =α _j whenever i≡j (mod p). For an integer parameter g ￡ \fracn2,g\leq \frac{n}{2}, the property Period(≤g) is the property of all strings that are in Period(p) for some p≤g. The property Period( ￡ \fracn2)\mathit{Period}(\leq \frac{n}{2}) is also called Periodicity.