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

The longest common subsequence problem for sequences with nested arc annotations

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2002年第3期65卷 465-480页

作者： Lin, GH Chen, ZZ Jiang, T Wen, JJ Univ Calif Riverside Dept Comp Sci Riverside CA 92521 USA Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Tokyo Denki Univ Dept Math Sci Hatoyama Saitama 3500394 Japan

Arc-annotated sequences are useful in representing the structural information of RNA and protein sequences. The LONGEST ARC-PRESERVING COMMON SUBSEQUENCE (LAPCS) Problem has been introduced in Evans (algorithms and complexity for annotated sequence analysis, Ph.D. Thesis, University of Victoria, 1999) as a framework for studying the similarity of arc-annotated sequences. Several algorithmic and complexity results on the LAPCS problem have been presented in Evans (1999) and Jiang et al. (in: Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching (CPM 2000), Lecture Note in Computer Science, Vol. 1848, 2000, pp. 154-165). In this paper, we continue this line of research and present new algorithmic and complexity results on the LAPCS problem restricted to two nested arc-annotated sequences, denoted as LAPCS(NESTED, NESTED). The restricted problem is perhaps the most interesting variant of the LAPCS problem and has important applications in the comparison of RNA secondary structures. Particularly, we prove that LAPCS(NESTED, NESTED) is NP-hard, which answers an open question in Evans (1999). We then present a polynomial-time approximation scheme for LAPCS(NESTED, NESTED) with an additional c-diagonal restriction. An interesting special case, UNARY LAPCS(NESTED, NESTED), is also investigated, for which we show the NP-hardness and present a better approximation algorithm, than the one for general LAPCS(NESTED, NESTED). (C) 2002 Elsevier Science (USA). All rights reserved.

关键词： sequence annotation longest common subsequence book embedding NP-hardness approximation algorithm polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

algorithm for computing a convex and simple path of bounded curvature in a simple polygon

引用

algorithmICA 2002年第2期34卷 109-156页

作者： Boissonnat, JD Ghosh, SK Kavitha, T Lazard, S INRIA PRISME F-06902 Sophia Antipolis France Tata Inst Fundamental Res Sch Comp Sci Bombay 400005 Maharashtra India INRIA Lorraine F-54602 Villers Les Nancy France

In this paper we study the collision-free path planning problem for a point robot, whose path is of bounded curvature (i.e., constrained to have curvature at most 1), moving in the plane inside an n-sided simple polygon P. Given two points s and t inside P and two directions of travel, one at s and one at t, the problem is to compute a convex and simple path of bounded curvature inside P from s to t consisting of straight-line segments and circular arcs such that (i) the radius of each circular arc is at least 1, (ii) each segment on the path is the tangent between the two consecutive circular arcs on the path, (iii) the given initial direction at s is tangent to the path at s and (iv) the given final direction at t is tangent to the path at t. We propose an 0(n(4)) time algorithm for this problem. Using the notion of complete visibility, P is pruned to another polygon P' such that any convex and simple path from s to t inside P also remains inside P'. Then our algorithm constructs the locus of center of a circle of unit radius translating along the boundary of P and, using this locus, the algorithm constructs a convex and simple path of bounded curvature. Our algorithm is based on the relationship between the Euclidean shortest path, link paths and paths of bounded curvature, and uses several properties derived here on convex and simple paths of bounded curvature. We also show that the path computed by our algorithm can be transformed in 0(n) time to a minimal convex and simple path of bounded curvature. Using this transformation and two necessary conditions proposed here for the shortest convex and simple path of bounded curvature, a minimal bounded curvature path is located in 0(n4) time whose length, except in special situations involving arcs of length greater than pi, is at most twice the length of a shortest convex and simple path of bounded curvature.

关键词： non-holonomic motion planning curvature constrained path Euclidean shortest path link path visibility approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An efficient distributed algorithm for constructing small dominating sets

引用

DISTRIBUTED COMPUTING 2002年第4期15卷 193-205页

