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

An O(n²) algorithm for a controllable machine scheduling problem

IMA Journal of Management Mathematics 1999年第1期10卷 15-26页

作者： Huang, Wanzhen Zhang, Feng Department of Mathematics and Statistics School of Mathematical Sciences Lakehead University ON P7B 5E1 Canada Department of Applied Mathematics Shanghai Second Polytechnic University China

A single-machine scheduling problem with controllable processing times is discussed in this paper. For some jobs, the processing time can be crashed up to u units of time with the additional cost c per unit of time crashed. The object is to find an optimal processing sequence as well as crash activities to minimize total costs of completion and crash. This problem is shown to be polynomially solvable, and an O(n²) algorithm is given together with the theoretical proof. © Oxford University Press 1999.

关键词： Controllable processing times Crash activities polynomial-time algorithm Single-machine scheduling problems

来源：评论

学校读者我要写书评

暂无评论

On the complexity of computing mixed volumes

引用

SIAM JOURNAL ON COMPUTING 1998年第2期27卷 356-400页

作者： Dyer, M Gritzmann, P Hufnagel, A Univ Leeds Sch Comp Studies Leeds LS2 9JT W Yorkshire England Tech Univ Munich Ctr Math Sci D-80290 Munich Germany

This paper gives various (positive and negative) results on the complexity of the problem of computing and approximating mixed volumes of polytopes and more general convex bodies in arbitrary dimension. On the negative side, we present several # P-hardness results that focus on the difference of computing mixed volumes versus computing the volume of polytopes. We show that computing the volume of zonotopes is # P-hard (while each corresponding mixed volume can be computed easily) but also give examples showing that computing mixed volumes is hard even when computing the volume is easy. On the positive side, we derive a randomized algorithm for computing the mixed volumes [GRAPHICS] of well-presented convex bodies K(1),...,K(s), where m(1),...,m(s) is an element of N(0) and m(1) greater than or equal to n - psi(n) with psi(n) = o(log n/log log n). The algorithm is an interpolation method based on polynomial-time randomized log algorithms for computing the volume of convex bodies. This paper concludes with applications of our results to various problems in discrete mathematics, combinatorics, computational convexity, algebraic geometry, geometry of numbers, and operations research.

关键词： computational convexity volume mixed volumes convex body polytope zonotope parallelotope computation approximation computational complexity deterministic algorithm randomized algorithm polynomial-time algorithm NP-hardness #P-hardness permanent determinant problems lattice point enumerator partial order Newton polytope polynomial equations

来源：评论

学校读者我要写书评

暂无评论

String noninclusion optimization problems

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 1998年第3期11卷 456-467页

作者： Rubinov, AR Timkovsky, VG Natl Transport Inst Moscow Russia Russian Acad Sci Econ Forecasting Inst Dept Comp Sci Moscow 117418 Russia

For every string inclusion relation there are two optimization problems: find a longest string included in every string of a given finite language, and find a shortest string including every string of a given finite language. As an example, the two well-known pairs of problems, the longest common substring (or subsequence) problem and the shortest common superstring (or supersequence) problem, are interpretations of these two problems. In this paper we consider a class of opposite problems connected with string noninclusion relations: find a shortest string included in no string of a given finite language and find a longest string including no string of a given finite language. The predicate "string alpha is not included in string beta" is interpreted as either "alpha is not a substring of beta" or "alpha is not a subsequence of beta". The main purpose is to determine the complexity status of the string noninclusion optimization problems. Using graph approaches we present polynomial-time algorithms for the first interpretation and NP-hardness proofs for the second. We also discuss restricted versions of the problems, correlations between the string inclusion and noninclusion problems, and generalized problems which are the string inclusion problems for one language and the string noninclusion problems for another. In applications the string inclusion problems are used to find a similarity between any structures which can be represented by strings. Respectively, the noninclusion problems can be used to find a nonsimilarity. Such problems occur in computational molecular biology, data compression, pattern recognition, and flexible manufacturing. The above generalized problems arise naturally in all of these applied areas. Apart from this practical reason, we hope that studying the string noninclusion problems will yield deeper understanding of the string inclusion problems.

