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

On the legal firing sequence problem of Petri nets with cactus structure

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2000年第3期E83A卷 480-486页

作者： Fujito, T Taoka, S Watanabe, T Nagoya Univ Dept Elect Nagoya Aichi 4648603 Japan Hiroshima Univ Dept Circuits & Syst Higashihiroshima 7398527 Japan

The legal firing sequence problem (LFS) asks if it is possible to fire each transition some prescribed number of times in a given Petri net. It is a fundamental problem in Petri net theory as it appears as a subproblem, or as a simplified version of marking reachability, minimum initial resource allocation, liveness, and some scheduling problems. It is also known to be NP-hard, however, even under various restrictions on nets (and on Bring counts), and no efficient algorithm has been previously reported for any class of nets having general edge weights. We show in this paper that LFS can be solved in polynomial time (in O(n log n) time) for a subclass of state machines, called cacti, with arbitrary edge weights allowed (if each transition is asked to be fired exactly once).

关键词： Petri nets legal firing sequence problem polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

List partitions

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2003年第3期16卷 449-478页

作者： Feder, T Hell, P Klein, S Motwani, R Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Univ Fed Rio de Janeiro Dept Ciencia Comp IM COPPE Sistemas BR-21945970 Rio De Janeiro Brazil Stanford Univ Dept Comp Sci Stanford CA 94305 USA

List partitions generalize list colorings and list homomorphisms. (We argue that they may be called list "semihomomorphisms.") Each symmetric matrix M over 0, 1, (*) defines a list partition problem. Different choices of the matrix M lead to many well-known graph theoretic problems, often related to graph perfection, including the problem of recognizing split graphs, finding homogeneous sets, clique cutsets, stable cutsets, and so on. The recent proof of the strong perfect graph theorem employs three kinds of decompositions that can be viewed as list partitions. We develop tools which allow us to classify the complexity of many list partition problems and, in particular, yield the complete classification for small matrices M. Along the way, we obtain a variety of specific results, including generalizations of Lovasz's communication bound on the number of clique-versus-stable-set separators, polynomial time algorithms to recognize generalized split graphs, a polynomial algorithm for the list version of the clique cutset problem, and the first subexponential algorithm for the skew cutset problem of Chvatal. We also show that the dichotomy (NP-complete versus polynomial time solvable), conjectured for certain graph homomorphism problems, would, if true, imply a slightly weaker dichotomy (NP-complete versus quasi-polynomial) for our list partition problems.

关键词： list homomorphisms H-colorings graph partitions perfect graphs split graphs skew cutsets clique cutsets 2-joins communication bound dichotomy constraint satisfaction problems quasi-polynomial algorithms NP-completeness polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

A graph theoretical approach for the yield enhancement of reconfigurable VLSI/WSI arrays

引用

DISCRETE APPLIED MATHEMATICS 1999年第1-3期90卷 195-221页

作者： Narasimhan, J Nakajima, K Rim, CS IBM Corp Thomas J Watson Res Ctr Yorktown Heights NY 10598 USA Univ Maryland Dept Elect Engn College Pk MD 20742 USA Sogang Univ Dept Comp Sci Seoul South Korea

In this paper, we consider the yield enhancement of programmable structures by logical restructuring of the circuit placement. In this approach, an initial placement of a circuit on the array is first obtained by simulated annealing on a defect-free array. To implement the circuit on a defective array, the initial placement is reconfigured so that only the defect-free portion of the array is used. Customizing a given initial placement for each defective chip by logical restructuring, if done very fast, would be a cost effective method for yield enhancement. We describe a formulation of the circuit reconfiguration problem in terms of graphs and pebbles, wherein each processing element (PE) of the array is represented by a vertex which is classified as either defective or nondefective, depending upon whether the PE that it represents is defective or nondefective. Vertices representing PEs that are physically adjacent are connected by an edge, whose length is a measure of the proximity of the PEs, The logic elements of a circuit are represented by weighted pebbles. The initial placement of the circuit on the array corresponds to an initial placement of the pebbles on the vertices of the graph, with at most one pebble per vertex. The problem is to successively shift these pebbles along paths in the graph, such that after reconfiguration no pebble is located on a defective vertex, and an associated cost function is minimized. We describe four cost measures using weighted displacement and weighted shift of the pebbles. After presenting exact algorithms for some special cases of the problem, we prove the NP-completeness of the general cases of the corresponding decision problems. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： reconfiguration yield enhancement placement polynomial time algorithms NP-completeness

来源：评论

学校读者我要写书评

暂无评论

Parameterized complexity of MaxSat Above Average

引用

THEORETICAL COMPUTER SCIENCE 2013年 511卷 77-84页

作者： Crowston, Robert Gutin, Gregory Jones, Mark Raman, Venkatesh Saurabh, Saket Univ London Egham Surrey England Inst Math Sci Madras 600113 Tamil Nadu India

