检索结果-内蒙古大学图书馆

16th IEEE International Conference on Embedded and Real-time Computing Systems and Applications (RTCSA)

作者： Andrei, Stefan Cheng, Albert Rinard, Martin Osborne, Lawrence Lamar Univ Dept Comp Sci Beaumont TX 77710 USA Univ Houston Dept Comp Sci Houston TX 77204 USA MIT Dept Elect Engn & Comp Sci Cambridge MA 02139 USA

ISBN: (纸本)9780769541556

Tasks' scheduling has always been a central problem in the embedded real-time systems community. As in general the scheduling problem is NP-hard, researchers have been looking for efficient heuristics to solve the scheduling problem in polynomial time. One of the most important scheduling strategies is the Earliest Deadline First (EDF). It is known that EDF is optimal for uniprocessor platforms for many cases, such as: non-preemptive synchronous tasks (i.e., all tasks have the same starting time and cannot be interrupted), and preemptive asynchronous tasks (i.e., the tasks may be interrupted and may have arbitrary starting time). However, Mok showed that EDF is not optimal in multiprocessor platforms. In fact, for the multiprocessor platforms, the scheduling problem is NP-complete in most of the cases where the corresponding scheduling problem can be solved by a polynomial-time algorithm for uniprocessor platforms. Coffman and Graham identified a class of tasks for which the scheduling problem can be solved by a polynomial-time algorithm, that is, two-processor platform, no resources, arbitrary partial order relations, and every task is non-preemptive and has a unit computation time. Our paper introduces a new non-trivial and practical subclass of tasks, called urgent tasks. Briefly, a task is urgent if it is executed right after it is ready or it can only wait one unit time after it is ready. Practical examples of embedded real-time systems dealing with urgent tasks are all modern building alarm systems, as these include urgent tasks such as 'checking for intruders', 'sending a warning signal to the security office', 'informing the building's owner about a potential intrusion', and so on. By using propositional logic, we prove a new result in schedulability theory, namely that the scheduling problem for asynchronous and preemptive urgent tasks can be solved in polynomial time.

关键词： optimal scheduling urgent task polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Colouring Vertices of Triangle-Free Graphs 1

引用

36th International Workshop on Graph-Theoretic Concepts in Computer Science

作者： Dabrowski, Konrad Lozin, Vadim Raman, Rajiv Ries, Bernard Univ Warwick DIMAP Coventry CV4 7AL W Midlands England

ISBN: (数字)9783642169267

ISBN: (纸本)9783642169250

The VERTEX COLOURING problem is known to be NP-complete in the class of triangle-free graphs. Moreover, it remains NP-complete even if we additionally exclude a graph F which is not a forest. We study the computational complexity of the problem in (K(3), F)-free graphs with F being a forest. From known results it follows that for any forest F on 5 vertices the VERTEX COLOURING problem is polynomial-time solvable in the class of (K3, F)-free graphs. In the present paper, we show that the problem is also polynomial-time solvable in many classes of (K3, F)-free graphs with F being a forest on 6 vertices.

关键词： Vertex colouring Triangle-free graphs polynomial-time algorithm Clique-width

来源：评论

学校读者我要写书评

暂无评论

An efficient test for product states, with applications to quantum Merlin-Arthur games

An efficient test for product states, with applications to q...

引用

IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS)

作者： Harrow, Aram W. Montanaro, Ashley Univ Bristol Dept Math Bristol BS8 1TH Avon England Univ Washington Dept Comp Sci & Engn Seattle WA USA Univ Bristol Dept Comp Sci Bristol Avon England Univ Cambridge Dept Appl Math & Theoret Phys Cambridge CB2 1TN England

ISBN: (纸本)9780769542447

