✦ LIBER ✦

A Constant-Factor Approximation Algorithm for thek-MST Problem

✍ Scribed by Avrim Blum; R Ravi; Santosh Vempala

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 186 KB
Volume: 58
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.1997.1542

No coin nor oath required. For personal study only.

✦ Synopsis

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 optimum. This improves upon previous performance ratios for this problem &O(-k) due to Ravi et al., O(log 2 k) due to Awerbuch et al., and the previous best bound of O(log k) due to Rajagopalan and Vazirani. Given any 0<:<1, we first present a bicriteria approximation algorithm that outputs a tree on p :k vertices of total cost at most 2pLÂ(1&:) k, where L is the cost of the optimal k-MST. The running time of the algorithm is O(n 2 log 2 n) on an n-node graph. We then show how to use this algorithm to derive a constant factor approximation algorithm for the k-MST problem. The main subroutine in our algorithm is an approximation algorithm of Goemans and Williamson for the prize-collecting Steiner tree problem. ] 1999

📜 SIMILAR VOLUMES

A Constant-Factor Approximation Algorith

A Constant-Factor Approximation Algorithm for the k-Median Problem

✍ Moses Charikar; Sudipto Guha; Éva Tardos; David B. Shmoys 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 165 KB

We present the first constant-factor approximation algorithm for the metric k-median problem. The k-median problem is one of the most wellstudied clustering problems, i.e., those problems in which the aim is to partition a given set of points into clusters so that the points within a cluster are rel

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

Constant Ratio Approximation Algorithms

Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem

✍ Daya Ram Gaur; Toshihide Ibaraki; Ramesh Krishnamurti 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 114 KB

We provide constant ratio approximation algorithms for two NP-hard problems, the rectangle stabbing problem and the rectilinear partitioning problem. In the rectangle stabbing problem, we are given a set of rectangles in two-dimensional space, with the objective of stabbing all rectangles with the m

A Polylogarithmic Approximation Algorith

A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem

✍ Naveen Garg; Goran Konjevod; R. Ravi 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 130 KB

The group Steiner tree problem is a generalization of the Steiner tree problem where we are given several subsets (groups) of vertices in a weighted graph, and the goal is to find a minimum-weight connected subgraph containing at least one vertex from each group.The problem was introduced by Reich a

A New Approximation Algorithm for the St

A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3

✍ Hans Jürgen Prömel; Angelika Steger 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 100 KB

In this paper we present an RNC approximation algorithm for the Steiner tree problem in graphs with performance ratio 5r3 and RNC approximation algorithms for the Steiner tree problem in networks with performance ratio 5r3 q ⑀ for all ⑀ ) 0. This is achieved by considering a related problem, the min

A robust algorithm for the solution of e

A robust algorithm for the solution of electromagnetic problems over a frequency interval via the Padé approximation

✍ Mustafa Kuzuoglu; Raj Mittra 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 124 KB 👁 2 views

In this paper, we present an efficient and systematic algorithm for the solution of electromagnetic scattering and radiation problems o¨er a wide frequency inter¨al. The algorithm is based on the e¨aluation of the Pade approximant of the solution ¨ector, constructed át a minimum number of expansion