𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A 2 +ɛapproximation algorithm for thek-MST problem

✍ Scribed by Sanjeev Arora; George Karakostas

Publisher
Springer-Verlag
Year
2005
Tongue
English
Weight
177 KB
Volume
107
Category
Article
ISSN
0025-5610

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