We give a test that can distinguish efficiently between product states of n quantum systems and states which are far from product. If applied to a state vertical bar psi > whose maximum overlap with a product state is 1 - epsilon, the test passes with probability 1 - Theta(epsilon), regardless of n or the local dimensions of the individual systems. The test uses two copies of vertical bar psi >. We prove correctness of this test as a special case of a more general result regarding stability of maximum output purity of the depolarising channel. A key application of the test is to quantum Merlin-Arthur games with multiple Merlins, where we obtain several structural results that had been previously conjectured, including the fact that soundness amplification is possible and that two Merlins can simulate many Merlins: QMA(k) = QMA(2) for k >= 2. Building on a previous result of Aaronson et al, this implies that there is an efficient quantum algorithm to verify 3-SAT with constant soundness, given two unentangled proofs of (O) over tilde(root n) qubits. Among other consequences, this result implies complexity-theoretic obstructions to finding a polynomial-time algorithm to determine separability of mixed quantum states, even up to constant error, and also to proving "weak" variants of the additivity conjecture for quantum channels. Finally, our test can also be used to construct an efficient test for determining whether a unitary operator is a tensor product, which is a generalisation of classical linearity testing.

关键词： SAT complexity-theoretic obstruction computability computational complexity depolarising channel game theory linearity testing maximum output purity polynomial-time algorithm probability probability product state product states quantum Merlin-Arthur quantum Merlin-Arthur game quantum algorithm quantum channel quantum computing quantum state quantum system separability tensor product tensors

来源：评论

学校读者我要写书评

暂无评论

Approximate algorithms of the Min-max Weighted Distance Problem

Approximate Algorithms of the Min-max Weighted Distance Prob...

引用

2010 4th International Conference on Intelligent Information Technology Application (IITA2010)

作者： Lin Liu Department of Mathematics and Physics Zhengzhou Institute of Aeronautical Industrial Management Zhengzhou, China Dayong Wu Department of Mathematics and Physics Zhengzhou Institute of Aeronautical Industrial Management Zhengzhou, China

The location problem is one kind of special type optimized problems .The Min-max weighted distance problem is a new class of location problem, its decision problem is a NP-Complete problem. In this paper, some approximate algorithms are designed, designs a genetic algorithm by some properties of the problem, and gives the design and selection method of crossover operator, mutation operator and reproduction operator.

关键词： location polynomial-time algorithm approximate algorithms genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Clique-transversal sets and weak 2-colorings in graphs of small maximum degree

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2009年第2期11卷 15-24页

作者： Bacso, Gabor Tuza, Zsolt Hungarian Acad Sci Inst Comp & Automat H-1111 Budapest Hungary Univ Pannonia Dept Comp Sci H-8200 Veszprem Hungary

A clique-transversal set in a graph is a subset of the vertices that meets all maximal complete subgraphs on at least two vertices. We prove that every connected graph of order n and maximum degree three has a clique-transversal set of size left perpendicular19n/30 + 2/15right perpendicular. This bound is tight, since 19n/30 - 1/15 is a lower bound for infinitely many values of n. We also prove that the vertex set of any connected claw-free graph of maximum degree at most four, other than an odd cycle longer than three, can be partitioned into two clique-transversal sets. The proofs of both results yield polynomial-time algorithms that find corresponding solutions.

关键词： clique-transversal set weak coloring clique coloring cubic graph claw-free graph polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Maximum-cover source location problems with objective edge-connectivity three

引用

MATHEMATICAL METHODS OF OPERATIONS RESEARCH 2009年第1期70卷 183-193页

作者： Sugihara, Kenya Ito, Hiro Kyoto Univ Grad Sch Informat Sakyo Ku Kyoto 6068501 Japan

Given a graph G = (V, E), a set of vertices S subset of V covers a vertex v is an element of V if the edge-connectivity between S and v is at least a given number k. Vertices in S are called sources. The maximum-cover source location problem, which is a variation of the source location problem, is to find a source set S with a given size at most p, maximizing the sum of the weight of vertices covered by S. In this paper, we show a polynomial-time algorithm for this problem in the case of k = 3 for a given undirected graph with a vertex weight function and an edge capacity function. Moreover, we show that this problem is NP-hard even if vertex weights and edge capacities are both uniform for general k.

关键词： Maximum-cover source location problem polynomial-time algorithm NP-hard

来源：评论

学校读者我要写书评

暂无评论

Independent sets in (P₆, diamond)-free graphs

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2009年第1期11卷 125-140页

作者： Mosca, Raffaele Univ G DAnnunzio Dipartimento Sci I-65127 Pescara Italy

