Timeline for NP-hard proof of optimization version of exact cover [closed]
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 5, 2014 at 18:05 | history | edited | ulyssis2 | CC BY-SA 3.0 |
reformulate the problem description
|
| Jul 31, 2014 at 14:09 | history | closed |
Emil Jeřábek Ryan Budney Stefan Kohl♦ S. Carnahan♦ |
Not suitable for this site | |
| Jul 31, 2014 at 12:14 | comment | added | Emil Jeřábek | You seem to be confused about the basic definitions of NP-completeness et al. Mathoverflow is really not an appropriate place for such questions, you should try cs.stackexchange.com or math.stackexchange.com . | |
| Jul 31, 2014 at 12:00 | comment | added | ulyssis2 | 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? | |
| Jul 31, 2014 at 11:59 | history | edited | ulyssis2 | CC BY-SA 3.0 |
added 336 characters in body
|
| Jul 31, 2014 at 11:52 | history | edited | ulyssis2 | CC BY-SA 3.0 |
added 336 characters in body
|
| Jul 31, 2014 at 10:47 | history | edited | ulyssis2 | CC BY-SA 3.0 |
deleted 9 characters in body
|
| Jul 30, 2014 at 17:57 | review | Close votes | |||
| Jul 31, 2014 at 14:09 | |||||
| Jul 30, 2014 at 17:40 | comment | added | Emil Jeřábek | See e.g. mathreference.com/lan-cx-np,excov.html | |
| Jul 30, 2014 at 17:35 | comment | added | ulyssis2 | 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. | |
| Jul 30, 2014 at 17:34 | comment | added | ulyssis2 | 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. | |
| Jul 30, 2014 at 16:47 | comment | added | Emil Jeřábek | The canonical exact cover problem does not involve any sums of weights, it just asks whether $U$ can be written as a disjoint union of a subcollection of $S$. This is a special case of your problem with all weights 1, and $\lambda=1/2$ (say). | |
| Jul 30, 2014 at 16:33 | comment | added | ulyssis2 | 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. | |
| Jul 30, 2014 at 15:15 | comment | added | Emil Jeřábek | As written, $\lambda$ does not do anything. Do you perhaps intend it to be part of the input rather than output? Or maybe a fixed parameter of the problem? Either way, exact cover is obviously a special case of your problem where all the weights are the same and $\lambda$ is set smaller, so I don’t understand where is supposed to be the problem. | |
| Jul 30, 2014 at 15:14 | history | edited | ulyssis2 | CC BY-SA 3.0 |
trivial changes on words.
|
| Jul 30, 2014 at 15:08 | review | First posts | |||
| Jul 30, 2014 at 15:13 | |||||
| Jul 30, 2014 at 15:03 | history | asked | ulyssis2 | CC BY-SA 3.0 |