Partitioning a weighted partial order |
| |
Authors: | Linda S Moonen Frits C R Spieksma |
| |
Institution: | (1) Research Center for Operations Research and Business Statistics (ORSTAT), Katholieke Universiteit Leuven, Naamsestraat 69, 3000 Leuven, Belgium |
| |
Abstract: | The problem of partitioning a partially ordered set into a minimum number of chains is a well-known problem. In this paper
we study a generalization of this problem, where we not only assume that the chains have bounded size, but also that a weight
w
i
is given for each element i in the partial order such that w
i
≤w
j
if i
≺
j. The problem is then to partition the partial order into a minimum-weight set of chains of bounded size, where the weight
of a chain equals the weight of the heaviest element in the chain. We prove that this problem is
-hard, and we propose and analyze lower bounds for this problem. Based on these lower bounds, we exhibit a 2-approximation
algorithm, and show that it is tight. We report computational results for a number of real-world and randomly generated problem
instances. |
| |
Keywords: | Partially ordered sets Chain decomposition Approximation algorithms |
本文献已被 SpringerLink 等数据库收录! |
|