4 ms·
i talk about karp's paper: reducibility among combinatorial problems(i); in another thread and i found this integer programming tutorial comprehensive in offer
by justifier 11y ago
i talk about karp's paper: reducibility among combinatorial problems(i); in another thread
and i found this integer programming tutorial comprehensive in offering practical applications of the desired algorithm(ii)
do any of these examples explain the problem best for you?
can you write a program that will solve this question for you?
now change the values of the variables, increase the number of variables
does your algorithm still work on these other inputs?
can you rewrite the algorithm to give the correct answers for these other inputs?
can you develop enough coverage to prove all possible inputs return correct values?
if your coverage is substantial, seemingly complete, can you write against your algorithm to find inputs that will still require you to further develop the algorithm?
for me, i felt i was able to follow the explanation for how the author found the answer and through that was able to start to see the shape of the coverage necessary to accommodate such a problem (iii)
this specific tutorial is on integer programming.. one of karp's 21, and through reduction on our understanding of 0-1 integer programming we can understand all of the other 21
(i) http://www.cs.berkeley.edu/~luca/cs172/karp.pdf http://www.cs.berkeley.edu/~luca/cs172/karp.pdf
(ii) http://mat.gsia.cmu.edu/orclass/integer/integer.html http://mat.gsia.cmu.edu/orclass/integer/integer.html
(iii) http://mat.gsia.cmu.edu/orclass/integer/node4.html#SECTION00031000000000000000 http://mat.gsia.cmu.edu/orclass/integer/node4.html#SECTION00...