𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Partitioning heuristics for two geometric maximization problems

✍ Scribed by M.E Dyer; A.M Frieze; C.J.H McDiarmid

Publisher
Elsevier Science
Year
1984
Tongue
English
Weight
315 KB
Volume
3
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Approximation Algorithms for Maximizatio
Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
✍ Uriel Feige; Michael Langberg πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 261 KB

Given a graph G = V E , a weight function w E β†’ R + , and a parameter k, we consider the problem of finding a subset U βŠ† V of size k that maximizes: Max-Vertex Cover k the weight of edges incident with vertices in U, Max-Dense Subgraph k the weight of edges in the subgraph induced by U, Max-Cut k th

ΞΊ-Partitioning problems for maximizing t
ΞΊ-Partitioning problems for maximizing the minimum load
✍ Yong He; Zhiyi Tan; Jing Zhu; Enyu Yao πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 664 KB

The optimization versions of the k-PARTITIONING problems are considered in this paper. For the objective to maximize the minimum load of m subsets, we first show that the FOLD-ING algorithm has a tight worst case ratio of max{2/k, l/m}. Th en, we present an algorithm called HARMONIC1 with a worst ca