Skip to main content
ulyssis2's user avatar
ulyssis2's user avatar
ulyssis2's user avatar
ulyssis2
  • Member for 10 years, 5 months
  • Last seen more than a month ago
awarded
revised
NP-hard proof of optimization version of exact cover
reformulate the problem description
Loading…
comment
NP-hard proof of optimization version of exact cover
Hi, Emil, now I understand the exact cover is NPC and also the proof on it. I edited my post, could you please have a look at it?
revised
Loading…
revised
Loading…
revised
Loading…
comment
NP-hard proof of optimization version of exact cover
I agree with you that canonical exact cover is one special case of my proposed problem, but I want to see how to prove my problem to be NP-hard.
comment
NP-hard proof of optimization version of exact cover
OK, I somehow misunderstood the canonical exact set cover, the weighted exact set cover problem which involves restriction on summation is a very different problem. One draft (arxiv.org/abs/1302.5820) gives proof on NP hardness of weighted exact set cover.
comment
NP-hard proof of optimization version of exact cover
Thanks Emil. $\lambda$ is one input. As to canonical exact cover problem, each set is assigned with identical weight, people check whether the number of sets (also is the sum of weights in the same time) exceeds one given integer number. My proposed problem has two differences with the canonical one, firstly, sets are given different weights, secondly, 'average weight' in stead of summation of weights are considered.
awarded
revised
Loading…
Loading…
awarded