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

The complexity of cyclic shop scheduling problems

JOURNAL OF SCHEDULING 2002年第4期5卷 307-327页

作者： Hall, NG Lee, TE Posner, ME Ohio State Univ Dept Management Sci Columbus OH 43210 USA Korea Adv Inst Sci & Technol Dept Ind Engn Yusong Gu Taejon 305701 South Korea

We consider scheduling problems for shops in which a job set is manufactured repetitively. Jobs are scheduled to minimize the cycle time of the job set, which is equivalent to maximizing the throughput rate. We characterize the complexity of the scheduling problem for several types of job shops. Polynomial time algorithms are presented for open shops, and for job shops where each job has at most two operations. When there are two machines and the maximum number of operations of any job is a constant k greater than or equal to 3, the recognition version of the job shop problem is shown to be binary NP-complete. We describe a pseudopolynomial time algorithm for a special case of the problem when k = 3. We also establish that some generalizations of this problem are unary NP-complete. One consequence of these results is that the recognition version of the two machine job shop makespan problem with at most five operations per job is unary NP-complete. This resolves a question posed by Lenstra et al. (Ann. Discrete Math. 1977;1:343). More generally, our results provide a map of the computational complexity of cycle time minimization problems that is analogous to that in the literature for makespan problems. Copyright (C) 2002 John Wiley Sons, Ltd.

关键词： manufacturing cyclic scheduling sequencing algorithms and complexity

来源：评论

学校读者我要写书评

暂无评论

Semantics and complexity of abduction from default theories

引用

ARTIFICIAL INTELLIGENCE 1997年第1-2期90卷 177-223页

作者： Eiter, T Gottlob, G Leone, N DEIS UNICAL CNR IST SISTEMIST & INFORMAT I-87036 RENDE ITALY

Abductive reasoning (roughly speaking, find an explanation for observations out of hypotheses) has been recognized as an important principle of common-sense reasoning. Since logical knowledge representation is commonly based on nonclassical formalisms like default logic, autoepistemic logic, or circumscription, it is necessary to perform abductive reasoning from theories (i.e., knowledge bases) of nonclassical logics. In this paper, we investigate how abduction can be performed from theories in default logic. In particular, we present a basic model of abduction from default theories. Different modes of abduction are plausible, based on credulous and skeptical default reasoning;they appear useful for different applications such as diagnosis and planning, Moreover, we thoroughly analyze the complexity of the main abductive reasoning tasks, namely finding an explanation, deciding relevance of a hypothesis, and deciding necessity of a hypothesis. These problems are intractable even in the propositional case, and we locate them into the appropriate slots of the polynomial hierarchy. However, we also present known classes of default theories for which abduction is tractable. Moreover, we also consider first-order default theories, based on domain closure and the unique names assumption, In this setting, the abduction tasks are decidable, but have exponentially higher complexity than in the propositional case. (C) 1997 Elsevier Science B.V.

关键词： abduction default logic algorithms and complexity tractability

来源：评论

学校读者我要写书评

暂无评论

COMPUTATIONAL-complexity OF DISTRIBUTED DETECTION PROBLEMS WITH INFORMATION CONSTRAINTS

引用

COMPUTERS & ELECTRICAL ENGINEERING 1993年第6期19卷 445-451页

作者： RAO, NSV IYENGAR, SS KASHYAP, RL OLD DOMINION UNIV DEPT COMP SCINORFOLKVA 23529 LOUISIANA STATE UNIV DEPT COMP SCIBATON ROUGELA 70803 PURDUE UNIV DEPT ELECT ENGNW LAFAYETTEIN 47907