关键词： string inclusion longest shortest common subsequence substring supersequence superstring polynomial-time algorithm NP-hard problem

来源：评论

学校读者我要写书评

暂无评论

Scheduling imprecise computation tasks with 0/1-constraint

引用

DISCRETE APPLIED MATHEMATICS 1997年第1-3期78卷 117-132页

作者： Ho, KIJ Leung, JYT Wei, WD Department of Computer Science and Engineering University of Nebraska-Lincoln Lincoln NE 68588-0115 USA

We consider the problem of preemptively scheduling a set of imprecise computation tasks on a single processor, with the added constraint that each optional subtask is either fully executed or entirely discarded. Two performance metrics are considered: (1) the total error;(2) the number of imprecisely scheduled tasks (i.e., tasks whose optional subtasks are entirely discarded). Since the problem of minimizing the total error is NP-hard, we consider an O(n(2))-time heuristic for it, where n is the number of tasks. It is shown that the total error of the schedule produced by the heuristic is at most three times that of an optimal schedule and the bound is tight. For the problem of minimizing the number of imprecisely scheduled tasks, we show that it can be solved in O(n(5)) time. Since the time complexity is unacceptably high, we consider an O(n(2))-time heuristic for it. It is shown that the number of imprecisely scheduled tasks in the schedule produced by the heuristic is at most twice that in an optimal schedule and the bound is tight. Interestingly, the number of precisely scheduled tasks (i.e., tasks whose optional subtasks are fully executed) in an optimal schedule is also at most twice that in the schedule produced by the heuristic and the bound is tight.

关键词： real-time system imprecise computation task single processor preemptive scheduling NP-hard polynomial-time algorithm heuristics worst-case analysis

来源：评论

学校读者我要写书评

暂无评论

Computing lower bounds on functional units before scheduling

引用

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS 1996年第2期4卷 273-279页

作者： Chaudhuri, S Walker, RA RENSSELAER POLYTECH INST DEPT ELECT COMP & SYST ENGNTROYNY 12180 RENSSELAER POLYTECH INST DEPT COMP SCITROYNY 12180

