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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
55 views

Verifying certificates versus solving problems

When we learn about P versus NP, we are taught that a certificate for a problem in NP can be verified (or invalidated) in polynomial time. But then the proof that $P \subseteq NP$ ignores the ...
user avatar
  • 349
5 votes
2 answers
86 views

Are "polynomial-time" algorithms for convex minimization actually pseudopolynomial time and/or FPTASes?

Motivating example This question concerns continuous convex minimization. However, the motivating example is the classic binary knapsack problem $$\text{maximize}\quad v^T x \qquad \text{subject to}\...
user avatar
  • 346
5 votes
0 answers
96 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 ...
user avatar
3 votes
0 answers
34 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 ...
user avatar
  • 389
4 votes
2 answers
167 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 ...
user avatar
2 votes
1 answer
82 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 ...
user avatar
  • 1,839
7 votes
2 answers
388 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 ...
user avatar
  • 117
9 votes
1 answer
168 views

A clustering problem with 0 or 1 distances for minimizing the summation of distances

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 \...
user avatar
  • 379
2 votes
1 answer
137 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} where $b$ is ...
user avatar
0 votes
1 answer
78 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 ...
user avatar
7 votes
1 answer
482 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 ...
user avatar
  • 223
5 votes
2 answers
336 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?
user avatar
0 votes
1 answer
94 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 ...
user avatar
  • 65
3 votes
0 answers
57 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\\ ...
user avatar
2 votes
0 answers
65 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 ...
user avatar
  • 5,705
4 votes
1 answer
305 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?
user avatar
6 votes
1 answer
112 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 ...
user avatar
  • 659
-1 votes
1 answer
100 views

How to calculate the complexity order of an optimisation model?

In some optimisation problem it is stated that the complexity is ${\cal O}(n)$ or ${\cal O}(n^2)$. How is this calculated? Any example will be very helpful.
user avatar
6 votes
0 answers
75 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). $$...
user avatar
  • 133
7 votes
1 answer
266 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 ...
user avatar
  • 1,546
8 votes
2 answers
143 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 ...
user avatar
  • 183
7 votes
2 answers
497 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 ...
user avatar
1 vote
1 answer
580 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.
user avatar
4 votes
1 answer
77 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?
user avatar
2 votes
0 answers
40 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 ...
user avatar
  • 871
5 votes
1 answer
123 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 \\ &\...
user avatar
  • 123
5 votes
3 answers
685 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 ...
user avatar
  • 413
2 votes
1 answer
82 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 ...
user avatar
  • 413
4 votes
1 answer
231 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 ...
user avatar
  • 413
6 votes
3 answers
577 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 ...
user avatar
4 votes
1 answer
126 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 ...
user avatar
  • 1,311
6 votes
1 answer
91 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 ...
user avatar
  • 1,311
5 votes
0 answers
60 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 ...
user avatar
  • 1,311
5 votes
2 answers
211 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 \...
user avatar
  • 115
3 votes
2 answers
945 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.
user avatar
  • 115
5 votes
1 answer
348 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 ...
user avatar
  • 2,034
5 votes
0 answers
84 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 ...
user avatar
5 votes
1 answer
63 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?
user avatar
  • 2,034
7 votes
1 answer
126 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$...
user avatar
  • 487
12 votes
1 answer
141 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^...
user avatar
8 votes
1 answer
291 views

Complexity comparision between purely BLP and MILP problems?

Could someone please comment and answer on the complexity of purely binary linear programming (BLP) and mixed-integer linear programming (MILP)? In MILP, we have both binary and continuous variables ...
user avatar
5 votes
1 answer
368 views

Solving a variant of multiple knapsack problem/ generalized assignment problem

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 ...
user avatar
11 votes
2 answers
2k views

MILP: is it NP-complete or NP-hard?

The pieces of information I get online are sometimes confusing. Someone says MILP problems are NP-hard, and somewhere else I found the claim that MILP problems are NP-complete. Can someone please ...
user avatar
8 votes
2 answers
2k 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 ...
user avatar
11 votes
2 answers
261 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 ...
user avatar
19 votes
2 answers
830 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 ...
user avatar
  • 2,009
18 votes
3 answers
4k 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 ...
user avatar
  • 2,009
-4 votes
2 answers
928 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?
user avatar
8 votes
1 answer
848 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 ...
user avatar
14 votes
2 answers
1k 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)....
user avatar
  • 2,110