Re: [eclipse-clp-users] Knappsack-Problem Modification

From: Wit Jakuczun <wit.jakuczun_at_gmail.com>
Date: Tue, 13 Apr 2010 16:46:59 +0200
W dniu 2010-04-13 13:47, Philipp Marcus pisze:
>    
>> Ok. So what is your exact task to do:
>> 1) to prove NP-completeness of the problem
>>      
> That is more a "bonus" task. Do you have any ideas how to prove it? I
> think the best way is to map it to a problem that is known to be
> NP-complete, but I don't know which one is suited best for that..
>    
Your problem is a variation of k-median problem that is NP-complete. 
Maybe you should check this path...

>> 2) write a solver for a problem using ECLiPSe ?
>>      
> Thats what I have to do. Currently I am working on a version that uses
> ic_symbolic and includes all your hints. I could post it to the list
> when I'm done.
>    
You do not need to use ic_symbolic. You could have a mapping: 1-A, 2-B, 
3-C and use ic or fd library.

Best regards

-- 
[ Wit Jakuczun http://pl.linkedin.com/in/jakuczunwit ]
Received on Tue Apr 13 2010 - 14:47:17 CEST

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET