Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!van-bc!ubc-cs!fornax!mahajan
From: mahajan@fornax.UUCP (Sanjeev Mahajan)
Newsgroups: comp.theory
Subject: Re: An NP-Complete Problem?
Message-ID: <443@fornax.UUCP>
Date: 21 Mar 90 06:16:05 GMT
References: <637950193.627@minster.york.ac.uk>
Organization: School of Computing Science, SFU, Burnaby, B.C. Canada
Lines: 27

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