Questions tagged [np-complete]
The np-complete tag has no usage guidance.
6
questions
2
votes
0
answers
121
views
Is OCN=DOCN decidable?
One-Counter Nets (OCNs) are finite-state machines equipped with an integer counter that
cannot decrease below zero and cannot be explicitly tested for zero.
An OCN $A$ over alphabet $\sum$ accepts a ...
- 21
4
votes
2
answers
111
views
A sum with a product-penalty
Let us consider the following optimization-problem: For a given set of tuples $T=(a_1,b_1),\dots,(a_n,b_n)$ and integers $k,C$. The task is to
\begin{align}
\max \quad & \sum_{i=1}^n x_i \cdot a_i ...
- 41
7
votes
1
answer
294
views
BIP for Sudoku naturally integral?
I was reading through the following notes regarding solving a 9x9 Sudoku via a binary integer program
https://vanderbei.princeton.edu/tex/talks/INFORMS_19/Sudoku.pdf
The formulation is straightforward ...
- 137
1
vote
1
answer
85
views
complexity Partitioning with negative numbers
I want to partition a set of numbers in two sets such that their sum is equal. Here in the original master set we can have positive as well as negative numbers. Can anyone tell me about the complexity ...
- 173
2
votes
1
answer
139
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 ...
- 173
4
votes
0
answers
66
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-...
- 892