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

An efficient retrieval selection algorithm for video servers with random duplicated assignment storage technique

INFORMATION PROCESSING LETTERS 2002年第6期83卷 315-321页

作者： Low, CP Nanyang Technol Univ Sch Elect & Elect Engn Singapore 639798 Singapore

Random Duplicated Assignment (RDA) is an approach in which video data is stored by assigning a number of copies of each data block to different, randomly chosen disks. It has been shown that this approach results in smaller response times and lower disk and RAM costs compared to the well-known disk stripping techniques. Based on this storage approach, one has to determine, for each given batch of data blocks, from which disk each of the data blocks is to be retrieved. This is to be done in such a way that the maximum load of the disks is minimized. The problem is called the Retrieval Selection Problem (RSP). In this paper, we propose a new efficient algorithm for RSP. This algorithm is based on the breadth-first search approach and is able to guarantee optimal solutions for RSP in O(n(2) + mn), where m and n correspond to the number of data blocks and the number of disks, respectively. We will show that our proposed algorithm has a lower time complexity than an existing algorithm, called the MFS algorithm. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： random duplicated assignment breadth-first search polynomial-time algorithms load balancing algorithms

来源：评论

学校读者我要写书评

暂无评论

Critical (P5, bull)-free graphs

引用

DISCRETE APPLIED MATHEMATICS 2023年第1期334卷 15-25页

作者： Huang, Shenwei Li, Jiawei Xia, Wen Nankai Univ Coll Comp Sci Tianjin 300071 Peoples R China Nankai Univ Tianjin Key Lab Network & Data Secur Technol Tianjin 300071 Peoples R China

Given two graphs H1 and H2, a graph is (H1, H2)-free if it contains no induced subgraph isomorphic to H1 or H2. Let Pt be the path on t vertices. A bull is the graph obtained from a triangle with two disjoint pendant edges. In this paper, we show that there are finitely many 5-vertex-critical (P5, bull)-free graphs.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Coloring Critical graphs Forbidden induced subgraphs Strong perfect graph theorem polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

THE COMPLEXITY OF FINDING MINIMUM-LENGTH GENERATOR SEQUENCES

引用

THEORETICAL COMPUTER SCIENCE 1985年第2-3期36卷 265-289页

作者： JERRUM, MR Department of Computer Science University of Edinburgh Edinburgh EH9 2JZ Scotland United Kingdom

The computational complexity of the following problem is investigated: Given a permutation group specified as a set of generators, and a single target permutation which is a member of the group, what is the shortest expression for the target permutation in terms of the generators? The general problem is demonstrated to be PSppace -complete and, indeed,is shown to remain so even when the generator set is restricted to contain only two permutations. The restriction on generator set cardinality is the best possible, as the problem becomes soluble in polynomial time if the generator set cantains only one permutation. An interesting feature of this problem is that it does not fall under the headings of ‘two person games’ or ‘formal languages’ which cover the great majority of known PSpace -complete problems. Some restricted versions of the problem, in which the generator set is fixed rather than being part of the problem instance, are also investigated and shown to be computationally tractable. One result of this kind is that determining the most compact expression of a permutation in terms of ‘cyclicly adjacent transpositions’ can be achieved in polynomial time. Thus, from an initial arrangement of distinct objects on a circle, one can quickly compute the smallest number of interchanges of adjacent objects required to realise any other arrangement. Surprisingly, this problem appears substantially more difficult to solve than the related one (for which a solution has been known for some time) in which the objects are arranged on a line segment.

关键词： Computational complexity permutation groups polynomial-time algorithms PSpace -completeness

来源：评论

学校读者我要写书评

暂无评论

polynomial algorithms FOR LP OVER A SUBRING OF THE ALGEBRAIC-INTEGERS WITH APPLICATIONS TO LP WITH CIRCULANT MATRICES

引用

MATHEMATICAL PROGRAMMING 1992年第2期57卷 121-143页

作者： ADLER, I BELING, PA 1. Department of Industrial Engineering and Operations Research University of California 94720 Berkeley CA USA

