# 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.

42 questions
Filter by
Sorted by
Tagged with
51 views

### How to calculate the time complexity of a Heuristic Algorithm?

I have a binary integer programming problem. I solve it with a heuristic approach. How can I calculate the time complexity of the heuristic algorithm?
230 views

### Effect of 'unused' variables on the result and runtime of optimization algorithms

I have a general question about the effect of 'unused' variables on the result and runtime of optimization algorithms. I try to explain my question by giving an example. Let's say I have 2 type of ...
88 views

### Reference for algorithms and complexity

What kind of background in algorithms and complexity theory is needed to fully understand the computational aspects of an OR paper. To be specific, I am not always sure when a paper says 'XYZ problem ...
116 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 ...
388 views

### Can a generic ILP solver find graph matchings as fast as a specialized algorithm?

Finding a maximum matching, or a maximum-weight matching, is a well-known problem, which has polynomial-time combinatorial algorithms. It can also be formulated as an integer linear program. In ...
90 views

### complexity order of the interior point method

I was wondering why the complexity order of the interior point method is O()^3 or O()^3.5? Much appreciate your time and consideration.
72 views

### Does anybody know the complexity of finding a maximum clique in circulant graphs?

I would be interested in knowing if finding a maximum clique in circulant graphs is NP-hard? Does anybody have any pointers or papers to suggest?
36 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 ...
87 views

### NP-hardness of a special case of multiple choice knapsack problem

Let us consider the following problem: \begin{align} \max &\quad\sum_{i=1}^n\sum_{j=1}^m v_{i,j}\cdot x_{i,j} \\ \text{s.t.}&\quad \sum_{i=1}^n x_{i,j} =1 &\forall j =1,\dots,m \\ &\...
767 views

### Fast algorithm for Transportation Problem in Python?

The Transportation Problem can be solved with a simplex algorithm, but it's time-consuming. I'm wondering if there exists a specific Python-implemented algorithm with low complexity.
633 views

### How to determine if this problem is NP-HARD or NP-COMPLETE?

Suppose that I have a pool with N nodes and I have to move the nodes one by one to another pool. For each move, consider a value on the edge linking the two pools. The goal is to find a order of nodes ...
78 views

### confusing results of two models with different complexity

i have two models that address the same problem. the first one is : the second one is: for different instances for the same size (n=30) i found the following results ( the first column on the left ...
216 views

### How to determine the size of a model?

I want to know about the number of variables and constraints of this formulation (exp: $o(n)$ variables and constraints or $o(n^2)$ ....). Is the number of variables $\mathcal O(n^3)$ because we have ...
204 views

### How to find all descendant vertices of all vertices in a big DAG (Directed acyclic graph)?

A simple algorithm may be traverse all vertices, and perform DFS for every vertex. However, the computational complexity is $O(n(n+m))$, where $n$ and $m$ are the number of vertices and edges in the ...
85 views

### Max flow problem with piece-wise costs

This question is a variant of a question I posted earlier and also fixes some typos in the earlier post (Complexity \ Reference request for variant of max flow problem). Some of the changes are ...
69 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 ...
329 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 ...
49 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 ...
168 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 \...
63 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 ...
56 views

### If a problem is inapproximable for $(2-\epsilon)$, can we conclude there exists no PTAS for it?

If we prove that: The existance of a $(2-\epsilon)$-approximation algorithm for Problem P1 implies $P = NP$, can we conclude: There exists no PTAS for Problem P1, and so P1 is APX-hard?
124 views

### Can this algorithm be considered polynomial?

Let us assume that an optimization algorithm requires $\mathcal{O}(n^{\log1/\epsilon})$ flops to find a solution $\bar{X}$ such that $$\| \bar{X} - X^{\star}\| \leq \epsilon$$ where $\epsilon < 1$...
132 views

703 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 ...
974 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)....
295 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 ...
3k 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 ...
538 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 ...
2k views

### Are there any efficient algorithms to solve the longest path problem in networks with cycles?

I have a directed social network and as a preprocessing step I need to calculate the longest path lengths for each node. Longest path problem is NP-hard as far as I know but I've seen dynamic ...
92 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 ...
231 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 ...