๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Estimates of the Duality Gap for Optimum Partition Problems

โœ Scribed by E. M. Kiseleva; N. K. Vasil'eva

Book ID
110314591
Publisher
Springer US
Year
2001
Tongue
English
Weight
39 KB
Volume
107
Category
Article
ISSN
1573-8795

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Approximation Results for the Optimum Co
Approximation Results for the Optimum Cost Chromatic Partition Problem
โœ Klaus Jansen ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 246 KB

In this paper, we study the optimum cost chromatic partition OCCP problem for several graph classes. The OCCP problem is the problem of coloring the vertices of a graph such that adjacent vertices get different colors and that the total coloring cost is minimum. We prove several approximation result

Exponentially small bounds on the expect
Exponentially small bounds on the expected optimum of the partition and subset sum problems
โœ George S. Lueker ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 172 KB

In the partition problem we seek to partition a list of numbers into two sublists to minimize the difference between the sums of the two sublists. For this and the related subset sum problem, under suitable assumptions on the probability distributions of the input, it is known that the median of the