𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Dynamic Programming Algorithm for thek-Haplotyping Problem

✍ Scribed by Zhen-ping Li; Ling-yun Wu; Yu-ying Zhao; Xiang-sun Zhang

Publisher
Institute of Applied Mathematics, Chinese Academy of Sciences and Chinese Mathematical Society
Year
2006
Tongue
English
Weight
165 KB
Volume
22
Category
Article
ISSN
0168-9673

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A Constant-Factor Approximation Algorith
A Constant-Factor Approximation Algorithm for thek-MST Problem
✍ Avrim Blum; R Ravi; Santosh Vempala πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 186 KB

Given an undirected graph with nonnegative edge costs and an integer k, the k-MST problem is that of finding a tree of minimum cost on k nodes. This problem is known to be NP-hard. We present a simple approximation algorithm that finds a solution whose cost is less than 17 times the cost of the opti

A Greedy On-Line Algorithm for thek-Trac
A Greedy On-Line Algorithm for thek-Track Assignment Problem
✍ U Faigle; W Kern; W.M Nawijn πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 107 KB

Given a collection I I of n jobs that are represented by intervals, we seek a maximal feasible assignment of the jobs to k machines such that not more than Ε½ . c M intervals overlap pairwise on any machine M and that a job is only assigned to a machine if it fits into one of several prescribed time