An efficient algorithm for the minimum-range ideal problem

An efficient algorithm for the minimum-range ideal problem

0.00 Avg rating0 Votes
Article ID: iaor2000440
Country: Japan
Volume: 42
Issue: 1
Start Page Number: 88
End Page Number: 97
Publication Date: Mar 1999
Journal: Journal of the Operations Research Society of Japan
Authors:
Keywords: combinatorial analysis, graphs
Abstract:

Suppose we are given a partially ordered set, a real-valued weight associated with each element and a positive integer k. We consider the problem which asks us to find an ideal of size k of the partially ordered set such that the range of the weights is minimum. We call this problem the minimum-range ideal problem. This paper shows a new and fast O(n log n + m) algorithm for this problem, where n is the number of elements and m is the smallest number of arcs to represent the partially ordered set. It is also proved that this problem has an Ω(n log n + m) lower bound. This means that the algorithm presented in this paper is optimal.

Reviews

Required fields are marked *. Your email address will not be published.