mike@minster.york.ac.uk (03/21/90)
Is the following problem NP-something? Given a get of tuples (bi, ci) and a value d, where the bi and ci are zero or positive integers, and d a non-zero positive integer, is it possible to test for the existance of a subset such that sum bi <= d <= sum bi + sum ci Any suggestions appreciated mike@minster.york.ac.uk Mike Richardson
mahajan@fornax.UUCP (Sanjeev Mahajan) (03/21/90)
In article <637950193.627@minster.york.ac.uk>, mike@minster.york.ac.uk writes: > > Given a get of tuples (bi, ci) and a value d, where > the bi and ci are zero or positive integers, and d > a non-zero positive integer, is it possible to test > for the existance of a subset such that > > sum bi <= d <= sum bi + sum ci > Restrict to partition, assign all ci's to 0, and assign d to the floor of half of all bi's. Sanjeev
halldors@paul.rutgers.edu (Magnus M Halldorsson) (03/21/90)
In article <637950193.627@minster.york.ac.uk> mike@minster.york.ac.uk writes: > Given a get of tuples (bi, ci) and a value d, where > the bi and ci are zero or positive integers, and d > a non-zero positive integer, is it possible to test > for the existance of a subset such that > > sum bi <= d <= sum bi + sum ci If the c_i's are all zero, then the problem reduces to finding a subset such that sum b_i = d, which is known as the Subset Sum problem and is NP-complete [e.g. see Garey & Johnson pp.223]. Magnus