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

approximation properties of haplotype tagging

BMC BIOINFORMATICS 2006年第1期7卷 8-8页

作者： Vinterbo, SA Dreiseitl, S Ohno-Machado, L Brigham & Womens Hosp Decis Syst Grp Boston MA 02115 USA Harvard Univ Sch Med Boston MA USA Harvard Mit Div Hlth Sci & Technol Boston MA USA Upper Austria Univ Appl Sci Dept Software Engn Hagenberg Austria

Single nucleotide polymorphisms (SNPs) are locations at which the genomic sequences of population members differ. Since these differences are known to follow patterns, disease association studies are facilitated by identifying SNPs that allow the unique identification of such patterns. This process, known as haplotype tagging, is formulated as a combinatorial optimization problem and analyzed in terms of complexity and approximation properties. Results: It is shown that the tagging problem is NP-hard but approximable within 1 + ln((n(2) - n)/ 2) for n haplotypes but not approximable within (1 - epsilon) ln(n/2) for any epsilon > 0 unless NP subset of DTIME(n(log) (log n)). A simple, very easily implementable algorithm that exhibits the above upper bound on solution quality is presented. This algorithm has running time O(np/2(2m - p + 1)) <= O(m(n(2) - n)/2) where p <= min(n, m) for n haplotypes of size m. As we show that the approximation bound is asymptotically tight, the algorithm presented is optimal with respect to this asymptotic bound. Conclusion: The haplotype tagging problem is hard, but approachable with a fast, practical, and surprisingly simple algorithm that cannot be significantly improved upon on a single processor machine. Hence, significant improvement in computatational efforts expended can only be expected if the computational effort is distributed and done in parallel.

关键词： approximation algorithm Polynomial Time Polynomial Time Reduction Disease Association Study Polynomial Time Computable Function

来源：评论

学校读者我要写书评

暂无评论

The expected size of the Rule k dominating set

The expected size of the Rule <i>k</i> dominating set

引用

10th Workshop on the Analysis of algorithms

作者： Hansen, Jennie C. Schmutz, Eric Sheng, Li Heriot Watt Univ Actuarial Math & Stat Dept Edinburgh EH14 4AS Midlothian Scotland Drexel Univ Dept Math Philadelphia PA 19104 USA

Dai, Li, and Wu proposed Rule k, a localized approximation algorithm that attempts to find a small connected dominating set in a graph. In this paper we consider the "average-case" performance of two closely related versions of Rule k for the model of random unit disk graphs constructed from n random points in an l(n) x l(n) square. We show that if k >= 3 and l(n) = o(root n), then for both versions of Rule k, the expected size of the Rule k dominating set is a Theta(l(n)(2)) as n > infinity. It follows that, for l(n) in a suitable range, the expected size of the Rule k dominating sets are within a constant factor of the optimum.

关键词： dominating set localized algorithm approximation algorithm performance analysis probabilistic analysis Rule k unit disk graph

来源：评论

学校读者我要写书评

暂无评论

On load-balanced semi-matchings for weighted bipartite graphs

On load-balanced semi-matchings for weighted bipartite graph...

引用

3rd International Conference on Theory and Applications of Models of Computation (TAMC 2006)

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

ISBN: (纸本)3540340211

A semi-matching on a bipartite graph G = (U boolean OR V, E) is a set of edges X C E such that each vertex in U is incident to exactly one edge in X. The sum of the weights of the vertices from U that are assigned (semi-matched) to some vertex v G V is referred to as the load of vertex v. In this paper, we consider the problem to finding a semi-matching that minimizes the maximum load among all vertices in V. This problem has been shown to be solvable in polynomial time by Harvey et. al.[3] and Fakcharoenphol et. al.[5] for unweighted graphs. However, the computational complexity for the weighted version of the problem was left as an open problem. In this paper, we prove that the problem of finding a semi-matching that minimizes the maximum load among all vertices in a weighted bipartite graph is NP-complete. A 3/2-approximation algorithm is proposed for this problem.

关键词： semi-matching bipartite graphs load balancing NP-hard approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Online-Optimization of Large-Scale Vehicle Dispatching Problems

引用

Electronic Notes in Discrete Mathematics 2006年第SPEC. ISS.期25卷 145-146页

作者： Saliba, Sleman Krumke, Sven O. Westphal, Stephan Department of Mathematics University of Kaiserslautern D-67653 Kaiserslautern P.O.Box 3049 Germany Department of Mathematics University of Kaiserslautern D-67653 Kaiserslautern P.O.Box 3049 Germany Department of Mathematics University of Kaiserslautern D-67653 Kaiserslautern P.O.Box 3049 Germany