For a system consisting of a set of sensors S = {S1, S2, ..., S(m)} and a set of objects O = {O1, O2, ..., O(n)}, there are information constraints given by a relation R subset-or-equal-to S x O such that (S(i), O(j)) is-an-element-of R if and only if S(i) is capable of detecting O(j). Each (S(i), O(j)) is-an-element-of R is assigned a confidence factor (a positive real number) which is either explicitly given or can be efficiently computed. Given that a subset of sensors have detected obstacles, the detection problem is to identify a subset H subset-of-equal-to O with the maximum confidence value. The computational complexity of the detection problem, which depends on the nature of the confidence factor and the information constraints, is the main focus of this paper. This problem exhibits a myriad of complexity levels ranging from a worst-case exponential (in n) lower bound in a general case to an O(m + n) time solvability. We show that the following simple versions of a detection problem are computationally intractable: (a) deterministic formulation, where confidence factors are either 0 or 1;(b) uniform formulation where (S(i), O(j)) is-an-element-of R, for all S(i) is-an-element-of S, O(j) is-an-element-of O;(c) decomposable systems under multiplication operation. We then show that the following versions are solvable in polynomial (in n) time: (a) single object detection;(b) probabilistically independent detection;(c) decomposable systems under additive and nonfractional multiplicative measures;and (d) matroid systems.

关键词： DISTRIBUTED DETECTION NETWORKS algorithms and complexity COMPUTATIONAL INTRACTABILITY

来源：评论

学校读者我要写书评

暂无评论

The complexity of manipulative attacks in nearly single-peaked electorates

引用

ARTIFICIAL INTELLIGENCE 2014年第1期207卷 69-99页

作者： Faliszewski, Piotr Hemaspaandra, Edith Hemaspaandra, Lane A. AGH Univ Sci & Technol Dept Comp Sci Krakow Poland Rochester Inst Technol Dept Comp Sci Rochester NY 14623 USA Univ Rochester Dept Comp Sci Rochester NY 14627 USA

Many electoral control and manipulation problems-which we will refer to in general as "manipulative actions" problems-are NP-hard in the general case. It has recently been noted that many of these problems fall into polynomial time if the electorate is single-peaked, i.e., is polarized along some axis/issue. However, real-world electorates are not truly single-peaked. There are usually some mavericks, and so real-world electorates tend merely to be nearly single-peaked. This paper studies the complexity of manipulative-action algorithms for elections over nearly single-peaked electorates. We do this for many notions of nearness and for a broad range of election systems. We provide instances where even one maverick jumps the manipulative-action complexity up to NP-hardness, but we also provide many instances where some number of mavericks can be tolerated without increasing the manipulative-action complexity. (C) 2013 Elsevier B.V. All rights reserved.

关键词： algorithms and complexity Computational social choice Election control/manipulation Multiagent systems Nearly single-peaked preferences

来源：评论

学校读者我要写书评

暂无评论

COMPUTATIONAL-complexity ISSUES IN OPERATIVE DIAGNOSIS OF GRAPH-BASED SYSTEMS

引用

IEEE TRANSACTIONS ON COMPUTERS 1993年第4期42卷 447-457页

作者： RAO, NSV Oak Ridge Nat. Lab. TN USA Abstract Authors References Cited By Keywords Metrics Similar Download Citation Email Print Request Permissions

Systems that can be modeled as graphs, such thal nodes represent the components and the edges represent the fault propagation between the components, are considered. Some components are equipped with alarms that ring in response to faulty conditions. In these systems, two types of problems are studied: a) fault diagnosis, and b) alarm placement. The fault diagnosis problems deal with computing the set of all potential failure sources that correspond to a set of ringing alarms A(R). First, the single faults, where exactly one component can become faulty at any time, are considered. Systems are classified into zero-time and nonzero-time systems based on fault propagation times, and the latter is further classified based on the knowledge of propagation times. For each of these classes algorithms are presented for single fault diagnosis. The problem of detecting multiple faults is shown to be NP-complete. An alarm placement problem, that requires a single fault to be uniquely diagnosed, is examined;various versions of this problem are shown to be NP-complete. The single fault diagnosis algorithms have been implemented and tested.

关键词： ALARM PLACEMENT PROBLEMS algorithms and complexity FAULT DIAGNOSIS NP-COMPLETE PROBLEMS OPERATIVE DIAGNOSIS SINGLE AND MULTIPLE FAULTS