We prove that on the class of (P-6, diamond)-free graphs the Maximum-Weight Independent Set problem and the Minimum-Weight Independent Dominating Set problem can be solved in polynomial time.

关键词： Maximum-Weight Independent Set Minimum-Weight Independent Dominating Set polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

MARKOV EQUIVALENCE FOR ANCESTRAL GRAPHS

引用

ANNALS OF STATISTICS 2009年第5B期37卷 2808-2837页

作者： Ali, R. Ayesha Richardson, Thomas S. Spirtes, Peter Univ Guelph Dept Math & Stat Guelph ON N1G 2W1 Canada Univ Washington Dept Stat Seattle WA 98195 USA Carnegie Mellon Univ Dept Philosophy Pittsburgh PA 15213 USA

Ancestral graphs can encode conditional independence relations that arise in directed acyclic graph (DAG) models with latent and selection variables. However, for any ancestral graph, there may be several other graphs to which it is Markov equivalent. We state and prove conditions under which two maximal ancestral graphs are Markov equivalent to each other, thereby extending analogous results for DAGs given by other authors. These conditions lead to an algorithm for determining Markov equivalence that runs in time that is polynomial in the number of vertices in the graph.

关键词： Directed acyclic graphs discriminating path inducing path Markov equivalence polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT SOLUTION OF A STOCHASTIC SCHEDULING PROBLEM ON AN OUT-FOREST-REVISITED

引用

SIAM JOURNAL ON OPTIMIZATION 2009年第2期20卷 903-914页

作者： Rothblum, Uriel G. Technion Israel Inst Technol IL-32000 Haifa Israel

We consider the problem of scheduling tasks subject to out-forest precedence constraints, where the tasks are identified with the edges. Initially only the tasks with no predecessors are available. At each step, an available task is selected and processed, resulting in either (a) termination, or (b) the replacement of the selected task in the available set by a random subset of its immediate successors. Also, an outcome-dependent reward is gained. The goal is to maximize the expected utility, which can be either linear or exponential. Denardo, Rothblum, and Van der Heyden [Math. Oper. Res., 29 (2004), pp. 162-181] (DRV) study a special version of the above problem. DRV use a leaf-to-stem induction to demonstrate the optimality of a priority rule and to compute it, the latter with work that is quadratic in the number of edges in the application that motivated their paper. Sethuraman and Tsitsiklis [Math. Oper. Res., 32 (2007), pp. 589-593] (ST) treat the general model and demonstrate optimality of a priority rule by employing an idea of Tsisiklis [Ann. Appl. Probab., 4 (1994), pp. 194-199] to successively eliminate nodes, from highest to lowest priority. ST report a work bound that is exponential in the size of the data. In the current paper, we adapt the leaf-to-stem methodology of DRV to show how to compute optimal priority rules for the general model, with work that is polynomial in the size of the data.

关键词： stochastic scheduling trees precedence constraints polynomial-time algorithm combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Stable marriage with ties and bounded length preference lists

引用

JOURNAL OF DISCRETE algorithmS 2009年第2期7卷 213-219页

作者： Irving, Robert W. Manlove, David F. O'Malley, Gregg Univ Glasgow Dept Comp Sci Glasgow G12 8QQ Lanark Scotland

We consider variants of the classical stable marriage problem in which preference lists may contain ties, and may be of bounded length. Such restrictions arise naturally in practical applications, such as centralised matching schemes that assign graduating medical students to their first hospital posts. In such a setting, weak stability is the most common solution concept, and it is known that weakly stable matchings can have different sizes. This motivates the problem of finding a maximum cardinality weakly stable matching, which is known to be NP-hard in general. We show that this problem is solvable in polynomial time if each man's list is of length at most 2 (even for women's lists that are of unbounded length). However if each man's list is of length at most 3, we show that the problem becomes NP-hard (even if each women's list is of length at most 3) and not approximable within some delta > 1 (even if each woman's list is of length at most 4). (C) 2008 Elsevier B.V. All rights reserved.

关键词： Stable marriage problem Ties Incomplete lists NP-hardness polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：