Title: Partitioning a weighted partial order
Authors: Moonen, Linda ×
Spieksma, Frederik #
Issue Date: May-2008
Publisher: Kluwer Academic Publishers
Series Title: Journal of combinatorial optimization vol:15 issue:4 pages:342-356
Abstract: 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 wi is given for each element i in the partial order such that wi ≤ wj 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 APX-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
ISSN: 1382-6905
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Research Center for Operations Research and Business Statistics (ORSTAT), Leuven
× corresponding author
# (joint) last author

Files in This Item:
File Status SizeFormat
Partioning a weighted partial.pdf Published 337KbAdobe PDFView/Open Request a copy

These files are only available to some KU Leuven Association staff members


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science