In MAXSAT, we are given a CNF formula F with n variables and m clauses;the task is to find a truth assignment satisfying the maximum number of clauses. Let r(1),..., r(m), be the number of literals in the clauses of F. Then asat(F) = Sigma(m)(i=1)(1-2(-r1)) is the expected number of clauses satisfied by a random truth assignment, when the truth values to the variables are distributed uniformly and independently. It is well-known that, in polynomial time, one can find a truth assignment satisfying at least asat(F) clauses. In the parameterized problem MAXSAT-AA, we are to decide whether there is a truth assignment satisfying at least asat(F) + k clauses, where k is the (nonnegative) parameter. We prove that MAXSAT-AA is para-NP-complete and thus, MAXSAT-AA is not fixed-parameter tractable unless P = NP. This is in sharp contrast to the similar problem MAXLIN 2-AA which was recently proved to be fixed-parameter tractable by Crowston et al. (FSTTCS 2011). In fact, we consider a more refined version of MAXSAT-AA, MAX-r(n)-SAT-AA, where r(j) <= r(n) for each j. Alan et al. (SODA 2010) proved that if r = r(n) is a constant, then MAX-r-SAT-AA is fixed-parameter tractable. We prove that MAX-r(n)-SAT-AA is para-NPcomplete for any r(n) >= inverted right perpendicularlog ninverted left perpendicular. We also prove that assuming the exponential time hypothesis, MAX-r(n)-SAT-AA is not even in XP for any integral r(n) >= log log n + phi(n), where phi(n) is any real-valued unbounded strictly increasing computable function. This lower bound on r(n) cannot be decreased much further as we prove that MAX-r(n)-SAT-AA is (i) in XP for any r(n) <= log log n - log log log n and (ii) fixed-parameter tractable for any r(n) <= log log n - log log log n - phi(n), where phi(n) is any real-valued unbounded strictly increasing computable function. The proof uses some results on MAXLIN 2-AA. (C) 2013 Elsevier B.V. All rights reserved.

关键词： PARAMETERIZATION COMPUTATIONAL complexity ARITHMETIC mean MATHEMATICAL formulas polynomial time algorithms MATHEMATICAL proofs

来源：评论

学校读者我要写书评

暂无评论

Rescheduling Problems with Agreeable Job Parameters to Minimize the Tardiness Costs under Deterioration and Disruption

引用

MATHEMATICAL PROBLEMS IN ENGINEERING 2013年第1期2013卷 1-7页

作者： Zhang Xingong Wang Yong Chongqing Univ Coll Econ & Business Adm Chongqing 400030 Peoples R China Chongqing Normal Univ Coll Math Sci Chongqing 400047 Peoples R China

This paper considers single-machine rescheduling problems with agreeable job parameters under deterioration and disruption. Deteriorating jobs mean that the processing time of a job is defined by an increasing function of its starting time. Rescheduling means that, after a set of original jobs has already been scheduled, a new set of jobs arrives and creates a disruption. We consider four cases of minimization of the total tardiness costs with agreeable job parameters under a limit of the disruptions from the original job sequence. We propose polynomial-time algorithms or some dynamic programming algorithms under sequence disruption and time disruption.

关键词： TARDINESS FUNCTIONS (Mathematics) polynomial time algorithms DYNAMIC programming PRODUCTION scheduling MATHEMATICAL models

来源：评论

学校读者我要写书评

暂无评论

The Most Trustworthy Path Selection in Online Social Networks

引用

MATHEMATICAL PROBLEMS IN ENGINEERING 2013年第1期2013卷 1-10页

作者： Liu, Lianggui Zhejiang Sci Tech Univ Sch Informat Sci & Technol Hangzhou 310018 Zhejiang Peoples R China

In online social networks, it is crucial for a service consumer to find the most trustworthy path to a target service provider from numerous social trust paths between them. The selection of the most trustworthy path (namely, optimal social trust path (OSTP)) with multiple end-to-end quality of trust (QoT) constraints has been proved to be NP-Complete. Heuristic algorithms with polynomial and pseudo-polynomial-time complexities are often used to deal with this challenging problem. However, existing solutions cannot guarantee the efficiency of searching;that is, they can hardly avoid obtaining partial optimal solutions during searching process. Quantum annealing uses delocalization and tunneling to avoid falling into local minima without sacrificing execution time. It has been proved to be a promising way to many optimization problems in recently published literature. In this paper, for the first time, QA based OSTP algorithm (QA_OSTP) is applied to the selection of the most trustworthy path. The experiment results show that QA based algorithm has better performance than its heuristic opponents.

关键词： PATH analysis (Statistics) ONLINE social networks polynomialS HEURISTIC algorithms QUANTUM annealing polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Scheduling imprecise computation tasks on uniform processors

引用

INFORMATION PROCESSING LETTERS 2007年第2期104卷 45-52页

作者： Wan, Guohua Leung, Joseph Y-T. Pinedo, Michael L. New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA Shenzhen Univ Coll Management Shenzhen 518060 Peoples R China NYU Stern Sch Business New York NY 10012 USA

