Robinson has proposed the bundle-based decomposition algorithm to solve a class of structured large-scale convex optimization problems. In this method, the original problem is transformed (by dualization) to an uncons...
详细信息
Robinson has proposed the bundle-based decomposition algorithm to solve a class of structured large-scale convex optimization problems. In this method, the original problem is transformed (by dualization) to an unconstrained nonsmooth concave optimization problem which is in turn solved by using a modified bundle method. In this paper, we give a posteriori error estimates on the approximate primal optimal solution and on the duality gap. We describe implementation and present computational experience with a special case of this class of problems, namely, block-angular linear programming problems. We observe that the method is efficient in obtaining the approximate optimal solution and compares favorably with MINOS and an advanced implementation of the Dantzig-Wolfe decomposition method.
We consider the problem of preemptively scheduling a set of periodic, real-time tasks on a multiprocessor computer system. We give a new scheduling algorithm, the so-called Slack-Time Algorithm, and show that it is mo...
详细信息
We consider the problem of preemptively scheduling a set of periodic, real-time tasks on a multiprocessor computer system. We give a new scheduling algorithm, the so-called Slack-Time Algorithm, and show that it is more effective than the known Deadline Algorithm. We also give an (exponential-time) algorithm to decide if a task system is schedulable by the Slack-Time or the Deadline Algorithm. The same algorithm can also be used to decide if a task system is schedulable by any given fixed-priority scheduling algorithm. This resolves an open question posed by Leung and Whitehead. Finally, it is shown that the problem of deciding if a task system is schedulable by the Slack-Time, the Deadline, or any given fixed-priority scheduling algorithm is co-NP-hard for each fixedm≥.
If there is to be a new, substantive area of teaching and research that combines competence in specific areas of the humanities with computer {1. understandings and skills, such teaching and research needs to be l...
详细信息
If there is to be a new, substantive area of teaching and research that combines competence in specific areas of the humanities with computer {1. understandings and skills, such teaching and research needs to be led by persons who themselves are competent in both the humanities and in computer {1., rather than by a team of persons who represent a division' of labors along the lines of 'idea' persons and 'technical' persons. The new kind of teaching and research that might result is pointed to by describing a connectionist, neural network approach to the study of metaphor.
Ranking is the problem of computing for an input string its lexicographic index in a given (fixed) language. This paper concerns the complexity of ranking. We show that ranking languages accepted by 1.way unambiguous ...
Ranking is the problem of computing for an input string its lexicographic index in a given (fixed) language. This paper concerns the complexity of ranking. We show that ranking languages accepted by 1.way unambiguous auxiliary pushdown automata operating in polynomial time is inNC (2). We also prove negative results about ranking for several classes of simple languages.C is rankable in deterministic polynomial time iffP=P #P , whereC is any of the following six classes of languages: (1. languages accepted by logtime-bounded nondeterministic Turing machines, (2) languages accepted by (uniform) families of unbounded fan-in circuits of constant depth and polynomial size, (3) languages accepted by 2-way deterministic pushdown automata, (4) languages accepted by multihead deterministic finite automata, (5) languages accepted by 1.way nondeterministic logspace-bounded Turing machines, and (6) finitely ambiguous linear context-free languages.
Recovery from transient processor failures can be achieved by using optimistic message logging and checkpointing. The faulty processors roll back, and some/all of the non-faulty processors also may have to roll back. ...
详细信息
Recovery from transient processor failures can be achieved by using optimistic message logging and checkpointing. The faulty processors roll back, and some/all of the non-faulty processors also may have to roll back. This paper formulates the rollback problem as a closure problem. A centralized closure algorithm is presented together with two efficient distributed implementations. Several related problems are also considered and distributed algorithms are presented for solving them.
In this paper, we extend the partial deduction framework of Lloyd and Shepherdson, so that unfolding of non-ground negative literals and loop checks can be carried out during partial deduction. We show that the unifie...
详细信息
In this paper, we extend the partial deduction framework of Lloyd and Shepherdson, so that unfolding of non-ground negative literals and loop checks can be carried out during partial deduction. We show that the unified framework is sound and complete wrt well-founded model semantics, when certain conditions are satisfied.
In this article,both the basic principles and the experimental methods of identity recognition technology based on heart sounds are ***,the characteristics of heart sounds and the feasibility of heart sounds as a biom...
详细信息
In this article,both the basic principles and the experimental methods of identity recognition technology based on heart sounds are ***,the characteristics of heart sounds and the feasibility of heart sounds as a biometric were analyzed.A synthetic model of heart sounds was then developed based on a family of wavelets;Finally,the characteristic parameters of heart sounds were extracted by using the heart sounds linear band frequency cepstra(HS-LBFC)with a specified configuration,and the similarity distance was adopted for heart sound *** highlight the difference in two heart sound signals between the time and frequency domains,a construction method of the heart sound wavelet,a calculation method of the parameters of a synthetic model,selection of the characteristic parameters of heart sounds and the corresponding data processing technology were *** experimental results showed that the proposed method exhibited excellent performance and practicability.
For the first time, a threshold quantum secure direct communication (TQSDC) scheme is presented. Similar to the classical Shamir's secret sharing scheme, the sender makes n shares, S1. …, Sn of secret key K and e...
详细信息
For the first time, a threshold quantum secure direct communication (TQSDC) scheme is presented. Similar to the classical Shamir's secret sharing scheme, the sender makes n shares, S1. …, Sn of secret key K and each receiver keeps a share secretly. If the sender wants to send a secret message M to the receivers, he en-codes the information of K and M on a single photon sequence and sends it to one of the receivers. According to the secret shares, the t receivers sequentially per-form the corresponding unitary operations on the single photon sequence and ob-tain the secret message M. The shared shares may be reusable if it can be judged that there is no eavesdropper in line. We discuss that our protocol is feasible with current technology.
This paper derives an asymptotic average symbol error probability(SEP)expression for multiple-input multiple-output(MIMO)two-hop amplify-and-forward(AF)relay systems with optimal *** analysis at high signal-to-noise r...
详细信息
This paper derives an asymptotic average symbol error probability(SEP)expression for multiple-input multiple-output(MIMO)two-hop amplify-and-forward(AF)relay systems with optimal *** analysis at high signal-to-noise ratio(SNR)quantifies the diversity order and array gain,which are valid for any antenna numbers of the terminals and arbitrary channel fading *** is also proved that the system performance is dominated by the relatively degraded one of the two-hop *** results based on the simple expressions provide valuable insights into the performance and practical design considerations of MIMO AF networks.
暂无评论