𝔖 Bobbio Scriptorium
✦   LIBER   ✦

κ-Partitioning problems for maximizing the minimum load

✍ Scribed by Yong He; Zhiyi Tan; Jing Zhu; Enyu Yao

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
664 KB
Volume
46
Category
Article
ISSN
0898-1221

No coin nor oath required. For personal study only.

✦ Synopsis

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 case ratio at least max{l/k, l/( TX;1 l/i] + 1)). It concludes the HAR-MONICl is better than FOLDING for k > 2( [C~"=l l/i1 + 1). We further show that HARMONIC1 is asymptotically optimal ordinal algorithm. We also present an algorithm HARMONIC2 for solving the general /Q-PARTITIONING problem.

📜 SIMILAR VOLUMES

Algorithms for the minimum partitioning
Algorithms for the minimum partitioning problems in graphs
✍ Hiroshi Nagamochi 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 545 KB

## Abstract In this paper, the author explains the recent evolution of algorithms for minimum partitioning problems in graphs. When the set of vertices of a graph having non‐negative weights for edges is divided into __k__ subsets, the set of edges for which both endpoints are contained in differen

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

Approximating the maximally balanced con
Approximating the maximally balanced connected partition problem in graphs
✍ Janka Chlebíková 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 572 KB

The approximability of the following optimization problem is investigated: Given a connected graph G = (YE), find the maximally balanced connected partition for G, i.e. a partition (K, V2) of V into disjoint sets VI and V2 such that both subgraphs of G induced by VI and & are connected, and maximize