9

This is where decomposition algorithms (specifically Dantzig-Wolfe can be quite useful). My thesis work and subsequent OSS in COIN provides APIs to do this kind of thing: https://projects.coin-or.org/Dip The basic idea is that the oracle is the graph implementation while the side constraints are modeled as the master constraints in the decomposition ...


8

If variable fixings can be derived automatically (e.g. you specified a constraint saying $2x_1=4$ and maybe another saying $x_1+x_2=1$), those variables will be fixed at known values. A smaller problem will then be solved, and we will restore the values for the fixed variables when we report the solution (e.g. in this case $x_1=2$ and $x_2=-1$). The cost of ...


7

The prototypical graph search algorithm Dijkstra's algorithm for finding the shortest paths between nodes in a graph which works for unbounded non-negative weights has a time complexity for $O(|V|^2)$ where $|V|$ is the number of nodes/vertices in a graph which is in $P$. There are special cases where further knowledge (such as heuristics) or the graph ...


7

In general ILP solvers are not as efficient in solving the Maximum Matching problem. A comparison of efficient matching algorithm implementations, as well as an ILP formulation for the Maximum Cardinality Matching Problem and the Minimum Weight perfect matching problem can be found in Figures 5 and 6 of this paper: Dimitrios Michail, Joris Kinable, Barak ...


5

It is NP-hard: Bruno Codenotti, Ivan Gerace, Sebastiano Vigna. Hardness results and spectral techniques for combinatorial problems on circulant graphs, Linear Algebra and its Applications 285 (1-3), pages 123-142, 1998, pdf Other Cayley graphs have been studied by Chris Godsil and Brendan Rooney in the paper Hardness of Computing Clique Number and Chromatic ...


5

If only a subset of nodes is to be transfered, and that the cardinality of this subset is undefined, then I agree with @LocalSolver. Otherwise (if all nodes have to be transfered $1$ by $1$), I believe the problem is not NP-hard (nor NP-complete): Consider the following graph : Create a first layer with the $n$ nodes. Create a second layer with $n \times n$ ...


5

So as I mentioned in the comment CLRS is a really wonderful reference and I enjoyed learning from it in my undergraduate algorithms class. But yes, it's a big book so you probably want to pick and choose some useful topics. Here are my suggestions: Ch. 2 is a fine intro to the subject, maybe skim it Ch. 3 is a must and will teach you some of the asymptotic ...


4

You might want to read the paper DIFFERENT VERSIONS OF THE SAVINGS METHOD FOR THE TIME LIMITED VEHICLE ROUTING PROBLEM[1] which gives time complexities between $O(n^3)$ and $O(n^2\log(n))$ note that in these complexity analysis the number of nodes not nodes as $n$. The reason why it is $n^2$ and not $n$ is this part of the algorithm: Taken from EOR 151 – ...


4

I invite you to first check Wikipedia pages on computational complexity and Big O notation. Then, I would recommend you to study the celebrated book "Introduction to Algorithms" written by Cormen, Leiserson, Rivest, and Stein. It will allow you to improve your knowledge and understanding of problem and algorithm theoretical complexity.


4

For a linear program in standard form \begin{align} \min_{x} \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & Ax = b,\\ & x \geq 0, \end{align} where the constraint matrix $A \in \mathbb{R}^{m \times n}$ (i.e., $m$ constraints and $n$ variables) has full row rank (which implies $n \geq m$), the best-known interior-point algorithms require $O(\sqrt{n} \log(1/\...


3

As nicely mentioned above by @Kuifje, the problem can be reduced to a minimum-cost maximum flow problem if all the nodes have to be transferred. If only a subset of the nodes has to be transferred then this is a graph partitioning problem known: partitioning the vertices of a graph into two subsets such that the weight of the cut between the two subsets is ...


3

I think the problem is NP-hard since: it will reduce to the 0-1 Knapsack problem with an equality constraint; and, changing $\leq$ to $=$ in the 0-1 Knapsack constraint does not change its complexity (see explanation below). So, your problem is NP-hard as 0-1 Knapsack is. P.S. To see why (2) is correct, suppose all weights and values are equal. Then the ...


1

As I did not see how one would have to choose the weights in @Kuifje answer I started thinking about the problem as well and I came to the conclusion that it is NP hard. The proof uses reduction of graph partitioning and goes as follows. Let $G = (V,E)$ with $n:=|V|$ even be the graph that we want to find the minimal graph partitioning of. Create an instance ...


Only top voted, non community-wiki answers of a minimum length are eligible