Randomizer
  • Member for 11 years
  • Last seen more than a month ago
Compendium of the Best Approximation and Hardness Results for NP optimization problems
7 votes

Complexity Garden is a wiki devoted to computational problems and their relations to complexity classes. As suggested here, I was planning to a start a new wiki for the algorithmic results, but I ...

View answer
Bin Packing with uniform size constraints
Accepted answer
5 votes

As Peter pointed out, the 3-partition problem is NP-hard even when the sizes are between $1/3-\delta$ and $1/3+\delta$ for any constant $\delta>0$. Therefore, by a simple reduction from the 3-...

View answer