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
5
votes
2answers
301 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 ...
9
votes
1answer
162 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 \...
2
votes
1answer
124 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 ...
0
votes
1answer
74 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 ...
6
votes
1answer
391 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
2answers
333 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
1answer
81 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
0answers
53 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
0answers
61 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
1answer
297 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
1answer
86 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
1answer
86 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.
6
votes
0answers
73 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
1answer
249 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 ...
7
votes
1answer
98 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
2answers
458 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
1answer
236 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
1answer
75 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
0answers
38 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
1answer
107 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
3answers
674 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
1answer
81 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
1answer
226 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
3answers
408 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
1answer
110 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
1answer
81 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
0answers
58 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
2answers
193 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 \...
3
votes
2answers
851 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
1answer
344 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
0answers
79 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
1answer
62 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
1answer
125 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
1answer
136 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^...
8
votes
1answer
221 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 ...
5
votes
1answer
327 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 ...
11
votes
2answers
1k 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 ...
8
votes
2answers
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 ...
11
votes
2answers
249 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 ...
19
votes
2answers
826 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 ...
17
votes
3answers
3k 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 ...
-4
votes
2answers
783 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?
7
votes
1answer
778 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 ...
14
votes
2answers
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)....
16
votes
6answers
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 ...
12
votes
1answer
549 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 ...
21
votes
1answer
307 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 ...
9
votes
0answers
110 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 ...
11
votes
2answers
194 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 ...
11
votes
2answers
243 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 ...