𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximation Algorithms for Min–Max Tree Partition

✍ Scribed by Nili Guttmann-Beck; Refael Hassin

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
298 KB
Volume
24
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the problem of partitioning the node set of a graph into p equal sized subsets. The objective is to minimize the maximum length, over these subsets, of a minimum spanning tree. We show that no polynomial algorithm with bounded Ž 2 . error ratio can be given for the problem unless P s NP. We present an O n time algorithm for the problem, where n is the number of nodes in the graph. Assuming that the edge lengths satisfy the triangle inequality, its error ratio is at most 2 p y 1. We also present an improved algorithm that obtains as an input a positive Ž Ž pqx . p 2 . Ž integer x. It runs in O 2 n time, and its error ratio is at most 2 y xr Ž . . x q p y 1 p .

📜 SIMILAR VOLUMES

Improved Approximation Algorithms for MA
Improved Approximation Algorithms for MAX SAT
✍ Takao Asano; David P. Williamson 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 215 KB

MAX SAT (the maximum s~tisfiability problem) is stated as follows: given a set of clauses with weights, find a truth assignment that maximizes the sum of the weights of the satisfied clauses. In this paper, we consider approxima~ tion algorithms for MAX SAT proposed by Goemans and Williamson and pze

Improved Approximation Algorithms for Tr
Improved Approximation Algorithms for Tree Alignment
✍ Lusheng Wang; Dan Gusfield 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 251 KB

Multiple sequence alignment is a task at the heart of much of current computaw x tional biology 4 . Several different objective functions have been proposed to formalize the task of multiple sequence alignment, but efficient algorithms are lacking in each case. Thus multiple sequence alignment is on

On Approximation Algorithms for Hierarch
On Approximation Algorithms for Hierarchical MAX-SAT
✍ Sameet Agarwal; Anne Condon 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 232 KB

We prove upper and lower bounds on performance guarantees of approximation Ž . algorithms for the hierarchical MAX-SAT H-MAX-SAT problem. This problem is representative of a broad class of PSPACE-hard problems involving graphs, Boolean formulas, and other structures that are defined succinctly. Our

Approximation results for min-max path c
Approximation results for min-max path cover problems in vehicle routing
✍ Zhou Xu; Liang Xu; Chung-Lun Li 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 410 KB

## Abstract This article studies a min‐max path cover problem, which is to determine a set of paths for __k__ capacitated vehicles to service all the customers in a given weighted graph so that the largest path cost is minimized. The problem has wide applications in vehicle routing, especially when