Questions tagged [np-complete]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
64 views

Np-hard sequencing or packing problems with total ordering between elements

I would like to know if anyone is aware of any Np-hard problems in scheduling or packing where there is total ordering between tasks or items to be packed together. The objective can be anything. For ...
user avatar
4 votes
0 answers
48 views

bilinear problem proof for NP-completeness of degeneracy check

In the paper "Some NP-complete problems in linear programming" (https://doi.org/10.1016/0167-6377(82)90006-2), there are several proofs given to show that testing for degeneracy in LPs is NP-...
user avatar
  • 585