来源：评论

学校读者我要写书评

暂无评论

Computing intersections of Horn theories for reasoning with models

引用

ARTIFICIAL INTELLIGENCE 1999年第1期110卷 57-101页

作者： Eiter, T Ibaraki, T Makino, K Vienna Univ Technol Inst Ludwig Wittgenstein Labor Informat Syst Knowledge Based Syst Grp A-1040 Vienna Austria Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 606 Japan Osaka Univ Grad Sch Engn Sci Dept Syst & Human Sci Toyonaka Osaka 560 Japan

Model-based reasoning has been proposed as an alternative form of representing and accessing logical knowledge bases. In this approach, a knowledge base is represented by a set of characteristic models. In this paper, we consider computational issues when combining logical knowledge bases, which are represented by their characteristic models;in particular, we study taking their logical intersection. We present low-order polynomial time algorithms or prove intractability for the major computation problems in the context of knowledge bases which are Horn theories. In particular, we show that a model of the intersection Sigma of Horn theories Sigma(1),...,Sigma(l) represented by their characteristic models, can be found in linear time, and that some characteristic model of Sigma can be found in polynomial time. Moreover, we present an algorithm which enumerates all the models of Sigma with polynomial delay. The analogous problem for the characteristic models is proved to be intractable, even if the possible exponential size of the output is taken into account. Furthermore, we show that approximate computation of the set of characteristic models is difficult as well. Nonetheless, we show that deduction from Sigma is possible for a large class of queries in polynomial time, while abduction turns out to be intractable. We also consider a generalization of Horn theories, and prove negative results for the basic questions, indicating that an extension of the positive results beyond Horn theories is not immediate. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： automated reasoning model-based reasoning characteristic models algorithms and complexity knowledge representation

来源：评论

学校读者我要写书评

暂无评论

Variable-strength conditional preferences for ranking objects in ontologies

引用

JOURNAL OF WEB SEMANTICS 2007年第3期5卷 180-194页

作者： Lukasiewicz, Thomas Schellhase, Joerg Univ Roma La Sapienza Dipartimento Informat & Sistemat I-00185 Rome Italy Univ Kassel Fachgebiet Wirtschaftsinformat D-34127 Kassel Germany

introduce conditional preference bases as a means for ranking objects in ontologies. Conditional preference bases consist of a description logic knowledge base and a finite set of conditional preferences, which are statements of the form "generally, in the context phi, property a is preferred over property -alpha with strength s". They are inspired by variable-strength defaults in conditional knowledge bases. We define the notion of consistency for conditional preference bases, and we show how consistent conditional preference bases can be used for ranking objects in ontologies, where every object represents essentially a set of individuals that are sharing the same ranking-relevant properties. More concretely, we define two object rankings, denoted k(sum) and k(lex), which evaluate the strengths of conditional preferences in an additive and a lexicographic way, respectively. Furthermore, we provide algorithms for the main computational tasks for ranking objects under conditional preference bases, we analyze the complexity of these tasks, and we delineate a tractable special case. To give evidence of the usefulness of this approach in practice, we describe two applications in the areas of product and literature search, where it allows especially for a flexible user-defined ranking of the query results reflecting personal preferences. (c) 2007 Elsevier B.V. All rights reserved.

关键词： variable-strength conditional preference ranking ontology description logic semantic web literature search algorithms and complexity

来源：评论

学校读者我要写书评

暂无评论

DNA combinatorial messages and Epigenomics: The case of chromatin organization and nucleosome occupancy in eukaryotic genomes

引用

THEORETICAL COMPUTER SCIENCE 2019年 792卷 117-130页

作者： Giancarlo, Raffaele Rombo, Simona E. Utro, Filippo Univ Palermo Dipartimento Matemat & Informat Via Archirafi 34 I-90123 Palermo Italy IBM TJ Watson Res Computat Biol Ctr Yorktown Hts NY 10598 USA