In this talk we investigate a real-world large scale vehicle routing problem posed by our cooperation partner, the German Automobile Association (ADAC). Service vunits are requested to assist people whose cars break down. Such service requests arrive online. The goal is to route the requests to service vehicles such that low operational costs and good quality of service is provided (soft time windows). Currently, a column generation approach is used to solve the offline problem, in which only known requests are considered. In order to speed up the column generation, we need to start with "good" short routes. We will show that that this problem is NP-hard even for two requests per service unit. Moreover, we present an approximation algorithm with a constant-factor approximation rate even with nonlinear lateness costs for violating the soft time windows. © 2006 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Online Optimization Vehicle Routing

来源：评论

学校读者我要写书评

暂无评论

Augmenting forests to meet odd diameter requirements

引用

14th Annual International Symposium on algorithms and Computation

作者： Ishii, Toshimasa Yamamoto, Shigeyuki Nagamochi, Hiroshi Toyohashi Univ Technol Dept Informat & Comp Sci Aichi 4418580 Japan I FOR COM Co Ltd Kanagawa 2200207 Japan Kyoto Univ Dept Appl Math & Phys Grad Sch Informat Kyoto 6068501 Japan

ISBN: (纸本)9783540206958

Given a graph G = (V, E) and an integer D >= 1, we consider the problem of augmenting G by the smallest number of new edges so that the diameter becomes at most D. It is known that no constant approximation algorithms to this problem with an arbitrary graph G can be obtained unless P = NP. For a forest G and an odd D >= 3, it was open whether the problem is approximable within a constant factor. In this paper, we give the first constant factor approximation algorithm to the problem with a forest G and an odd D;our algorithm delivers an 8-approximate solution in O(vertical bar V vertical bar(3)) time. We also show that a 4-approximate solution to the problem with a forest G and an odd D can be obtained in linear time if the augmented graph is additionally required to be biconnected. (c) 2006 Elsevier B.V. All rights reserved.

关键词： undirected graph graph augmentation problem diameter forest approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Probabilistic Verification and approximation

引用

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2006年 143卷 101-114页

作者： Lassaigne, Richard Peyronnet, Sylvain Univ Paris 07 CNRS Equipe Logique Math UMR 7056 Paris France EPITA Res & Dev Lab LRDE Paris France

Model checking is an algorithmic method allowing to automatically verify if a system which is represented as a Kripke model satisfies a given specification. Specifications are usually expressed by formulas of temporal logic. The first objective of this paper is to give an overview of methods able to verify probabilistic systems. Models of such systems are labelled discrete time Markov chains and specifications are expressed in extensions of temporal logic by probabilistic operators. The second objective is to focus on the complexity of these methods and to answer the question: can probabilistic verification be efficiently approximated? In general, the answer is negative. However, in many applications, the specification formulas can be expressed in some positive fragment of linear time temporal logic. In this paper, we show how some simple randomized approximation algorithms can improve the efficiency of the verification of such probabilistic specifications.

关键词： Probabilistic Verification approximation algorithm Model Checking

来源：评论

学校读者我要写书评

暂无评论

Approximating the minimum number of maximum power users in ad hoc networks

Approximating the minimum number of maximum power users in a...

引用

3rd International Conference on Ad-Hoc, Mobile and Wireless Networks

作者： Lloyd, Errol L. Liu, Rui Ravi, S. S. Univ Delaware Dept Comp & Informat Sci Newark DE 19716 USA SUNY Albany Dept Comp Sci Albany NY 12222 USA

ISBN: (纸本)9783540286349

Topology control is the problem of assigning transmission power values to the nodes of an ad hoc network so that the induced graph satisfies some specified property. The most fundamental such property is that the network/graph be connected. For connectivity, prior work on topology control gave a polynomial time algorithm for minimizing the maximum power assigned to any node (such that the induced graph is connected). In this paper we study the problem of minimizing the number of maximum power nodes. After establishing that this minimization problem is NP-complete, we focus on approximation algorithms for graphs with symmetric power thresholds. We first show that the problem is reducible in an approximation preserving manner to the problem of assigning power values so that the sum of the powers is minimized. Using known results for that problem, this provides a family of approximation algorithms for the problem of minimizing the number of maximum power nodes with approximation ratios of 5/3 + epsilon for every epsilon > 0. Unfortunately, these algorithms, based on solving large linear programming problems, are not practical. The main results of this paper are practical algorithms with approximation ratios of 7/4 and 5/3 (exactly). In addition, we present experimental results, both on randomly generated networks, and on two networks derived from proximity data associated with the TRANSIMS project of Los Alamos National Labs. Finally, based on the reduction to the problem of minimizing the total power, we describe some additional results for minimizing the number of maximum power users, both for graph properties other than connectivity and for graphs with asymmetric power thresholds.