We show that a modified variant of the interior point method can solve linear programs (LPs) whose coefficients are real numbers from a subring of the algebraic integers. By defining the encoding size of such numbers to be the bit size of the integers that represent them in the subring, we prove the modified algorithm runs in time polynomial in the encoding size of the input coefficients, the dimension of the problem, and the order of the subring. We then extend the Tardos scheme to our case, obtaining a running time which is independent of the objective and right-hand side data. As a consequence of these results, we are able to show that LPs with real circulant coefficient matrices can be solved in strongly polynomial time. Finally, we show how the algorithm can be applied to LPs whose coefficients belong to the extension of the integers by a fixed set of square roots.

关键词： LINEAR PROGRAMMING polynomial-time algorithms STRONGLY polynomial-time algorithms CIRCULANT MATRICES ALGEBRAIC NUMBERS

来源：评论

学校读者我要写书评

暂无评论

Reconfiguration models and algorithms for stateful interactive processes

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1999年第3期25卷 401-415页

作者： Varvarigou, TA Anagnostou, ME Ahuja, SR Natl Tech Univ Athens Dept Elect Engn & Comp Sci GR-15773 Athens Greece AT&T Bell Labs Lucent Technol Murray Hill NJ 07974 USA

In this paper, we present new results in the area of reconfiguration of stateful interactive processes in the presence of faults. More precisely, we consider a set of servers/processes that have the same functionality, i.e., are able to perform the same tasks and provide the same set of services to their clients. In the case when several of them turn out to be faulty, we want to reconfigure the system so that the clients of the faulty servers/processes are served by some other, fault-free, servers of the system in a way that is transparent to all the system clients. We propose a new method for reconfiguring in the presence of faults: compensation paths. Compensation paths are an efficient way of shifting spare resources from where they are available to where they are needed. We also present optimal and suboptimal simple reconfiguration algorithms of low polynomial time complexity O(nmlog(n(2)/m)) for the optimal and O(m) for the suboptimal algorithms, where M is the number of processes and m is the number of primary-backup relationships. The optimal algorithms compute the way to reconfigure the system whenever the reconfiguration is possible. The suboptimal algorithms may sometimes fail to reconfigure the system, although reconfiguration would be possible by using the optimal centralized algorithms. However, suboptimal algorithms have other competitive advantages over the centralized optimal algorithms with regard to time complexity and communication overhead.

关键词： reconfiguration of stateful processes compensation paths polynomial-time algorithms optimal centralized algorithms suboptimal distributed and hybrid algorithms

来源：评论

学校读者我要写书评

暂无评论

Computation of the Highest Coefficients of Weighted Ehrhart Quasi-polynomials of Rational Polyhedra

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2012年第4期12卷 435-469页

作者： Baldoni, V. Berline, N. De Loera, J. A. Koeppe, M. Vergne, M. Univ Calif Davis Dept Math Davis CA 95616 USA Univ Roma Tor Vergata Dipartimento Matemat I-00133 Rome Italy Ecole Polytech Ctr Math Laurent Schwartz F-91128 Palaiseau France Inst Math Jussieu Theorie Grp F-75251 Paris 05 France

This article concerns the computational problem of counting the lattice points inside convex polytopes, when each point must be counted with a weight associated to it. We describe an efficient algorithm for computing the highest degree coefficients of the weighted Ehrhart quasi-polynomial for a rational simple polytope in varying dimension, when the weights of the lattice points are given by a polynomial function h. Our technique is based on a refinement of an algorithm of A. Barvinok in the unweighted case (i.e., ha parts per thousand 1). In contrast to Barvinok's method, our method is local, obtains an approximation on the level of generating functions, handles the general weighted case, and provides the coefficients in closed form as step polynomials of the dilation. To demonstrate the practicality of our approach, we report on computational experiments which show that even our simple implementation can compete with state-of-the-art software.

关键词： Ehrhart functions Exponential sums and integrals Intermediate sums polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Finding minimal siphons in general Petri nets

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 1996年第11期E79A卷 1817-1824页

作者： Tanimoto, S Yamauchi, M Watanabe, T Department of Circuits and Systems Faculty of Engineering Hiroshima University Higashi-Hiroshima-shi 739 Japan