作者： Jia, LJ Rajaraman, R Suel, T Northeastern Univ Coll Comp Sci Boston MA 02115 USA Polytech Univ Dept Comp & Informat Sci Brooklyn NY 11201 USA

The dominating set problem asks for a small subset D of nodes in a graph such that every node is either in D or adjacent to a node in D. This problem arises in a number of distributed network applications, where it is important to locate a small number of centers in the network such that every node is nearby at least one center. Finding a dominating set of minimum size is NP-complete, and the best known approximation is logarithmic in the maximum degree of the graph and is provided by the same simple greedy approach that gives the well-known logarithmic approximation result for the closely related set cover problem. We describe and analyze new randomized distributed algorithms for the dominating set problem that run in polylogarithmic time, independent of the diameter of the network, and that return a dominating set of size within a logarithmic factor from optimal, with high probability. In particular, our best algorithm runs in O (log n log, Delta) rounds with high probability, where n is the number of nodes, Delta is one,plus the maximum degree of any node, and each round involves a constant number of message exchanges among any two neighbors;the size of the dominating set obtained is within O (log Delta) of the optimal in expectation and within O(log n) of the optimal with high probability. We also describe generalizations to the weighted case and the case of multiple covering requirements.

关键词： dominating set distributed computing approximation algorithm ad hoc network

来源：评论

学校读者我要写书评

暂无评论

Single machine scheduling with release dates

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2002年第2期15卷 165-192页

作者： Goemans, MX Queyranne, M Schulz, AS Skutella, M Wang, YG MIT Dept Math Cambridge MA 02139 USA CORE Louvain Belgium Univ British Columbia Fac Commerce & Business Adm Vancouver BC V6T 1Z2 Canada MIT Alfred P Sloan Sch Management Cambridge MA 02139 USA Tech Univ Berlin Dept Math D-1000 Berlin Germany Tech Univ Berlin Inst Math Fak Math & Nat Wissensch 2 D-10623 Berlin Germany Peoplesoft Inc Pleasanton CA 94588 USA

We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We first study two linear programming relaxations of the problem, one based on a time-indexed formulation, the other on a completion-time formulation. We show their equivalence by proving that a O(n log n) greedy algorithm leads to optimal solutions to both relaxations. The proof relies on the notion of mean busy times of jobs, a concept which enhances our understanding of these LP relaxations. Based on the greedy solution, we describe two simple randomized approximation algorithms, which are guaranteed to deliver feasible schedules with expected objective function value within factors of 1.7451 and 1.6853, respectively, of the optimum. They are based on the concept of common and independent alpha-points, respectively. The analysis implies in particular that the worst-case relative error of the LP relaxations is at most 1.6853, and we provide instances showing that it is at least e/(e-1) approximate to 1.5819. Both algorithms may be derandomized;their deterministic versions run in O(n(2)) time. The randomized algorithms also apply to the on-line setting, in which jobs arrive dynamically over time and one must decide which job to process without knowledge of jobs that will be released afterwards.

关键词： approximation algorithm LP relaxation scheduling on-line algorithm

来源：评论

学校读者我要写书评

暂无评论

A quasi-solution state evolution algorithm for channel assignment problems in cellular networks

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2002年第5期E85A卷 977-987页

作者： Funabiki, N Nakanishi, T Yokohira, T Tajima, S Higashino, T Okayama Univ Dept Commun Network Engn Okayama 7008530 Japan Osaka Univ Dept Informat & Math Sci Toyonaka Osaka 5608531 Japan

