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.

9 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9
votes
0answers
104 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 ...
6
votes
0answers
70 views

Sample Average Approximation vs. Numerical Integration

In the sense of the calculation of the expected value of objective functions, we have two choices to evaluate the value; 1. Sample Average Approximation (SAA): $$ \frac{1}{N}\sum_{i=1}^N f(x,\xi^i). $$...
5
votes
0answers
57 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 ...
5
votes
0answers
73 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
118 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 ...
3
votes
0answers
49 views

Polynomial Time Solution For a Mixed-Integer Linear Programming Specific Case

Consider the following mixed-integer linear programming (MILP): \begin{equation*} \begin{array}{ll@{}ll} \text{maximize} & 1 & \\ \text{subject to}& x_{i} \geq 0, &i=1 ,\dots, m\\ ...
2
votes
0answers
60 views

Mathematical model complexity Vs Time Complexity of the model

As far as I know, when we talk about the term of complexity, it referred to the time complexity of the model in which how long does it take to solve a specific mathematical program by a specific ...
2
votes
0answers
38 views

Hardness Reduction for assigning Users to Servers

Suppose there are $x$ servers, and $y$ users. The $y$ users are to be assigned to the $x$ servers similar to classic scheduling problems. The cost of using servers is given by $c(|x|)$ which is an ...
1
vote
0answers
35 views

Spatial complexity of optimization algorithm

How can I calculate the spatial complexity of an optimization algorithm? Otherwise, what would happen if the complexity exceeds the machine capacity, and can I use the hardware instead of RAM? In this ...