@article{oai:bunkyo.repo.nii.ac.jp:00003450,
 author = {Nemoto,Toshio},
 journal = {情報研究, Information and Communication Studies},
 month = {1996-01-01, 2012-01-17},
 note = {Suppose we are given a poset (partially ordered set) P= (V,?), a real-valued weight w(v) associated with each element v ∈ V and a positive integer K. We consider the problem which asks to find an ideal of size K of P such that the sum of the weights of the elements of this ideal is the minimum for all ideals that can be constructed from P. We call this problem the minimum-weight x-ideal problem. In this paper we explore a further possibility for a solvable case of this problem because it has been proven that this problem is NP-hard even if the Hasse diagram representing a given poset is a bipartite graph. We obtain two new results. First, we describe an O(K2n) algorithm on the special poset whose Hasse diagram is a directed tree, which is called a directed tree poset. Here n is the cardinality of the underlying set of the given poset. This outperforms an O(n4) algorithm that is the best previously known. Secondly, we show a characteristic of the polyhedron obtained from the LP-relaxation of the K-ideal problem on a directed tree poset. This is the first step to solve the other type K-ideal problems from the LP-relaxation technique.},
 pages = {265--274},
 title = {The Minimum-weight k-Ideal Problem on a Directed Tree Poset and Its Polyhedron},
 volume = {17},
 year = {}
}