0

I am a computer science student in university, at work I stumbled across what I believe is a NP-Hard problem that I have an active interest to solve in it's complete form. I have no experience in either solving these problems or publishing papers. My question is how I would go about solving the problem while having a paper I can submit at the end, advice on guidance for solving would be welcome though extraneous to the answer. I spent time searching to see if this problem was solved yet, the closest to it I found was stock cutting algorithms which this is not so I am under the impression that the problem itself is novel.

Improve this question
3
  • 8
    1) If you are a specific university, then your best option is to talk with professors at that university and get one to help you. 2) I'm a little concerned here about your desire to "solve" the problem in this context. What do you mean by solve? Do you mean you have an algorithm which is better than the obvious one for this specific problem? Or do you mean something else?
    – JoshuaZ
    Commented Apr 11 at 16:38
  • By solve I mean come up with an algorithm for a novel problem, that is to say that I haven't found this problem in the wild which was surprising, but I want to figure out a way to figure it out, and it could be extremely practical in terms of ui
    – TimothyH
    Commented Apr 11 at 16:54
  • I'm going to ask George Corser probably, thanks... I was considering it but due to my own level of stupid I wanted to try keeping things to myself as I'm more than a little likely to just drop this
    – TimothyH
    Commented Apr 11 at 16:55

1 Answer 1

Reset to default
1

A good start is to become familiar with the area of NP-hard problems and understand what can and cannot be done with them. Specifically, NP-hard problems cannot be "solved" efficiently. That's pretty much the definition (in practice, though of course not as far as theory is concerned) of what NP-hard actually means. All you can do is to find approximate solutions, which is something that can often be done efficiently.

I don't think anyone can give you advice on solving (or approximating) the problem unless you describe it in detail.

Improve this answer
5
  • The arrangement of boxes into a box which should have an aspect ratio of 1.777... such that the solution is graded by how small the containing box is (the way to verify in theory the solution being to generate every combination and search those for the best). I've considered try this by representing each contained box using a vector... I was mostly asking the question for the paper, should I have used the word approximation rather than solution in my question?
    – TimothyH
    Commented Apr 11 at 20:16
  • 1
    This sounds like the knapsack problem, or one of its variations.
    – Wolfgang Bangerth
    Commented Apr 11 at 22:37
  • I looked up knapsack and stock cutting problems, I thought it was closer to the stock cutting. Is there a reason that it's closer to knapsack?
    – TimothyH
    Commented Apr 12 at 11:54
  • 1
    @TimothyH You've never explained in detail what the problem is. I can't know what it is closer to.
    – Wolfgang Bangerth
    Commented Apr 12 at 16:01
  • George Corser gave me a little direction, I'm going to start working on the problem, thanks
    – TimothyH
    Commented Apr 12 at 16:46

Not the answer you're looking for? Browse other questions tagged .