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.
8
questions
15
votes
2
answers
2k
views
State-of-the-art algorithms for solving linear programs
Průša and Werner (2019) show that the general linear programming problem reduces in nearly linear time to the LP relaxations of many classical NP-hard problems (assuming sparse encoding of instances)....
- 2,170
7
votes
2
answers
583
views
Optimization Solution Framework
I am working through Pascal Van Hentenryck's excellent discrete optimization course on Coursera.
While the course certainly touches on it in some ways, I am looking for more of a framework in terms of ...
- 217
8
votes
1
answer
1k
views
Why is the Ellipsoid Method of polynomial complexity?
We know that the ellipsoid method is proven to be of polynomial complexity.
However, as far as I can tell we may need to add exponentially many feasibility cuts in order to solve the LP (or prove no ...
- 12.2k
10
votes
2
answers
5k
views
Complexity of LP and MILP Problems?
My original problem is an MILP. I make it an LP by relaxing the integer variables.
Can someone please comment on the complexity, solvability and optimality of MILP and LP problems, in general?
Is ...
- 2,397
6
votes
1
answer
105
views
Complexity \ Reference request for variant of max flow problem
In the standard max cost flow problem with arc capacities, the cost of using an arc is proportional to the flow through the arc. For example, if $f_{uv}$ is the flow through the arc $(u,v)$, then the ...
- 1,583
5
votes
1
answer
392
views
Polynomially solvable cases of zero-one programming
I am dealing with a problem having two types of variables: binary variables, and continuous variables.
In some cases, the continuous variables are not used, and so the problem contains those binary ...
- 2,104
5
votes
2
answers
322
views
Polynomial algorithm for a special ILP problem
Given the following problem:
\begin{align}
& z=\min \sum_{ij} x_{ij}\\
\text{s.t.} & \quad \sum_i d_{ij} x_{ij} \ge s_j, \quad \forall j \tag1 \\
& \quad \sum_j x_{ij} \le 1, \quad \...
- 135
3
votes
0
answers
127
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 ...
- 9,248