The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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.

18 questions
Filter by
Sorted by
Tagged with
183 views

Generalized Assignment Problem as the sub-problem

I was wondering what is the state-of-the-art for solving the Generalized Assignment Problem (GAP) and if there are special cases that are polynomially solvable? Moreover, is there any usage of this ...
763 views

How do we decide/plan an SLA for an NP-hard optimization process running in production?

How do you decide or plan an SLA (Service Level Agreement) for an application that depends on an optimization process when the problems you deal with are NP-hard? That is, if you are developing an ...
895 views

Can an integer optimization problem be convex?

I'm trying to wrap my head around an apparent paradox that I've come across while trying to learn more about optimization algorithms: On one hand several sources state that convex optimization is ...
299 views

Are there NP hard problems solved in P time?

Does anyone know of a problem previously believed to be NP hard, to be solved nowadays in polynomial time optimally?
510 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 ...
449 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)....
2k views

Does the problem of P vs NP come under the category of Operational Research?

I am enrolled in an Operational Research program. I am also interested in Algorithms, and I wish to know whether "P vs NP" is a common point in both of the fields, so that the effort put in ...
497 views

Complexity of verifying optimality in (mixed) integer programming

I looked around for a while, but I couldn't find a precise answer to the following question. If I'm given a candidate solution for a (mixed) integer (convex) program, what's the complexity of ...
272 views

Polynomially solvable problems with exponential extension complexity

The maximum matching problem is solvable in polynomial time using Edmonds' blossom algorithm. However, unlike for example the spanning tree polytope, it has been proven fairly recently that the ...
68 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 ...
182 views

Is deciding the presence of mixed-integer points in the relative interior of a polyhedron in NP?

Given $P = \{x\in\mathbb R^n: Ax \leq b\}$, I want to decide if $(\mathbb Z^\ell \times \mathbb R^{n-\ell}) \cap \operatorname{relint}(P)$ is non-empty. Is this problem in NP? One idea is to check ...
197 views

Can SOCPs approximate better than LPs?

Are there any classes of NP-hard combinatorial optimization problems where Second order cone programs (SOCP) gives a better approximation than linear programs (LP)? I am looking for results in the ...
76 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 ...
134 views

When is the original BFGS algorithm still better than the Limited-Memory version?

I have been going through Andrew NG's original data science course on Coursera. I learned the BFGS algorithm at some point in my OR education, but not the Limited Memory version that Andrew NG focuses ...