This brief presents a new polynomial-time algorithm for computing lower bounds on the number of functional units (FU's) of each type required to schedule a data Bow graph in a specified number of control steps. A formal approach is presented that is guaranteed to find the tightest possible bounds that can be found by relaxing either the precedence constraints or integrality constraints on the scheduling problem, This tight, yet fairly efficient, bounding method can be used to estimate FU area, to generate resource constraints for reducing the search space, or in conjunction with exact techniques for efficient optimal design space exploration.

关键词： VLSI circuit CAD data flow graphs formal specification high level synthesis integrated circuit design scheduling VLSI synthesis data flow graph scheduling functional units lower bounds optimal design space exploration polynomial-time algorithm resource c Lower bound FUNCTIONAL UNITS circuit CAD integrated circuit design Very large scale integration Formal specifications data flow graphs high level synthesis

来源：评论

学校读者我要写书评

暂无评论

On k-sum optimization

引用

OPERATIONS RESEARCH LETTERS 1996年第5期18卷 233-236页

作者： Punnen, AP Aneja, YP UNIV WINDSOR FAC BUSINESS ADMWINDSORON N9B 3P4CANADA UNIV NEW BRUNSWICK DEPT MATH STAT & COMP SCIST JOHNSNB E2L 4L5CANADA

The k-sum optimization problem (KSOP) is the combinatorial problem of finding a solution such that the sum of the weights or the ii largest weighted elements of the solution is as small as possible. KSOP simultaneously generalizes both bottleneck and minsum problems. We show that KSOP can be solved in polynomial time whenever an associated minsum problem can be solved in polynomial time. Further we show that if the minsum problem is solvable by a polynomial time epsilon-approximation scheme then KSOP can also be solved by a polynomial time epsilon-approximation scheme.

关键词： combinatorial optimization graphs polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Finding edge-disjoint paths in partial k-trees 7th

Finding edge-disjoint paths in partial k-trees

引用

7th Annual International Symposium on algorithms and Computation

作者： Zhou, XA Tamura, S Nishizeki, T Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 98077 Japan

ISBN: (纸本)3540620486

For a given graph G and p pairs (s(i), t(i)), 1 less than or equal to i less than or equal to p, of vertices in G, the edge-disjoint paths problem is to find p pairwise edge-disjoint paths P-i 1 less than or equal to i less than or equal to p, connecting s(i) and t(i). Many combinatorial problems can be efficiently solved for partial k-trees (graphs of treewidth bounded by a fixed integer k), but it has not been known whether the edge-disjoint paths problem can be solved in polynomial time for partial k-trees unless p = O(1). This paper gives two algorithms for the edge-disjoint paths problem on partial k-trees. The first one solves the problem for any partial k-tree G and runs in polynomial time if p = O(log n) and in linear time if p = O(1), where n is the number of vertices in G. The second one solves the problem under some restriction on the location of terminal pairs even if p greater than or equal to log n.

关键词： edge-disjoint paths partial k-tree bounded tree-width polynomial-time algorithm edge-coloring

来源：评论

学校读者我要写书评

暂无评论

A NOTE ON SINGLE-PROCESSOR SCHEDULING WITH time-DEPENDENT EXECUTION timeS

引用

OPERATIONS RESEARCH LETTERS 1995年第3期17卷 127-129页

作者： CHEN, ZL Department of Civil Engineering and Operations Research Princeton University Princeton NJ 08544 USA

We consider a single-processor scheduling model where the execution time of a task is a decreasing linear function of its starting time. The complexity of the problem of minimizing the number of late tasks remains unknown for a set of tasks with identical due dates. We present an O(n(2))-time dynamic programming algorithm for solving this problem.

关键词： SCHEDULING SINGLE-PROCESSOR DYNAMIC PROGRAMMING polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A QUADRATICALLY CONVERGENT O((KAPPA+1)ROOT-N L)-ITERATION algorithm FOR THE P-ASTERISK(KAPPA)-MATRIX LINEAR COMPLEMENTARITY-PROBLEM

引用

MATHEMATICAL PROGRAMMING 1995年第3期69卷 355-368页

作者： MIAO, JM RUTCOR — Rutgers Center for Operations Research Rutgers University New Brunswick United States

An interior-point predictor-corrector algorithm for the P*(kappa)-matrix linear complementarity problem is proposed. The algorithm is an extension of Mizuno-Todd-Ye's predictor-corrector algorithm for linear programming problem. The extended algorithm is quadratically convergent with iteration complexity O((kappa + 1)root nL). It is the first polynomially and quadratically convergent algorithm for a class of LCPs that are not necessarily monotone.

关键词： LINEAR COMPLEMENTARITY PROBLEM INTERIOR-POINT algorithm QUADRATIC CONVERGENCE polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

ON THE CONSECUTIVE-RETRIEVAL PROBLEM

引用

SIAM JOURNAL ON COMPUTING 1994年第2期23卷 398-414页

作者： SWAMINATHAN, R WAGNER, DK OFF NAVAL RES DIV MATH SCI ARLINGTON VA 22217 USA

A {0, 1}-matrix M has the consecutive-retrieval property if there exists a tree T such that the vertices of T are indexed on the rows of M and the columns of M are the incidence vectors of the vertex sets of paths of T. If such a T exists, then T is a realization for M. In this paper, an O(r2c) algorithm is presented to determine whether a given standard, r x c matrix has the consecutive-retrieval property and, if so, to construct a realization.

关键词： CONSECUTIVE-RETRIEVAL PROPERTY TREE REALIZATION MATRIX DECOMPOSITION polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：