关键词： adhoc network topology control maximum power users approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Steiner connected dominating set

Approximation algorithms for Steiner connected dominating se...

引用

9th Asia-Pacific Computer Systems Architecture Conference (ACSAC 2004)

作者： Wu, YF Xu, YL Chen, GL Univ Sci & Technol China Natl High Performance Comp Ctr Hefei Dept Comp Sci & Technol Hefei 230027 Peoples R China

Steiner connected dominating set (SCDS) is a generalization of the famous connected dominating set problem, where only a specified set of required vertices has to be dominated by a connected dominating set, and known to be NP-hard. This paper firstly modifies the SCDS algorithm of Guha and Khuller and achieves a worst case approximation ratio of (2 + 1/(m - 1))H(min(Delta, k)) + O(1), which outperforms the previous best result (c + 1)H(min(Delta, k)) + O(1) in the case of m >= 1 + 1/(c - 1), where c is the best approximation ratio for Steiner tree, Delta is the maximum degree of the graph, k is the cardinality of the set of required vertices, m, is an optional integer satisfying 0 <= m <= min(Delta, k) and H is the harmonic function. This paper also proposes another approximation algorithm which is based on a greedy approach. The second algorithm can establish a worst case approximation ratio of 21n(min(Delta, k)) + O(1), which can also be improved to 21nk if the optimal solution is greater than c(.)e(2c+1)/2(c+1).

关键词： approximation algorithm Steiner connected dominated set graph algorithm NP-hard

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for the Quality of Service Multicast Tree Problem

引用

algorithmICA 2005年第2期42卷 109-120页

作者： Karpinski, M Mandoiu, II Olshevsky, A Zelikovsky, A Univ Bonn Dept Comp Sci D-53117 Bonn Germany Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA MIT Dept Elect Engn & Comp Sci Cambridge MA 02139 USA Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA

The Quality of Service Multicast Tree Problem is a generalization of the Steiner tree problem which appears in the context of multimedia multicast and network design. In this generalization, each node possesses a rate and the cost of an edge with length l in a Steiner tree T connecting the source to non-zero rate nodes is l center dot r(e), where r(e) is the maximum node rate in the component of T-{e} that does not contain the source. The best previously known approximation ratios for this problem (based on the best known approximation factor of 1.549 for the Steiner tree problem in networks) are 2.066 for the case of two non-zero rates and 4.212 for the case of an unbounded number of rates. In this paper we give improved approximation algorithms with ratios of 1.960 and 3.802, respectively. When the minimum spanning tree heuristic is used for finding approximate Steiner trees, then the previously best known approximation ratios of 2.667 for two non-zero rates and 5.542 for an unbounded number of rates are reduced to 2.414 and 4.311, respectively.

关键词： approximation algorithm interconnection network multicast quality of service Steiner tree

来源：评论

学校读者我要写书评

暂无评论

A linear programming formulation and approximation algorithms for the metric labeling problem

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2005年第3期18卷 608-625页

作者： Chekuri, C Khanna, S Naor, J Zosin, L Bell Labs Lucent Technol Murray Hill NJ 07974 USA Univ Penn Dept Comp & Informat Sci Philadelphia PA 19104 USA Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel NEC Res Inst Princeton NJ 08540 USA

We consider approximation algorithms for the metric labeling problem. This problem was introduced in a paper by Kleinberg and Tardos [J. ACM, 49 (2002), pp. 616-630] and captures many classification problems that arise in computer vision and related fields. They gave an O(log k log log k) approximation for the general case, where k is the number of labels, and a 2-approximation for the uniform metric case. (In fact, the bound for general metrics can be improved to O(log k) by the work of Fakcheroenphol, Rao, and Talwar [Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 448-455].) Subsequently, Gupta and Tardos [Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing, 2000, pp. 652-658] gave a 4-approximation for the truncated linear metric, a metric motivated by practical applications to image restoration and visual correspondence. In this paper we introduce an integer programming formulation and show that the integrality gap of its linear relaxation either matches or improves the ratios known for several cases of the metric labeling problem studied until now, providing a unified approach to solving them. In particular, we show that the integrality gap of our linear programming (LP) formulation is bounded by O(log k) for a general k-point metric and 2 for the uniform metric, thus matching the known ratios. We also develop an algorithm based on our LP formulation that achieves a ratio of 2 + root 2 similar or equal to 3.414 for the truncated linear metric improving the earlier known ratio of 4. Our algorithm uses the fact that the integrality gap of the LP formulation is 1 on a linear metric.

关键词： metric labeling linear program approximation algorithm truncated linear metric

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：