0
votes
0answers
114 views

Karger's algorithm for bin-packing?

I first came across that algorithm as the "Random minimum cut" algorithm. And recently a colleague was trying to pack a big quantity of small textures into one image file. Then it clicked - why not ...
14
votes
5answers
2k views

What would be the Impact of P=NP? [closed]

I am preparing for a test and I can't find a clear answer on the question: What would be the impact of proving that PTIME=NPTIME. I checked wikipedia and it just mentioned that it would have "profound ...
11
votes
2answers
925 views

Converting a bounded knapsack problem to 0/1 knapsack problem

I ran across a problem where goal was to use dynamic programming (instead of other approaches). There is a distance to be spanned, and a set of cables of different lengths. What is the minimum number ...