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

68 questions
Filter by
Sorted by
Tagged with
121 views

### Is OCN=DOCN decidable?

One-Counter Nets (OCNs) are finite-state machines equipped with an integer counter that cannot decrease below zero and cannot be explicitly tested for zero. An OCN $A$ over alphabet $\sum$ accepts a ...
554 views

### How many variables and constraints can modern mixed integer programming solvers handle?

I originally asked a question here and they suggested that I crosspost it to the OR stack exchange, so that is what I am doing (hopefully correctly?). Here is the question I asked there: "I know ...
1 vote
65 views

### Polynomial time separation and optimization for an LP with exponential columns and rows?

We know the fundamental theorem on the equivalence of separation and optimization: an optimization problem can be solved in a polynomial time if and only if there is a polynomial time separation ...
1 vote
105 views

110 views

### How many clues make Sudoku polynomial

Consider a $n^2 \times n^2$ grid sudoku. Define a clue to be composed of a coordinate $x$ and $y$ of the grid and a value $z$. The goal is given $n$ and a set of clues, to find one solution to the ...
43 views

### Complexity of the ellipsoid method in general convex problems

The ellipsoid method is often mentioned in relation to the complexity of solving linear programs. Is the method however polynomial in the general non-linear convex cases? Preferably I would like a ...
278 views

### Reformulate CPLEX optimization model of Warehouse Product Allocation

I am trying to optimize the allocation of of products inside a fictive warehouse, having a predefined number of aisles (3 in the example code below) where products ...
112 views

### Traveling Salesman Reference

Can anyone recommend a reference which shows the amount of time required for the Traveling Salesman Problem (TSP) to be solved using brute force as the number of cities increase? I have informally ...
520 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 ...
184 views

I have a clustering problem with $\{0,1\}$ distances between a set of nodes, which can be stated as follows: Given: Finite set $\mathbb{X}$, a distance $d(x, y) \in \{0,1\}$ for each pair (x, y) \in \... 2 votes 1 answer 149 views ### Is this integer optimization problem still NP? I have the following integer optimization problem \begin{align}\min&\quad\sum_ix_i\\ \text{s.t.}&\quad Ax \geq b\\ &\quad x \geq 0,\\ &\quad x \in \mathbb{Z}^n\end{align} whereb$is ... 0 votes 1 answer 89 views ### How can we prove the solvability time of a linear program? Given a linear program, by experimentation, I can see that the solver can solve large instances in a few seconds. How can I prove that my LP is in polynomial time, or can we say that it is just by ... 7 votes 1 answer 646 views ### RAM requirement for optimization problems I understand that RAM required for optimization problem is problem specific and some problems require much more memory. I am thinking how much RAM I need for my system and need to decide between ... 5 votes 2 answers 353 views ### The importance of evaluating the number of constraints If I introduce a problem, say as an ILP formulation, should I also discuss the number of introduced constraints? If yes, why? 0 votes 1 answer 116 views ### Spatial complexity of optimization algorithm How can I calculate the space 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 ... 3 votes 0 answers 91 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 0 answers 111 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 ... 4 votes 1 answer 348 views ### Complexity of navigation with google maps I was wondering what complexity a simple start-destination task in a routing software would have. Knowing the shortest path problem, it should be in P. Is there anything I am missing? 6 votes 1 answer 286 views ### In which time complexity operates the Savings algorithm for the TSP? In which time complexity operates the Savings algorithm from Clarke and Wright for the TSP? I mean the parallel version of Savings. I think it is in$\mathcal O(|V|\log|V|)$with V as vertex/node ... -1 votes 1 answer 212 views ### How to calculate the complexity order of an optimization model? In some optimization problem it is stated that the complexity is${\cal O}(n)$or${\cal O}(n^2)$. How is this calculated? 6 votes 0 answers 90 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).$$... 7 votes 1 answer 328 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 ... 8 votes 2 answers 188 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 ... 7 votes 2 answers 597 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 ... 1 vote 1 answer 2k 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. 4 votes 1 answer 88 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? 2 votes 0 answers 42 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 ... 5 votes 1 answer 227 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 \\ &\... 5 votes 3 answers 737 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 ... 2 votes 1 answer 88 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 ... 4 votes 1 answer 262 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 ... 6 votes 3 answers 1k 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 ... 4 votes 1 answer 173 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 ... 6 votes 1 answer 101 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 ... 5 votes 0 answers 63 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 2 answers 293 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 \... 5 votes 3 answers 1k 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. 5 votes 1 answer 375 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 ... 5 votes 0 answers 108 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 1 answer 86 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? 7 votes 1 answer 127 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$... 12 votes 1 answer 152 views ### Re-calculating shortest path in slightly altered graph I was wondering if someone has come across this before and/or has a smart idea for the following: I have a directed graph$G$with costs$c$associated with the arcs, and I know the shortest path$P^...
Consider $m$ knapsack and $n$ items. With each knapsack $j$ associated a capacity $c(j)$ and with each item $i$ associated a profit $p(i,j)$ (that depends on the knapsack, so it's not exactly the ...