Stack Overflow
Stack Overflow

Questions tagged [np-hard]

NP-hard problems (Non-deterministic Polynomial-time hard problems) are those problems which are not easier than any problem in NP; in other words, an algorithm for an NP-hard problem can be used to solve any problem in NP by transforming the input in polynomial time. Problems which are in both NP-Hard and NP are known as NP-Complete.

178 questions
1409
votes
12 answers

What are the differences between NP, NP-Complete and NP-Hard?

What are the differences between NP, NP-Complete and NP-Hard? I am aware of many resources all over the web. I'd like to read your explanations, and the reason is they might be different from what's out there, or there is something that I'm not…
DarthVader
  • 52,984
  • 76
  • 209
  • 300
59
votes
7 answers

Parabolic knapsack

Lets say I have a parabola. Now I also have a bunch of sticks that are all of the same width (yes my drawing skills are amazing!). How can I stack these sticks within the parabola such that I am minimizing the space it uses as much as possible? I…
rook
  • 66,304
  • 38
  • 162
  • 239
47
votes
4 answers

What is the problem name for Traveling salesman problem(TSP) without considering going back to starting point?

I would like to know what is the problem name for TSP w/o considering the way of going back to starting point and what is the algorithm to solve this. I looked into Shortest path problem but that is not what I am looking for, the problem only find…
A-letubby
  • 8,474
  • 8
  • 38
  • 48
42
votes
6 answers

3 dimensional bin packing algorithms

I'm faced with a 3 dimensional bin packing problem and am currently conducting some preliminary research as to which algorithms/heuristics are currently yielding the best results. Since the problem is NP hard I do not expect to find the optimal…
BuschnicK
  • 5,304
  • 8
  • 37
  • 49
30
votes
10 answers

Teacher time schedule algorithm

This is a problem I've had on my mind for a long time. Being the son of a teacher and a programmer, it occurred to me early on... but I still haven't found a solution for it. So this is the problem. One needs to create a time schedule for a school,…
Sklivvz
  • 30,601
  • 24
  • 116
  • 172
22
votes
14 answers

Have you used a traveling salesman algorithm to solve a problem?

I studied TSP in college in the context of NP Completeness. I have never actually had a situation where it would apply to a practical problem. A little bit of research shows that it has been used to pick the cheapest path to move a drill…
EvilTeach
  • 28,120
  • 21
  • 85
  • 141
20
votes
2 answers

Minimum number of flips to get adjacent 1's in a matrix

Given a binary matrix (values of 0 or 1), adjacent entries of 1 denote “hills”. Also, given some number k, find the minimum number of 0's you need to “flip” to 1 in order to form a hill of at least size k. Edit: For clarification, adjacent means…
The Monkey
  • 262
  • 1
  • 9
19
votes
3 answers

Relationship between NP-hard and undecidable problems

Am a bit confused about the relationship between undecidable problems and NP hard problems. Whether NP hard problems are a subset of undecidable problems, or are they just the same and equal, or is it that they are not comparable? For me, I have…
akaHuman
  • 1,332
  • 1
  • 14
  • 33
18
votes
14 answers

I need high performance. Will there be a difference if I use C or C++?

I need to write a program (a project for university) that solves (approx) an NP-hard problem. It is a variation of Linear ordering problems. In general, I will have very large inputs (as Graphs) and will try to find the best solution (based on a…
Itsik
  • 3,920
  • 1
  • 25
  • 37
12
votes
5 answers

NP-Complete VS NP-Hard

I am trying to understand the difference between NP-Complete and NP-Hard. Below is my understanding An NP-Hard problem is one that is not solvable in polynomial time but can be verified in polynomial time. An NP-Complete problem is one that is…
ade19
  • 1,150
  • 4
  • 13
  • 28
11
votes
3 answers

largest possible rectangle of letters

Write a program to find the largest possible rectangle of letters such that every row forms a word (left to right) and every column forms a word (top to bottom). I found this interesting question. It's not homework, though it may sound as such.…
Adrian
  • 5,603
  • 8
  • 53
  • 85
10
votes
4 answers

NP-Hard? Algorithmic complexity of online poker collusion detection?

What's the best way to describe the algorithmic complexity of collusion detection for a ten-million-player online poker site? Assume (I don't think these assumptions make much difference so feel free to ignore them, but just to clarify): That the…
user2189331
10
votes
5 answers

What are the "hardest" problems using polynomial time?

Recently I read a seminar work which says: The matching algorithm [for general graphs] can be extended to the weighted case, which appears to be one of the "hardest" combinatorial optimization problems that can be solved in polynomial time.…
Karussell
  • 17,085
  • 16
  • 97
  • 197
9
votes
2 answers

max-weight k-clique in a complete k-partite graph

My Problem Whether there's an efficient algorithm to find a max-weight (or min-weight) k-clique in a complete k-partite graph (a graph in which vertices are adjacent if and only if they belong to different partite sets according to wikipedia)? More…
linusz
  • 743
  • 1
  • 14
  • 26
8
votes
7 answers

Minimum cost strongly connected digraph

I have a digraph which is strongly connected (i.e. there is a path from i to j and j to i for each pair of nodes (i, j) in the graph G). I wish to find a strongly connected graph out of this graph such that the sum of all edges is the least. To put…
Kazoom
  • 5,659
  • 16
  • 56
  • 69
1
2 3
…
11 12