Epigenomics is the study of modifications on the genetic material of a cell that do not depend on changes in the DNA sequence, since those latter involve specific proteins around which DNA wraps. The end result is that Epigenomic changes have a fundamental role in the proper working of each cell in Eukaryotic organisms. A particularly important part of Epigenomics concentrates on the study of chromatin, that is, a fiber composed of a DNA-protein complex and very characterizing of Eukaryotes. Understanding how chromatin is assembled and how it changes is fundamental for Biology. In more than thirty years of research in this area, Mathematics and Theoretical Computer Science have gained a prominent role, in terms of modeling and mining, regarding in particular the so-called 10 nm fiber. Starting from some very basic notions of Biology, we briefly illustrate the recent advances obtained via laboratory experiments on the organization and dynamics of chromatin. Then, we mainly concentrate our attention on the contributions given by Combinatorial and Informational Methodologies, that are at the hearth of Theoretical Computer Science, to the understanding of mechanisms determining the 10 nm fiber. We conclude highlighting several directions of investigation that are perceived as important and where Theoretical Computer Science can provide high impact results. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Computational biology algorithms and complexity Formal languages Combinatorics on words

来源：评论

学校读者我要写书评

暂无评论

Total tessellation cover: Bounds, hardness, and applications

引用

DISCRETE APPLIED MATHEMATICS 2022年 323卷 149-161页

作者： Abreu, Alexandre Cunha, Luis Figueiredo, Celina Marquezino, Franklin Posner, Daniel Portugal, Renato Univ Fed Rio de Janeiro Rio De Janeiro Brazil Fundacao Getulio Vargas Rio De Janeiro Brazil Univ Fed Fluminense Niteroi Brazil Univ Fed Rural Rio de Janeiro Seropedica Brazil Lab Nacl Comp Cient Petropolis Brazil

The concept of graph tessellation cover was defined in the context of quantum walk models, and is a current research area in graph theory. In this work, we propose a generalization called total tessellation cover. A tessellation of a graph G is a partition of its vertex set V(G) into vertex disjoint cliques. A tessellation cover of G is a set of tessellations that covers its edge set E(G). A total tessellation cover of G consists of a tessellation cover together with a compatible vertex coloring, such that the color of each vertex is different from the tessellation labels of the edges incident to the vertex. The total tessellation cover number Tt(G) is the size of a minimum total tessellation cover of G. We present lower bounds Tt(G) > omega(G) and Tt(G) > s(G) + 1, where omega(G) is the size of a maximum clique, and s(G) is the number of edges of a maximum induced star subgraph. A graph G is called a good total tessellable if Tt(G) = omega(G) or Tt(G) = s(G)+ 1. We study the complexity of the k -TOTAL TESSELLABILITy problem, which aims to decide whether a given graph G has Tt(G) < k. We prove that k -TOTAL TESSELLABILITy is in P for good total tessellable graphs. We establish the NP-completeness of the k -TOTAL TESSELLABILITy when restricted to the following graph classes: bipartite graphs, line graphs of triangle-free graphs, universal graphs, (2, 1)-chordal graphs and planar graphs.(c) 2021 Elsevier B.V. All rights reserved.

关键词： Graph tessellation Graph coloring algorithms and complexity Quantum walks

来源：评论

学校读者我要写书评

暂无评论

On the connection between a cyclic job shop and a reentrant flow shop scheduling problem

引用

JOURNAL OF SCHEDULING 2006年第4期9卷 381-387页

作者： Steiner, George Xue, Zhihui McMaster Univ Hamilton ON L8S 4M4 Canada Canadian Imperial Bank Commerce Toronto ON Canada

Hall et al. (J. Sched. 2002;5:307-327) investigated the cycle time minimization problem in a two-machine job shop, where each job consists of at most three operations. In this note, we reduce the problem to a two-mach... 详细信息

关键词： job shop reentrant flow shop cycle time makespan algorithms and complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：