Questions tagged [computational-complexity]

For questions about the theoretical runtime needed for solving computational problems, often measured in the size of the input. This includes questions about whether polynomial time algorithms exist, NP-hardness, among others.

4 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9
votes
0answers
86 views

Modelling resource dependency in the assignment problem

The assignment problem is well-studied and has a nice polynomial time algorithm. I'm interested in an extension of this problem where all edges are in a certain group and taking multiple edges from ...
5
votes
0answers
56 views

Complexity of determining whether a LP or MIP is infeasible

What is the best complexity for the worst case scenario and the algorithm associated with it to determine if a linear programming (LP) is infeasible ? Further, what if we consider a mixed integer ...
5
votes
0answers
97 views

Maximum eigenvalue across subsamples

I have an $N$-dimensional vector of data, say $X_{t}$, with $1 \leq t \leq T$. Of this vector $X_{t}$, I want to consider sub-vectors, say $X_{t}^{b}$, which are $m$-dimensional combinations of ...
4
votes
0answers
45 views

Complexity of solving a certain commodity flow problem

Does anyone know the complexity of obtaining the optimal solution to the integral multi-commodity network flow problem with unit demands, integral capacities, but the cost of using an arc varies ...