For efficient use of limited electromagnetic wave resource, the assignment of communication channels to call requests is very important in a cellular network. This task has been formulated as an NP-hard combinatorial optimization problem named the channel assignment problem (CAP). Given a cellular network and a set of call requests, CAP requires to find a channel assignment to the call requests such that three types of interference constraints between channels are not only satisfied, but also the number of channels (channel span) is minimized. This paper presents an iterative search approximation algorithm for CAP, called the Quasi-solution state evolution algorithm for CAP (QCAP). To solve hard CAP instances in reasonable time, QCAP evolutes quasi-solution states where a subset of call requests are assigned channels and no more request can be satisfied without violating the constraint QCAP is composed of three stages. The first stage computes the lower bound on the channel span for a given instance. After the second stage greedily generates an initial quasi-solution state, the third stage evolutes them for a feasible channel assignment by iteratively generating best neighborhoods, with help of the dynamic state jump and the gradual span expansion for global convergence. The performance of QCAP is evaluated through solving benchmark instances in literature, where QCAP always finds the optimum or near-optimum solution in very short time. Our simulation results confirm the extensive search capability and the efficiency of QCAP.

关键词： CAP approximation algorithm benchmark NP-hard cellular network

来源：评论

学校读者我要写书评

暂无评论

A min-max theorem on feedback vertex sets

引用

MATHEMATICS OF OPERATIONS RESEARCH 2002年第2期27卷 361-371页

作者： Cai, MC Deng, XT Zang, WN Acad Sinica Inst Syst Sci Acad Math & Syst Sci Beijing 100080 Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Univ Hong Kong Dept Math Hong Kong Hong Kong Peoples R China

We establish a necessary and sufficient condition for the linear system {x : Hx greater than or equal to e, x greater than or equal to 0} associated with a bipartite tournament to be totally dual integral, where H is the cycle-vertex incidence matrix and e is the all-one vector. The consequence is a min-max relation on packing and covering cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem on the corresponding bipartite tournaments. In addition, we show that the feedback vertex set problem on general bipartite tournaments is NP-complete and approximable within 3.5 based on the min-max theorem.

关键词： feedback vertex set bipartite tournament totally dual integrality min-max relation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimizing electronic line terminals for automatic ring protection in general WDM optical networks

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2002年第1期20卷 183-189页

作者： Calinescu, G Frieder, O Wang, PJ IIT Dept Comp Sci Chicago IL 60616 USA

Automatic ring protection provides simple and rapid fault protection and restoration in telecommunication networks. To implement the automatic ring protection in general wavelength-division multiplexing (WDM) optical networks, the lightpaths are partitioned into groups each of which can be carried in a simple cycle of the underlying network. As the electronic line terminals are the dominant cost factor in the deployment of WDM optical networks, we study how to generate these partitions with minimum electronic line terminals. This optimization problem is NP-hard. We develop two polynomial-time approximation algorithms, with performance guarantees between 1.5 and 1.6 and between 1.5 and 1.5 + epsilon, respectively. The second algorithm can be adapted, with the same performance guarantees, to the problem in which lightpaths are not prespecified and only the endpoints of each connection are given. Both algorithms can be easily adapted, with the same performance guarantees, to the problem in which only link protection is desired, and each group must be carried in a closed trail. The first algorithm matches and the second algorithm improves the approximation ratio obtained independently by Eilam et al. (2000).

关键词： approximation algorithm automatic ring protection lightpath traffic grooming

来源：评论

学校读者我要写书评

暂无评论

Minimizing service and operation costs of periodic scheduling

引用

MATHEMATICS OF OPERATIONS RESEARCH 2002年第3期27卷 518-544页

作者： Bar-Noy, A Bhatia, R Naor, JS Schieber, B Brooklyn Coll Comp & Informat Sci Dept Brooklyn NY 11210 USA Bell Labs Lucent Technol Murray Hill NJ 07974 USA Technion Dept Comp Sci IL-32000 Haifa Israel IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA

