𝔖 Bobbio Scriptorium
✦   LIBER   ✦

New approximation algorithm for RTILE problem

✍ Scribed by Krzysztof Lorys; Katarzyna E. Paluch

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
337 KB
Volume
303
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

For a given two-dimensional array of nonnegative numbers and a positive integer p we want to ΓΏnd a covering of the array with p tiles so as to minimize the weight of the heaviest tile. We present a 9 4 -approximation linear-time algorithm for this problem, which improves on the previous best result.

πŸ“œ SIMILAR VOLUMES

Approximation Algorithms for Directed St
Approximation Algorithms for Directed Steiner Problems
✍ Moses Charikar; Chandra Chekuri; To-yat Cheung; Zuo Dai; Ashish Goel; Sudipto Gu πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 181 KB

We give the first non-trivial approximation algorithms for the Steiner tree problem and the generalized Steiner network problem on general directed graphs. These problems have several applications in network design and multicast routing.

Approximation algorithm for the group St
Approximation algorithm for the group Steiner network problem
✍ Michal Penn; Stas Rozenfeld πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 143 KB

## Abstract In this article we study the __group Steiner network__ problem, which is defined in the following way. Given a graph __G__ = (__V,E__), a partition of its vertices into K groups and connectivity requirements between the different groups, the aim is to find simultaneously a set of repres