KzNuRs's blog

By KzNuRs, history, 7 years ago, In English

How to solve?

  • Vote: I like it
  • -14
  • Vote: I do not like it

| Write comment?
»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I don't think this is a min-flow max cut problem...

  • »
    »
    7 years ago, hide # ^ |
     
    Vote: I like it +34 Vote: I do not like it

    Yes, because min flow can be solved in O(1).

  • »
    »
    7 years ago, hide # ^ |
    Rev. 2  
    Vote: I like it +9 Vote: I do not like it

    You can frame it as one, I believe. I think you can reduce it to the following problem:

    You are given $$$n$$$ boxes of varying dimensions $$$l_i \times w_i \times h_i$$$, and we say that box $$$i$$$ can be nested in box $$$j$$$ iff $$$l_i \lt l_j$$$, $$$w_i \lt w_j$$$, and $$$h_i \lt h_j$$$. You can stack nesting, i.e. if box $$$i$$$ can be nested in box $$$j$$$ and box $$$j$$$ in box $$$k$$$, then, you can nest $$$i$$$ into $$$j$$$ and $$$j$$$ into $$$k$$$, meaning neither box $$$i$$$ nor box $$$j$$$ is visible anymore. Given our $$$n$$$ boxes, we want to nest the boxes in such a way to reduce the total number of visible boxes.

    The above problem appeared on my algorithms homework, and the solution used max flow.

    I think the solution is cool but I don't actually want to write it, because I'm still not convinced that this problem isn't OP's homework problem (he posted it before with a download link to the image, and it was called "Assignment7.pdf").