We study the problem of scheduling activities of several types under the constraint that, at most, a fixed number of activities can be scheduled in any single time slot An given activity type is associated with a service cost and an operating cost that increases linearly with the number of time slots since the last service of this typed The problem is to find an optimal schedule that minimizes the long-run average cost per time slot. Applications of such a model are the scheduling of maintenance service to machines, multi-item replenishment of stock, and minimizing the mean response time in Broadcast Disks. Broadcast Disks recently gained a lot of attention because they were used to model backbone communications in wireless systems, Teletext systems, and Web caching in satellite systems. The first contribution of this paper is the definition of a general model that combines into one several important previous models We prove that an optimal cyclic schedule for the general problem exists, and we establish the NP-hardness of the problem. Next, we formulate a nonlinear program that relaxes the optimal schedule and serves as a lower bound on the cost of an optimal schedule, We present an efficient algorithm for finding a near-optimal solution to the nonlinear program. We use this solution to obtain several approximation algorithms. (1) A 9/8 approximation for a variant of the problem that models the Broadcast Disks application, The algorithm uses some propertied of "Fibonacci sequences," Using this sequence, we present a 1.57-approximation algorithm for the general problem. (2) A simple randomized algorithm and a simple deterministic greedy algorithm for the problem. We prove that both achieve approximation factor of 2. To the best of our knock ledge this is the first worst-case analysis of a widely used greedy heuristic for this problem.

关键词： scheduling maintenance service broadcast disk cyclic schedule approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Splittable traffic partition in WDM/SONET rings to minimize SONET ADMs

引用

THEORETICAL COMPUTER SCIENCE 2002年第1-2期276卷 33-50页

作者： Calinescu, G Wan, PJ IIT Dept Comp Sci Chicago IL 60616 USA

SONET ADMs are the dominant cost factor in the WDM/SONET rings. Recently several articles (Belvaux et al., European J. Oper. Res. 108 (1) (1998) 26-35;Calinescu and Wan, Traffic partition in WDM/SONET rings to minimize SONET ADMs, submitted for publication;Gerstel et al., Proc. IEEE INFOCOM'98, vol. 1, pp. 94-101;Liu et al., Proc. INFOCOM, vol. 2, 2000, pp. 1020-1025;Sutter et al., Oper. Res. 46 (5) (1998) 719-728) proposed a number of heuristics for traffic partition so as to use as few SONET ADMs as possible. Most of these heuristics assumes wavelength-continuity, i.e., the same wavelength is allocated on all of the links in the path established for a traffic stream. It was first observed and argued by Gerstel et al. that the number of ADMs can be potentially reduced by allowing a traffic stream to be locally transferred from one ADM in a wavelength to another ADM in a different wavelength at any intermediate node, in other words, the traffic streams are splittable. In this paper, we study two variations of this minimum ADM problem with splittable traffic streams: all traffic streams have prespecified routings, and all traffic streams have no prespecified routings respectively. Both variations are shown to be NP-hard. For the former variation, a heuristic with approximation ratio at most 5/4 is proposed. For the latter variation, a similar heuristic with approximation ratio 3/2 is proposed. (C) 2002 Published by Elsevier Science B.V.

关键词： approximation algorithm wavelength division multiplexing (WDM) optical networks synchronous optical networks (SONET) add-drop multiplexer (ADM)

来源：评论

学校读者我要写书评

暂无评论

Additive bounding, worst-case analysis, and the breakpoint median problem

引用

SIAM JOURNAL ON OPTIMIZATION 2002年第2期13卷 508-519页

作者： Caprara, A Univ Bologna DEIS I-40136 Bologna Italy

We analyze the worst-case performance of a simple algorithm for the breakpoint median problem (BMP), a well-known problem in computational biology. BMP is the special case of the min-cost traveling salesman problem on a complete graph G = (V, E), in which the edge cost vector c is an element of R-E has the form 1 - x*, with x* a convex combination of the incidence vectors of the Hamiltonian circuits of G. The performance guarantee shown is 5/3, which improves on the previously known guarantee of 2. We also consider the signed variant of BMP and prove that a similar approach yields a performance guarantee of 3/2 (again improving over the previously known 2). Our proofs are based on formulating the problem as a suitable integer linear program and then defining a feasible dual solution for the associated linear programming relaxation in two phases, in a so-called additive bounding fashion.

关键词： breakpoint median problem approximation algorithm linear programming additive bounding traveling salesman problem perfect matching

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：