A siphon (or alternatively a structural deadlock) of a Petri net is defined as a set S of places such that existence of any edge from a transition t to a place of S implies that there is an edge from some place of S to t. A minimal siphon is a siphon such that any proper subset is not a siphon. The results of the paper are as follows. (1) The problem of deciding whether or not a given Petri net has a minimum siphon (i.e., a minimum-cardinality minimal siphon) is NP-complete. (2) A polynomial-time algorithm to find, if any, a minimal siphon or even a maximal class of mutually disjoint minimal siphons of a general Petri net is proposed.

关键词： general Petri nets minimal siphons polynomial-time algorithms strongly connectedness NP-completeness

来源：评论

学校读者我要写书评

暂无评论

Complexity of single machine scheduling subject to nonnegative inventory constraints

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第2期207卷 605-619页

作者： Briskorn, Dirk Choi, Byung-Cheon Lee, Kangbok Leung, Joseph Pinedo, Michael Univ Cologne Wirtschafts & Sozialwissensch Fak D-50923 Cologne Germany Chungnam Natl Univ Dept Business Adm Taejon 305704 South Korea NYU Stern Sch Business New York NY 10012 USA New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA

This paper focuses on single machine scheduling subject to inventory constraints. Jobs either add items to an inventory or remove items from that inventory. Jobs that have to remove items cannot be processed if the required number of items is not available. We consider scheduling problems on a single machine with the minimization of the total weighted completion time, the maximum lateness, and the number of tardy jobs, respectively, as objective and determine their computational complexity. Since the general versions of our problems turn out to be strongly NP-hard, we consider special cases by assuming that different jobs have certain parameter values in common. We determine the computational complexity for all special cases when the objective is either to minimize total completion time or to minimize maximum lateness and for several special cases when the objective is either to minimize total weighted completion time or to minimize the number of tardy jobs. (C) 2010 Elsevier BM. All rights reserved.

关键词： Machine scheduling Inventory constraints Computational complexity Strong NP-hardness polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

A polynomial projection-type algorithm for linear programming

引用

OPERATIONS RESEARCH LETTERS 2014年第1期42卷 91-96页

作者： Vegh, Laszlo A. Zambelli, Giacomo Univ London London Sch Econ & Polit Sci Dept Management London WC2A 2AE England

We propose a simple O(vertical bar n(5)/log n vertical bar L) algorithm for linear programming feasibility, that can be considered as a polynomial-time implementation of the relaxation method. Our work draws from Chubanov's "Divide-and-Conquer" algorithm (Chubanov, 2012), with the recursion replaced by a simple and more efficient iterative method. A similar approach was used in a more recent paper of Chubanov (2013). (C) 2014 Elsevier B.V. All rights reserved.

关键词： Linear programming polynomial-time algorithms Relaxation method

来源：评论

学校读者我要写书评

暂无评论

Extracting minimal siphon-traps of Petri nets and its application to computing nonnegative integer-invariants

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2002年第11期E85A卷 2436-2446页

作者： Taoka, S Takano, K Watanabe, T Hiroshima Univ Grad Sch Engn Higashihiroshima 7398527 Japan Hitachi Software Engn Co Yokohama Kanagawa Japan

A siphon-trap of a Petri net N is defined as a place set S with S-. = S-., where S-.={u\ N has an edge from u to a vertex of S} and S-. = {v\ N has an edge from a vertex of S to v}. A minimal siphon-trap is a siphon-trap such that any proper subset is not a siphon-trap. The following polynomial-time algorithms are proposed: 1. FDST for finding, if any, a minimal siphon-trap or even a maximal class of mutually disjoint minimal siphon-traps of a given Petri net;2. FDSTi that repeats FDST i times in order to extract more minimal siphon-traps than FDST. 3. STFM-T (STFM-T-i, respectively) which is a combination of the Fourier-Motzkin method and FDST (FDSTi) and which has high possibility of finding, if any, at least one minimal-support nonnegative integer invariant.

关键词： Petri nets minimal siphon-traps Fourier-Motzkin method invariant computation polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：