We consider the problem of preemptively scheduling n imprecise computation tasks on m >= 1 uniform processors, with each task T-i having two weights w(i) and w(i)'. Three objectives are considered: (1) minimizing the maximum w'-weighted error;(2) minimizing the total w-weighted error subject to the constraint that the maximum w'-weighted error is minimized;(3) minimizing the maximum w'-weighted error subject to the constraint that the total w-weighted error is minimized. For these objectives, we give polynomial time algorithms with time complexity O(mn(4)), O(mn(4)) and O(kmn(4)), respectively, where k is the number of distinct w-weights. We also present alternative algorithms for the three objectives, with time complexity O(cmn(3)), O(cmn(3) + mn(4)) and O(kcmn(3)), respectively, where c is a parameter-dependent number. (c) 2007 Elsevier B.V. All rights reserved.

关键词： preemptive scheduling uniform processors imprecise computation task polynomial time algorithms algorithms analysis of algorithms combinatorial problems

来源：评论

学校读者我要写书评

暂无评论

The Ordered Covering Problem

引用

ALGORITHMICA 2018年第10期80卷 2874-2908页

作者： Feige, Uriel Hitron, Yael Weizmann Inst Sci Dept Comp Sci & Appl Math IL-76100 Rehovot Israel

We study the Ordered Covering (OC) problem. The input is a finite set of n elements X, a color function and a collection of subsets of X. A solution consists of an ordered tuple of sets from which covers X, and a coloring such that , the first set covering x in the tuple, namely with , has color . The minimization version is to find a solution using the minimum number of sets. Variants of OC include OC in which each element of color appears in at most sets of , and k-OC in which the first set of the solution is required to have color 0, and there are at most alternations of colors in the solution. Among other results we showThere is a polynomial time approximation algorithm for Min-OC(2, 2) with approximation ratio 2. (This is best possible unless Vertex Cover can be approximated within a ratio better than 2.) Moreover, Min-OC(2, 2) can be solved optimally in polynomial time if the underlying instance is bipartite. For every , there is a polynomial time approximation algorithm for Min-3-OC with approximation . Unless the unique games conjecture is false, this is best possible.

关键词： SET theory FUNCTIONS (Mathematics) GRAPH theory polynomial time algorithms MATHEMATICAL analysis

来源：评论

学校读者我要写书评

暂无评论

SCHEDULING MULTIPROCESSOR TASKS ON 3-DEDICATED PROCESSORS

引用

INFORMATION PROCESSING LETTERS 1992年第5期41卷 275-280页

作者： BLAZEWICZ, J DELLOLMO, P DROZDOWSKI, M SPERANZA, MG CNR IASIROMEITALY UNIV BRESCIA DEPT QUANTITAT METHODSBRESCIAITALY

The problem of scheduling a set of multiprocessor tasks on 3 dedicated processors is considered. Each task requires for its processing the simultaneous availability of a specified subset of processors. The objective of the problem is to minimize the makespan. Because tasks requiring all 3 processors cannot be executed in parallel with any other task, they can be simply added at the beginning of the schedule. Therefore, attention is focused on uni-processor and duo-processor tasks. The general problem of scheduling tasks on 3 dedicated problems is shown to be NP-hard in the strong sense. Some polynomial cases are presented, and an approximation algorithm for hard cases is presented and analyzed.

关键词： PARALLEL PROCESSING RESOURCE ALLOCATION SCHEDULING COMPUTATIONAL COMPLEXITY polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Probabilistic analysis of a combined aggregation and math programming heuristic for a general class of vehicle routing and scheduling problems

引用

MANAGEMENT SCIENCE 1997年第8期43卷 1060-1078页

作者： Federgruen, A vanRyzin, G Graduate School of Business Columbia University New York NY 10027 United States

We propose and analyze a heuristic that uses region partitioning and an aggregation scheme for customer attributes (load size, time windows, etc.) to create a finite number of customer types. A math program is solved based on these aggregated customer types to generate a feasible solution to the original problem. The problem class we address is quite general and defined by a number of general consistency properties. Problems in this class include VRPs with general distance norms, capacitated problems, time window VRPs, pick-up and delivery problems, combined inventory control and routing problems and are routing. We provide a probabilistic analysis of this heuristic under very general probabilistic assumptions. In particular, we do not require independence between customer locations and their various attributes. The heuristic is (a.s.) epsilon-optimal as the number of customers n tends to infinity. Further, it runs in O(n log n) time for a fixed relative error, and can be designed to be asymptotically optimal while still running in polynomial time. We characterize the asymptotic average value of the heuristic and the optimal solution as the limit of a sequence of linear program values. We also provide bounds on the rate of convergence to the asymptotic value and bounds on tail probabilities. Finally, we discuss numerical issues involved in implementing our heuristic.

关键词： vehicle routing linear programming probabilistic analysis polynomial time algorithms heuristics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：